# Turkish Combinatorics problem with distinct balls and boxes

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

• I think you're not counting some particular combinations. When you say "Pair each box with a ball", you're forcing to be the first five balls the ones that have this restriction, but it could be others. With this, you're missing the options where the sixth ball is alone in any of the boxes, because sixth and seventh ball are always the ones that go where another ball was already put. Jul 7 at 11:17
• Initially I had an extra $\binom{7}{5}$ and $\binom{7}{4}$ for case 1 and 2 respectively to deal with this but it gives a negative answer Jul 7 at 11:37
• Because if you do that there is ton of overlapping. For example, $(123), (4), (5), (6), (7)$ would appear if you chose $(1,4,5,6,7)$ as initial balls to fill restriction and after that $(2,3)$ to fill whatever, or if you chose $(2,4,5,6,7)$ to fill restriction and after that $(1,3)$ to fill whatever. Whatever path you choose, you have to consider possible overlapping, that is, combinations that you're counting twice, and possible combinations you could be missing. Jul 7 at 11:41
• @user71207 where did you find this question in Turkish ? Jul 7 at 13:09
• @Bulbasaur do you mean Turskish language? The original I found was also in English, but just stated the source was Turkish Jul 8 at 8:55

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

• I gave the +1 for determinedly using generating functions wherever possible Jul 9 at 11:20
• @trueblueanil Thank you :))) Jul 9 at 11:42

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.)

• I gave the +1 for describing the generalized inclusion-exclusion principle in so simple a way. Jul 9 at 11:19
• I suppose the only change needed to the formula for the exactly j variant is to increase each upper binomial index by $1$ . Jul 11 at 6:54
• @trueblueanil Yes, that's right. Jul 11 at 14:36

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

• I gave +1 ,always giving elegant approaches :) Jul 9 at 11:43
• @Bulbasaur: Thanks a lot ! :) Jul 9 at 12:21