Stars and bars
Tonight's idea
Ann, Ben and Cal share ten identical sweets. A child may get none. How many ways are there? Listing them (10, 0, 0, then 9, 1, 0, …) is slow and easy to get wrong.
Draw the sweets as ten stars in a row. Drop in two bars to cut the row into three parts. Ann gets the stars left of the first bar, Ben those between the bars, Cal the rest.
Every sharing gives one picture, and every picture one sharing. So count pictures instead.
A picture is a row of 12 symbols, and all that matters is which 2 of the 12 places hold bars. Pick a place for one bar (12 choices), then the other (11 choices). That is \(12 \times 11 = 132\), but each pair of places has been counted twice, once in each order. So there are 66 ways.
\(n\) identical things shared among 3 people: \(n\) stars, 2 bars, \(\dfrac{(n + 2)(n + 1)}{2}\) ways. For \(k\) people use \(k - 1\) bars.
Watch one: nobody goes without
Now each of the three children must get at least one of the ten sweets. Hand out one each first. There is no choice in that. Seven sweets are left to share freely: 7 stars, 2 bars, 9 places, so \(\dfrac{9 \times 8}{2} = 36\) ways.
Four children need three bars. Ten sweets and three bars fill 13 places. Picking three places in order: \(13 \times 12 \times 11 = 1716\) ways. Each set of three places turns up in \(3 \times 2 \times 1 = 6\) orders, so there are \(1716 \div 6 = 286\) ways.
Your turn
- (a) Draw the stars and bars for Ann 4, Ben 4, Cal 2, and for Ann 0, Ben 10, Cal 0. (b) What sharing is ★★||★★★★★★★★? (c) Two children share 6 identical sweets. One bar, so how many ways?
- How many ways can three children share (a) 5 identical sweets, (b) 8 identical sweets?
- Four children share ten identical sweets, and each child must get at least one. How many ways?
- A bakery sells four kinds of doughnut and has plenty of each. You buy a box of six. Two boxes are the same if they hold the same number of each kind. (a) What are the stars here, and what do the bars separate? (b) How many different boxes are there? (c) How many of them have at least one of every kind?
Stretch: no more than five each
Ann, Ben and Cal share ten sweets, but nobody may have more than 5. How many ways? Start from 66 and remove the bad sharings. To count those where Ann has 6 or more, hand her 6 first. Can two children both have 6 or more?
Answers
- (a) ★★★★|★★★★|★★ and |★★★★★★★★★★|. (b) Ann 2, Ben 0, Cal 8. (c) Six stars and one bar make 7 places, and the bar can go in any of them: 7 ways (Ann gets 0, 1, 2, …, 6).
- (a) 5 stars and 2 bars, 7 places: \(\dfrac{7 \times 6}{2} = 21\). (b) 8 stars and 2 bars, 10 places: \(\dfrac{10 \times 9}{2} = 45\).
- Give each child one sweet. Six are left for four children: 6 stars, 3 bars, 9 places. \(\dfrac{9 \times 8 \times 7}{6} = 84\) ways.
- (a) The stars are the six doughnuts. Three bars separate the four kinds: the stars before the first bar are the first kind, and so on. (b) 6 stars and 3 bars, 9 places: \(\dfrac{9 \times 8 \times 7}{6} = 84\) boxes. (c) Put one of each kind in the box. Two doughnuts are left to choose: 2 stars, 3 bars, 5 places, \(\dfrac{5 \times 4 \times 3}{6} = 10\) boxes.
Stretch. Hand Ann 6 sweets. The other 4 can be shared among the three in \(\dfrac{6 \times 5}{2} = 15\) ways, so 15 sharings give Ann 6 or more. The same goes for Ben and for Cal. Two children cannot both have 6, since that would need 12 sweets, so no bad sharing is counted twice. That leaves \(66 - 3 \times 15 = 21\) ways.