Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many unique 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 unique 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.

share|improve this question
3  
"Stars and Bars" (please see Wikipedia) –  André Nicolas Aug 21 '11 at 4:14
1  
This problem also goes by the name "the number of compositions of $n$ into exactly $k$ parts" –  Mike Spivey Aug 21 '11 at 4:17
3  
For related problems, see the Twelvefold way. –  Calle Aug 21 '11 at 4:33
add comment

2 Answers 2

up vote 7 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
    
+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$. –  Quixotic Aug 21 '11 at 6:33
    
@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. –  Arturo Magidin Aug 21 '11 at 20:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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