Question 1205233: In a cars carrier, how many ways are there to put 8 cars labeled as {A, B , ..., H} in 4 containers labeled as { 1, 2, 3, 4 }? Each container must include at least one car.
Your answer is:
If the containe #1 must have the car A in it, find the new number of possible ways.
Your answer is:
Answer by ikleyn(52903)   (Show Source):
You can put this solution on YOUR website! .
This problem (first part) asks in how many ways 8 distinguishable items can be distributed
in 4 distinguishable boxes so that each box has at least one item.
Solution
The formula for the number of distributions of n distinguishable items in m distinguishable boxes
so that no one box is empty is
F(n,m) =  . (1)
The sources for this formula are these references
Feller - An Introduction to Probability Theory and its Applications, Vol I, 3ed, 1968,
Chen Chuan-Chong, Koh Khee-Meng - Principles and Techniques in Combinatorics, 1992,
Anderson - A first course in combinatorial Mathematics, 2001.
To make calculations using this formula, I prepared Excel spreadsheets for some different values n and m.
Below are calculations for n= 3, m= 2 (three balls in two boxes).
k (-1)^k combin(2,k) (2-k)^3 Separate addends
of formula (1)
0 1 1 8 8
1 -1 2 1 -2
6 <<<---=== Final sum F(3,2)
You can check it manually that F(3,2) = 6 is the correct number of different distributions
of 3 distinguishable balls in 2 distinguishable boxes.
Below are calculations for n= 4, m= 2 (four balls in two boxes).
k (-1)^k combin(2,k) (2-k)^4 Separate addends
of formula (1)
0 1 1 16 16
1 -1 2 1 -2
14 <<<---=== Final sum F(4,2)
You can check it manually that F(4,2) = 14 is the correct number of different distributions
of 4 distinguishable balls in 2 distinguishable boxes.
And finally, below are calculations for n= 8, m= 4 (8 balls in 4 boxes, the requested case).
k (-1)^k combin(4,k) (4-k)^8 Separate addends
of formula (1)
0 1 1 65536 65536
1 -1 4 6561 -26244
2 1 6 256 1536
3 -1 4 1 -4
40824 <<<---=== Final sum F(8,4)
ANSWER. The number of all different distributions of 8 distinguishable objects in 4 different boxes is 40824.
This part is solved.
|
|
|
