[R] Indistinguishable balls into distinguishable boxes

[Petr Savicky]

On Sat, Feb 04, 2012 at 08:45:20AM +0100, Marc Girondot wrote:
> Hi "the list" !
> 
> I would like to create a dataframe that answer to : "all the 
> combinations of the different way to distribute n indistinguishable 
> balls into k distinguishable boxes". Let take an example: 2 balls in 3 
> boxes:
> Box1 Box2 Box3
> 2       0       0
> 1       1       0
> 1       0       1
> 0       2       0
> 0       1       1
> 0       0       2

Hi.

The number of these placements is choose(n+k-1, k-1), which follows
from the representation of each placement by a sequence of balls and
boundaries between boxes, where "o" is a ball and "|" is a boundary.
For example (2, 0, 0) corresponds to "oo||" and
(1, 0, 1) is "o||o". Since this is a bijection, we can use it
for counting and also for generation.

  n <- 2
  k <- 3
  # generate all possible positions of the boundaries
  x <- combn(n+k-1, k-1)
  # compute the number of balls in each box
  a <- cbind(0, diag(k)) - cbind(diag(k), 0)
  t(a %*% rbind(0, x, n+k) - 1)

     [,1] [,2] [,3]
[1,]    0    0    2
[2,]    0    1    1
[3,]    0    2    0
[4,]    1    0    1
[5,]    1    1    0
[6,]    2    0    0

Hope this helps.

Petr Savicky.