0

In how many different ways can eight identical cookies be distributed among three distinct children if each child receives at least two cookies and no more than four cookies?

$x_1 \ ^2$ + $x_2 \ ^2$ + $x_3 \ ^2$ = 8

could be written as -

($x^2$ + $x^3$ + $x^4$)($x^2$ + $x^3$ + $x^4$)($x^2$ + $x^3$ + $x^4$) = $(x^2 +x^3 + x^4)^3$

Now I had to find out coefficient of $x^8$. This was a small problem so I manually calculated it and I got the answer 6, but is there any direct way to find out $a_kx^k$? without any expansion. I know the same problem can be solved using stars and bars method, but I wanted to know if there is any direct way to find coefficient using above method or not.

swapnil
  • 73
  • Good question. Quite often questions concerning distribution are answered with e.g.: "..so it is the coefficient of $x^{17}$". Okay, but how to find this coefficient?... I don't know you. I hope someone else knows and shares this. – drhab Dec 27 '18 at 12:49

2 Answers2

2

A handy identity that often helps in this type of problem is $$1+x+x^2+ \dots +x^n = \frac{1-x^{n+1}}{1-x}$$ so let's see if we can apply it here: $$\begin{align} (x^2+x^3+x^4)^3 &= x^6 (1+x+x^2)^3 \\ &= x^6 \left( \frac{1-x^3}{1-x} \right)^3 \\ &= x^6 (1-x^3)^3 (1-x)^{-3} \\ &= x^6 (1-3x^3+3x^6-x^9) \sum_{i=0}^{\infty} \binom{3+i-1}{i} x^i \end{align}$$ We applied the Binomial Theorem for a negative exponent in the last step.

From the last expression we can easily see that the coefficient of $x^8$ is $$\binom{3+2-1}{2} = 6$$

awkward
  • 14,736
2

In this case, it's very simple because the problem is small, as you say. We have $$(x^2+x^3+x^4)^3=x^6(1+x+x^2)^3,$$ so we need the coefficient of $x^2$in $(1+x+x^2)^3.$ By inspection, we must have either one factor of $x^2$ and two factors of $1$ ($3$ possibilities,) or one factor of $1$ and two factors of $x$ ($3$ possibilities,) for a total of $\boxed{6}.$

Of course, in larger problems, this won't work.

saulspatz
  • 53,131