In how many ways can 10 blankets be given to 3 beggars such that each recieves at least one blanket?

Question

The question was to find the number of ways in which 10 identical blankets can be given to 3 beggars such that each receives at least 1 blanket. So I thought about trying the multinomial theorem...this is the first time I've tried it so I'm stuck at a point...

So $$x_1+x_2+x_3 = 10$$ Subject to the condition that :

$$1\leq x_1 \leq8$$ $$1\leq x_2 \leq8$$ $$1\leq x_3 \leq8$$

As each beggar can get at maximum 8 blankets and at minimum, 1.

So the number of ways must correspond to the coefficient of $x^{10}$ in: $$(x^1+x^2+x^3+x^4+x^5+x^6+x^7+x^8)(x^1+x^2+x^3+x^4+x^5+x^6+x^7+x^8)(x^1+x^2+x^3+x^4+x^5+x^6+x^7+x^8)$$

= coeff of $x^{10}$ in $x^3(1+x^1+x^2+x^3+x^4+x^5+x^6+x^7)(1+x^1+x^2+x^3+x^4+x^5+x^6+x^7)(1+x^1+x^2+x^3+x^4+x^5+x^6+x^7)$

= coeff of $x^{10}$ in $x^3(1+x^1+x^2+x^3+x^4+x^5+x^6+x^7)^3$

= coeff of $x^{10}$ in $x^3(1-x^7)^3(1-x)^{-3}$

= coeff of $x^{10}$ in $x^3(1-x^{21}-3x^7(1-x^7))(1-x)^{-3}$

= coeff of $x^{10}$ in $(x^3-3x^{10})(1+\binom{3}{1}x + \binom{4}{2}x^2+...+ \binom{12}{10}x^{10})$

= $\binom{9}{7} - 3 = 33$

Is this right? From here I get the answer as $\binom{9}{7} - 3 = 33$ but the answer is stated as $36$. I don't understand where I'm making a mistake

Answer 1

Your error is going from

$$(x^1+x^2+x^3+x^4+x^5+x^6+x^7+x^8) (x^1+x^2+x^3+x^4+x^5+x^6+x^7+x^8) \\(x^1+x^2+x^3+x^4+x^5+x^6+x^7+x^8)$$

to

$$x^3(x^1+x^2+x^3+x^4+x^5+x^6+x^7)(x^1+x^2+x^3+x^4+x^5+x^6+x^7) \\(x^1+x^2+x^3+x^4+x^5+x^6+x^7)$$

and you should have written an $x^0$ term as in

$$x^3(x^0+x^1+x^2+x^3+x^4+x^5+x^6+x^7)(x^0+x^1+x^2+x^3+x^4+x^5+x^6+x^7) \\(x^0+x^1+x^2+x^3+x^4+x^5+x^6+x^7)$$

getting you later to

coeff of $x^{10}$ in $x^3(1-x^8)^3(1-x)^{-3}$

and then giving you $36$ rather than $33$

Answer 2

While generating functions are all well and good to understand, it is unnecessary here and a more direct approach is usually preferred.

The technique of stars and bars leads to a direct solution of $\binom{10-1}{3-1}=\binom{9}{2}=\binom{9}{7}$ outcomes where each person receives at least one item.

Answer 3

Try stars and bars. You have $10$ stars for the $10$ blankets:

$**********$

Now you can use $2$ bars to split this into $3$ sections. For example

$**|*******|*$

would mean beggar $1$ gets $2$ blankets, beggar $2$ gets $7$ blankets, and beggar $3$ gets $1$ blanket

Since each beggar should get at least $1$ blanket, we can't put the bars on the outside of the stars, and you also can't have the two bars between the same two stars. In other words, you need to choose $2$ out of the $9$ in-between locations, giving $9 \choose 2$ possible ways to do this.

Answer 4

First give one blanket to each recipient.

Now distribute the remaining $7$ blankets to $3$ recipients without constraints: $36$

If one person gets $7$ (additional) and the others get none, there are $3$ ways to do that. And likewise for the following distributions:

• $700$, $3$ ways
• $610$, $6$ ways
• $520$, $6$ ways
• $511$, $3$ ways
• $430$, $6$ ways
• $421$, $6$ ways
• $331$, $3$ ways
• $322$, $3$ ways (thanks @JMoravitz)

Total = $36$ ways

Answer 5

You may give a blanket to each one and and use stars and bars with remaining $7$ blanket.

You only need two bars with seven stars so the answer is $\binom {9}{2} =36$