12 distinct objects are distributed into 10 distinct box such that each box is non-empty. Find probability that no box contain 3 elements

Question

My thinking :-

$n(\text{Sample space})=10^{12}-\binom{10}{1}(10-1)^{12}+\binom{10}{2}(10-2)^{12}-...-\binom{10}{9}(10-9)^{12}$

(Found by principle of inclusion and exclusion).

Now we see that one box cannot have more than $3$ objects. for example if one box has $4$ objects then we have to divide $8$ objects into $9$ boxes such that each is non-empty which is not possible. Also no two boxes can have $3$ objects as then we would have to divide $6$ objects into $8$ box such that none is empty which is also not possible. So by my logic the only possibility we have to think about is that one box has $3$ elements and the other $9$ objects are divided into 9 box such that each is non empty. And then the probability of our required event is just $1-$ the probability of the above event.

If I view that I have to put 9 distinct object into 9 box such that none is empty , then I am just looking at permutation of 9 things(sort of like defining a bijective function from a set of 9 elements to another).I am concluding this from the fact that no box cannot have more than 1 element(as it would lead to 7 objects into 8 box) Now the possibilities of the above event is just:- $\binom{10}{1}\cdot9!=10!$ .

But If I view this again from principle of inclusion and exclusion then I am getting the expression:- $\binom{10}{1}\cdot(\displaystyle\sum_{k=0}^{9}\binom{9}{k}(-1)^{k}(9-k)^{9})$ . Now I know that these to are equal. Can someone suggest me how to prove that this summation also equals to $9!$?.

So anyways....the probability would just equal:-

$$\displaystyle 1-\frac{10!}{(\sum_{k=0}^{10}\binom{10}{k}(-1)^{k}(10-k)^{12})}$$

Is my reasoning correct? . Did I miss some cases? . Also how to prove the summation is same as the factorial? ( Not in a intuitive way . I know that the 9 object in 9 box is 9!, I want to show the summation equals 9!).

Answer 1

You are not counting the favorable cases correctly.

For sample space, you can apply Principle of Inclusion Exclusion, Stirling Number of Second Kind or simply count as in this answer.

As all boxes are non-empty, either two of the boxes have $2$ balls each or one of them has $3$ balls.

So sample space is,

$ \displaystyle {12 \choose 3} \cdot 10! + \underbrace{{12 \choose 2} {10 \choose 2} \cdot \cfrac{10!}{2!}}_{\text{favorable cases}}$

Favorable cases are those where none of the boxes have $3$ balls.

If you are finding sample space using P.I.E, you can subtract $ \displaystyle {12 \choose 3} \cdot 10!$ from it to find favorable cases.

Answer 2

You have ver elegant answer , but i want to give you another approach , it may help you to get rid of long processes. The name of this method is exponential generating functions ,which can be used when distributing distinct objects into distinct boxes.

I will not get in the logic of exponential generating functions , you can find it in many of combinatorics books.

Our denominator will be the number of cases where none of the boxes are empty. Hence , our exponential generating function will be $$\bigg(x + \frac{x^2}{2!} + \frac{x^3}{3!} \bigg)^{10}$$

because if each boxes have at least one object , then a box can have at most $3$ objects.

If none of the boxes have $3$ objects then , the exponential function turn out to be $$\bigg(x + \frac{x^2}{2!} \bigg)^{10}$$

Then we should find the coefficient of $[x^{12}]$ or find the coefficient of $x^{12}$ and multiply it by $12!$.

If you use wolfram to calculate them ,you will find that the coefficient of $x^{12}$ in the expansion of $\bigg(x + \frac{x^2}{2!} \bigg)^{10}$ is $\frac{45}{4}$ . Moreover , the coefficient of $x^{12}$ in the expansion of $\bigg(x + \frac{x^2}{2!} + \frac{x^3}{3!} \bigg)^{10}$ is $\frac{155}{12}$.

Then our answer is equal to $$\frac{12! \times \frac{45}{4}}{12! \times \frac{155}{12}}= \frac{5,388,768,000}{6,187,104,000}=0.870967741935...$$