Combinatorics – Distinct Ways to Keep N Balls into K Boxes

combinatorics

How many different ways I can keep $N$ balls into $K$ boxes, where each box should at least contain $1$ ball, $N >>K$, and the total number of balls in the boxes should be $N$? For example: for the case of $4$ balls and $2$ boxes, there are three different combinations: $(1,3), (3,1)$, and $(2,2)$.

Could you help me to solve this, please? Please also let me know if there is any classical name for this problem.

Best Answer

From your examples, the boxes are distinguishable but the balls are not.

Well, since each box has to contain at least one ball, place one ball in each box, leaving you with $N-K$ balls to distribute. The problem now turns into the problem of counting in how many ways can you distribute $N-K$ indistinguishable balls into $K$ distinguishable boxes, with no constraints.

Turns out that it's easier then to simply select the boxes that will have the balls. For your examples, having distributed one ball each in the two boxes, we are left with the problem of placing two balls in two boxes. The first combination corresponds to selecting box number $2$ twice; the second to selecting box number $1$ twice; and the third to selecting box $1$ once and box $2$ once.

So you want to make $N-K$ selections from among $K$ boxes; order does not matter; repetitions are allowed. This is a problem of "combinations with repetitions", also known as the "stars and bars problem". The number of ways of making $s$ selections from among $r$ distinguishable possibilities, where the order does not matter and repetitions are allowed is $$\binom{r+s-1}{s} = \frac{(r+s-1)!}{s!(r-1)!}.$$ In your example, we have $r=K = 2$, and $s=N-K=2$, so $\binom{2+2-1}{2} = \binom{3}{2}=3$ distinct ways.

Plugging in $N-K$ for $s$ and $K$ for $r$, we get $$\binom{K+N-K-1}{N-K} = \binom{N-1}{N-K} = \binom{N-1}{K-1}.$$

Related Question