Two empty boxes with whole square,two boxes empty boxes with divided by 2,three empty boxes with add 1, three empty boxes with multiple of 3
Answers
Answer:
This is not as straight forward as it seems. We cannot solve like, distribute first one object into each box and then the remaining 10 objects as we like with all possibilities among the boxes.
The way of partitioning given n distinct objects into k identical (unlabeled) bins is given by Sterling numbers of second kind. We have to put at least one object in one box.
{ n }
S(n, k) = { } n>=1, k>=1, n>=k
{ k }
The number of ways to distribute n distinct objects into k distinct labeled boxes (at least one object in each box) is given by k! * S(n, k). This is because we can permute the k boxes in k! ways. let us call these numbers as : f(n, k) = k! * S(n, k)
We can compute these sterling numbers for different n and k.
S(0,0) = 0. S(1,1) =1, S(n,1) = 1 S(n, n) = 1
f(0,0) = 0 f(1,1) = 1 f(n , 1) = 1 f(n, n) = n !
f(n, 2) = 2^n - 2
There is a recurrence relation among these numbers.
S(n+1, k) = k S (n, k) + S(n, k-1)
f(n+1, k) = k [ f(n, k) + f(n , k-1) ]
Thus we can find their values. with at least one object in each of 10 boxes:
The result should actually be a multiple of 10!..
======================
For part 1 of the question: with at least 3 empty boxes.
Number of the ways with all distinct objects being distributed in any fashion, with any number of objects in any distinct box. = 10^20
as for each object there are 10 ways, by putting it in any of the boxes.
Ways of 20 distinct objects being put in 10 distinct boxes, with one box empty:
10C1 * f(20, 9) = 10 * f(20, 9)
Ways of 20 distinct objects being put in 10 distinct boxes, with two boxes empty:
10C2 * f(20, 8) = 45 * f(20, 8)
So the answer for distribution of 20 objects in 10 boxes (distinct) with at least 3 boxes empty will be = 10^20 - 10 f(20, 9) - 45 *f(20,8)
This number will also be in the range of 10^19.