Turkish Combinatorics problem with distinct balls and boxes

Question

How many ways can you arrange 7 distinct balls into 5 distinct boxes such that at least two of the boxes are empty?

Here is my solution, which seems too big an answer:

I'm not sure if this is valid but here is my attempt:

I will do "TOTAL - (no box empty + one box empty)"

TOTAL: Each ball has $5$ possible choices (boxes) they can go in. Thus the total is simply $5^7$

NO EMPTY: Pair each box with a ball. There are $5!$ ways of doing this (first ball has 5 options, next 4, next 3 etc..). That's 5 balls dealt with after matching them up with boxes, so two left. We deal with these by $5^2$ since they can go in any box (condition has already been satisfied by previous). Thus the total is $5! \cdot 5^2$

ONE EMPTY: First choose a box to be empty $\binom{5}{1}$. The other boxes must be filled - so "matching up balls with boxes" again: $4!$. Then the other 3 balls $5^3$. Thus the total is $\binom{5}{1}\cdot 4! \cdot 5^3$.

My answer is $5^7 - \left(5! \cdot 5^2 + \binom{5}{1}\cdot 4! \cdot 4^3\right) = 60125$

Answer 1

Well , i will use exponential generating functions to solve it.

All situations without restriction is $5^7$ ,as you mention.

Generating function for no box is empty : $(e^x -1)^5$

Generating fuction for one box is empty : $5 \times (e^x -1)^4 =5\times (4^7 -4 \times 3^7 +6 \times 2^7 -4 )=5 \times 8400=42000$ where $5$ is $C(5,1)$ to determine which box will be empty

Then ; the hard part is $(e^x -1)^5 = e^{5x}-5e^{4x}+10e^{3x}-10e^{2x}+5e^x-1 =5^7 -5 \times 4^7 +10 \times 3^7 -10 \times 2^7 +5 =16800$

So $$5^7 - (42000+16800)=19325$$

Answer 2

One approach is to apply the "Generalized Inclusion / Exclusion Principle".

We say an assignment of balls to boxes has "Property $i$" if box $i$ is empty, for $1 \le i \le 5$, and let $S_j$ be the number of assignments with $j$ of the properties, for $1 \le j \le 4$. It's easy to see that $$S_j = \binom{5}{j} (5-j)^7$$

The Generalized Inclusion / Exclusion Principle says that if there are $m$ properties in all, then the number of arrangements with at least $j$ of the properties is $$f_j = S_j - \binom{j}{1} S_{j+1} + \binom{j+1}{2} S_{j+2} - \dots + (-1)^{m-j} \binom{m-1}{m-j} S_m$$ We are interested in the case $j=2$, $m=4$, for which $$f_2 = S_2 - \binom{2}{1} S_3 + \binom{3}{2} S_4 = 19,325$$ so the number of assignments of balls to boxes with at least two of the properties, i.e. with at least two boxes empty, is $19,325$.

The Generalized Inclusion / Exclusion Principle can be found in Schaum's Theory and Problems of Combinatorics by V.K. Balakrishnan, p. 68, or (in a probabilistic form) in An Introduction to Probability Theory and Its Applications, Volume I, Third Edition, by William Feller, p.109.

(Somewhat confusingly, the name "Generalized Principle of Inclusion and Exclusion" is also given to a formula for computing the number of arrangements which have exactly $j$ of the properties instead of at least $j$, but that is not the form we have used here.)

Answer 3

It can be mechanically solved using Stirling numbers of the second kind.

[Choose boxes to fill]$\,$[Fill boxes using S2]$\,$[permute boxes]

To fulfil the conditions, $1,2,\;or \;3$ boxes need to be filled

• $1$ box filled: $\binom51*1*1 = 5$

• $2$ boxes filled: $\binom52*S(7,2)*2! = 1260$

• $3$ boxes filled: $\binom53*S(7,3)*3! = 18,060$

Add up to get $\boxed{19,325}$