2
$\begingroup$

a. If there are no restrictions?

b. Each child gets at least one dime?

c. The oldest child gets at least two dimes?

For part (a), the textbook gives the answer $14 \choose 10$.

Where did the 14 come from? I thought we had 10 dimes to choose from, and 5 children to distribute them to. Why doesn't this come out to $10 \choose 5$?

Thanks!

$\endgroup$

2 Answers 2

2
$\begingroup$

The $14$ comes from the stars and bars approach, counting the number of arrangements with $5-1=4$ bars and $10$ stars. The correspondence can be illustrated by the following example: $$\overbrace{\star\star|\star\star\star\star|\star||\star\star\star}^{\text{stars and bars}} \quad \longleftrightarrow \quad \overbrace{(2,4,1,0,3)}^{\text{who gets what dimes}}.$$ There are $\binom{14}{10}$ such stars-and-bars arrangements.

Instead, $\binom{10}{5}$ is the number of ways of choosing $5$ dimes from $10$ dimes, which doesn't correspond with how to distribute them to the children.

For the second part of the question, we do the same thing after giving one dime to each child. For the third part of the question, we give the oldest student two dimes, then do the same thing again (with $8$ dimes).

$\endgroup$
5
  • $\begingroup$ This is a good method that I should remember more often $\endgroup$ Commented Jan 29, 2016 at 7:21
  • $\begingroup$ I see there are 14 stars and bars total, but then you are "choosing" 10 stars? Or does 10 refer to the number of redundant answers? $\endgroup$
    – nxheller
    Commented Jan 29, 2016 at 7:28
  • 1
    $\begingroup$ @Zed, you are choosing 10 positions for the stars. Could as well choose 4 positions for the bars. $\endgroup$
    – user306935
    Commented Jan 29, 2016 at 7:33
  • $\begingroup$ Do the 10 positions correspond to 10 coins? How do we reconcile this approach with the physical act of giving coins to children? I'm trying to visualize the process. $\endgroup$
    – nxheller
    Commented Jan 29, 2016 at 8:02
  • 1
    $\begingroup$ Yes, 14 positions correspond to 10 coins plus 4 bars. The 4 bars separate 5 slots that correspond to the 5 children. In general, there's one fewer bar than slots. (Next, give each child a dime and then use this method for the remaining dimes to answer the second question.) $\endgroup$
    – user306935
    Commented Jan 29, 2016 at 8:36
1
$\begingroup$

Line the children up in some order, say alphabetically. Let $d_1$, $d_2$, $d_3$, $d_4$, and $d_5$, respectively, denote the number of dimes given to the first, second, third, fourth, and fifth child. Then $$d_1 + d_2 + d_3 + d_4 + d_5 = 10$$ which is an equation in the non-negative integers. A particular solution corresponds to the placement of four addition signs in a row of ten ones. For instance, $$1 1 + 1 1 + 1 1 + 1 1 + 1 1$$ corresponds to the solution $d_1 = d_2 = d_3 = d_4 = d_5 = 2$, while $$1 1 1 + 1 + + 1 1 1 1 + 1 1$$ corresponds to the solution $d_1 = 3$, $d_2 = 1$, $d_3 = 0$, $d_4 = 4$, and $d_5 = 2$. Thus, the number of ways ten dimes can be distributed to five children is the number of ways four addition signs can be inserted into a row of ten ones, which is $$\binom{10 + 4}{4} = \binom{14}{4}$$ since we must choose which four of the fourteen symbols (four addition signs and ten ones) will be addition signs. Alternatively, we can choose which ten of the fourteen symbols will be ones in $$\binom{14}{10}$$ ways.

Note that $\binom{14}{4} = \binom{14}{10}$ since $$\binom{n}{k} = \frac{n!}{k!(n - k)!} = \frac{n!}{(n - k)!k!} = \binom{n}{n - k}$$

The number $\binom{10}{5}$ represents the number of ways we can select a subset of five objects from a set of ten objects, not the number of ways ten identical dimes can be distributed to five children.

For the second question, give each child one dime. Then we must distribute the five remaining dimes to the five children.

For the third question, give the oldest child two dimes. Then we must distribute the eight remaining dimes to the five children.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .