1
$\begingroup$

There are $N$ different balls and $K$ numbered cells, $K<N$. I need to calculate the number of options to distribute the balls into exactly $L$ cells ($L<K$) so each cell will have at least 1 ball. I tried doing this: I assume all the balls are identical and arrange all the balls in a line, there are $\binom{N-1}{L-1}$ ways to distribute them to L cells so each cell has at least 1 ball, now because the balls are different I have $N!$ ways to arrange them in the line so in total I have $\binom{N-1}{L-1}\cdot N!$ ways to distribute the balls into cells. I have $\binom{K}{L}$ ways to choose the cells that have balls, so the total number of options is $$\binom{K}{L}\cdot \binom{N-1}{L-1}\cdot N!$$ but it is apparently wrong but I don't understand what did I do wrong here


EDIT: after the comment I tried doing this instead: I choose $\binom{K}{L}$ cells and put 1 ball in each cell, I choose the $L$ balls in $\binom{N}{L}$ ways and because the balls are different I have $L!$ ways to distribute them between the $L$ chosen cells, the remaining $N-L$ balls can be distributed in $L^{N-L}$ ways so in total $$\binom{K}{L}\cdot \binom{N}{L} \cdot L! \cdot L^{N-L}$$ but again I got the wrong answer, I assume because there are intersections I missed, at this point I'm not sure how I'm supposed to approach this

$\endgroup$
1
  • $\begingroup$ The $N!$ term is wrong. Suppose $L=2$ and $N=4$. Then $C_1=\{B_1,B_2\},C_2=\{B_3,B_4\}$ is the same as $C_1=\{B_2,B_1\},C_2=\{B_3,B_4\}$ but when you permute all $N$ balls in $N!$ ways, you treat these two as different cases. $\endgroup$ Oct 22, 2020 at 19:47

1 Answer 1

1
$\begingroup$

First choose $L$ cells from $K$ cells $ = {K \choose L}$

Now we need to distribute $N$ distinct balls into $L$ distinct cells where $L \lt N$ and all $L$ cells must have at least one ball. This will require us to apply Principle of Inclusion Exclusion or we can use Stirling Number of the second kind to first distribute distinct balls into $L$ identical cells and then multiply by $L!$.

Using P.I.E, it is $\sum \limits_{i=0}^{L-1} {(-1)^i} {L \choose i} (L-i)^{N}$

For details on P.I.E and why it is necessary in these cases, please see my answer here -

In how many ways can $50$ sweets be distributed to $30$ children so that each child receives at least one sweet?

Using Stirling number of the second kind, it is ${L! \cdot S2[N,L]}$.

In the end, multiply your answer by ${K \choose L}$ which is number of ways of choosing $L$ cells from $K$.

$\endgroup$

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.