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!).
Best Answer
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.