9
$\begingroup$

How many different ways I can keep N balls into K boxes, where each box should atleast 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.

$\endgroup$
12
$\begingroup$

Let $x_1, x_2,\dots,x_k$ be the numbers of balls placed in box $1,2,\dots,k$, respectively. Then you are asking for the number of solutions in positive integers of the equation $$x_1+x_2+\cdots+x_k=n$$ There are many ways you can go about this. You could denote this number by $f(n,k)$ and set up a recurrence, you could find a bijection between these solutions and a more familiar set or you could use generating functions. Notice that $f(n,k)$ is the coefficient of $t^n$ in the expression $$(t+t^2+\cdots)^k=\frac{t^k}{(1-t)^k}=t^k\left(\sum_{m=0}^{\infty}\binom{m+k-1}{k-1}t^m\right)$$ So the number you are looking for is $\binom{n-1}{k-1}$.

$\endgroup$
18
$\begingroup$

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}.$$

$\endgroup$
  • $\begingroup$ +1,Although this problem is not new to me but thank you for the updating me about the formal name of the proof,Anyways I am thinking from last $2$ days,is there any proper derivation when we have to distribute $n$ identical items into $r$ identical groups?As of now I am doing it in the form of usual counting but that's only feasible for small values of $n$ and $r$. $\endgroup$ – Quixotic Aug 21 '11 at 6:33
  • $\begingroup$ @FoolForMath: Distributing $n$ iddentical identical items into $r$ identical groups with no restrictions is the equivalent of counting the number of partitions of $n$ into at most $r$ parts. $\endgroup$ – Arturo Magidin Aug 21 '11 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.