Refer to Combinatorics and Probability, Baffle_Method occured in Tutorial 8.
Combinations and Permutations
and
The number of ways to select k items from a set of n items:
| With Replacement | Order Matters | Formula |
|---|---|---|
| Yes | Yes | $n^k$ |
| No | Yes | $(n)_k$ |
| No | No | $\binom{n}{k}$ |
| Yes | No | $\binom{n+k-1}{k}$ |
Question
a. How many ways can 20 identical balloons and 32 distinct lollipops be distributed among 4 children?
b. What if each child gets at least 1 ball and exactly 8 lollipops?
Answer
identical means totally the same, so that we don’t distinguish any of them.
In this question, we focus on Baffle Method, so we focus only on the identical 20 balloons.
Analysis
a
a. 20 identical balloons would be distributed to 4 children. May someone gain 0 or 20 balloons.
The question is a category question. It’s not a permutation or comborics problem. We need to divide the 20 balloons into 4 categories, with order of the item numbers.
For example, list a small number:
Four identical balloons, distribute them to 3 different children.
There are some solutions:
0 0 4
0 4 0
4 0 0
1 0 3
1 2 1
...
Obviously it’s a category problem. We need to divide rather not a pure permutate or combination.
Imagine the baffles and four balloons.
Four different children, means three baffles. We regard the baffles as the balloons. So there are six positions, and there should be two baffles in them.
Then we talk about the baffles’s combinations so that we could know how many conditions that the baffles could divide the balloons.
$\binom{4+3-1}{2} = \binom{6}{2}$
Yes! We have solved four balloons!
Then we look back to the 20 balloons:
$\binom{20+4-1}{3} = \binom{23}{3}$
Imagine there are totally 23 positions, and we choose 3 positions as baffles in them.
b
b. What if each child gets at least 1 ball and exactly 8 lollipops?
We think of the three different children and four balloons firstly.
We found we can only confine the baffle positions into the intervals of the four balloons, so that every child could gain at least one balloon.
Hence $\binom{4-1}{3} = \binom{3}{3}$
The same to the b question, we gain $\binom{20-1}{3} = \binom{19}{3}$.
Welcome to point out the mistakes and faults!