I am trying to understand something about this question which appeared in a test i just had. the question is what is the number of ways to split k distinct items into n distinct bins with no bin with exactly one item?

This is my solution for the question using the enclusion-exclusion principle - |Ai|= the number of ways to split k-1 items into n-1 bins when the i item (for k+1>i>0) is in the n-th bin = ${n[(n-1)]}^{(k-1)}$ because there are n options to choose the bin and $(n-1)^{(k-1)}$ to choose the location of the other items. so now using the inclusion-exclusion formula we get - $$|𝑆| = ∑^k_{r=0}(−1)^{r} \cdot (^kC_𝑟) \frac {n!}{(n−𝑟)!} \cdot (𝑛−𝑟)^{(k-r)} $$

well, the answer was actually the same equation i got but they way they did it is also using the inclusion-exclusion principle but a bit different - |Ai|= the number of ways to split k-1 items into n-1 bins when the i-th bin has exactly one ball = ${k(n-1)}^{(k-1)}$. because there are k options to choose the i item. and $(n-1)^{(k-1)}$ to choose the other locations. so you get - $$|𝑆| = ∑^n_{r=0} (−1)^r\cdot(^nC_𝑟)\cdot \frac{k!}{(k−𝑟)!}\cdot(𝑛−𝑟)^{(k-r)}$$

the thing is - you can see that when you write both equations you get actually the same thing (i also tried to place numbers with wolfarm and it is always the same result) . but for some reason the first way wasn't accepted. is there anything wrong about this way???

it seems equal to me and you get the same equation eventually...


By moving the $r!$ in the denominator of $k \choose r$ to pair with the $\frac{n!}{(n-r)!}$, it is immediately clear that the summands are identical between the two summations. The issue is the bounds of summation, and to be technical, both answers are wrong, without additional information about the relationship between $n$ and $k$. Really, both answers should have the upper limit of summation equal to the minimum of $n$ and $k$.

Suppose $k > n$. Then in your argument, if $k \geq r > n$, you are trying to insist that $k$ items be put in $n$ bins such that $r > n$ items are in their own bin. This is impossible. Your formula kind of accounts for this, in that it has a term $(n-r)!$ which is undefined for $r > n$, but it is probably better to correctly assign the bounds of summation.


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.