How many ways are there to distribute 15 district objects into 5 distinct boxes with: (i) At least three empty box. (ii) No empty box.
Answers
Answered by
1
The way of partitioning given n distinct objects into k identical (unlabeled) bins is given by Sterling numbers of the second kind. We have to put at least one object in one box.
{ n }
S(n, k) = { } n>=1, k>=1, n>=k
{ k }
S^(k) n = S(n,k) = 1/k! ∑ kj = 0 (-1) k-j k Cj j^n
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:
f(20,10) = - 10C1 x 1^20 + 10C 2 x 2^20 - 10C3 x 3^20 + 10C4 x 4^20
- 10C5 x 5^20 + 10C6 x 6^20 - 10C7 x 7^20
+10C8 x 8^20 - 10C9 x 9^20 + 10^20
= 21473732319740100000
= 2.1473 x 10^19
The result should actually be a multiple of 10!
For part 1 of the question: with at least 3 empty boxes.
A 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.
{ n }
S(n, k) = { } n>=1, k>=1, n>=k
{ k }
S^(k) n = S(n,k) = 1/k! ∑ kj = 0 (-1) k-j k Cj j^n
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:
f(20,10) = - 10C1 x 1^20 + 10C 2 x 2^20 - 10C3 x 3^20 + 10C4 x 4^20
- 10C5 x 5^20 + 10C6 x 6^20 - 10C7 x 7^20
+10C8 x 8^20 - 10C9 x 9^20 + 10^20
= 21473732319740100000
= 2.1473 x 10^19
The result should actually be a multiple of 10!
For part 1 of the question: with at least 3 empty boxes.
A 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.
Similar questions