Permutation and Combination - Algebraic Expansion

Question

I have come across the following question and solution

Question

In how many different ways three persons A, B, C having 6, 7 and 8 one rupee coins respectively can donate Rs.10 collectively.

Solution given (http://www.askiitians.com/iit-jee-algebra/permutations-and-combinations/derangements-and-multinomial-theorem.aspx)

The number of ways in which they can denote Rs.10 is the same as the number of solutions of the equation $x_1 + x_2 + x_3 = 10$ subject to conditions $0 \leq x_1 \leq 6$, $0 \leq x_2 \leq 7$, $0 \leq x_3 \leq 8$.

Hence the number of solutions is $$ \begin{align} &=[x^{10}](1+x+x^2+...+x^6)(1+x+x^2+...+x^7)(1+x+x^2+...+x^8)\\ &=[x^{10}]\frac{(1-x^7)(1-x^8)(1-x^9)}{(1-x)^3}\\ &=[x^{10}](1-x^7-x^8-x^9)\left(1+\binom{3}{1}x + \binom{4}{2}x^2+ \binom{5}{3}x^3+...+\binom{12}{10}x^{10}\right)\\ &= \binom{12}{10} - \binom{5}{3} - \binom{4}{2} - \binom{3}{1}\\ &= 66 - 10 - 6 - 3 = 47. \end{align} $$ My Doubt is how coefficient of $x^{10}$ in $(1-x^7)(1-x^8)(1-x^9)/(1-x)^3$ is equal to coefficient of $x^{10}$ in $(1-x^7-x^8-x^9)(1+\binom{3}{1}x + \binom{4}{2}x^2+ \binom{5}{3}x^3+...+\binom{12}{10}x^{10})$ ?

Please help. Thanks in advance.

Answer 1

There are two things at play here.

1. Expansion of $(1-x)^{-3}$. Here, we use a (negative) binomial series: $$ \begin{align} (1-x)^{-3}&=\sum_{n=0}^{\infty}\binom{-3}{n}(-1)^nx^n\\ &=\sum_{n=0}^{\infty}\frac{(-3)(-3-1)(-3-2)\cdots(-3-(n-1))}{n!}(-1)^nx^n\\ &=\sum_{n=0}^{\infty}\frac{(-1)^n3\cdot4\cdot5\cdots(3+n-1)}{n!}(-1)^nx^n\\ &=\sum_{n=0}^{\infty}\frac{(n+2)_{n}}{n!}x^n\\ &=\sum_{n=0}^{\infty}\binom{n+2}{n}x^n, \end{align} $$ where $(a)_b$ is the falling factorial. Notice, here, that all terms have a non-negative power of $x$.

2. Expansion of $(1-x^7)(1-x^8)(1-x^9)$. When you multiply this out, you get $$ 1-x^7-x^8-x^9+x^{15}+x^{16}+x^{17}-x^{24}. $$

Let us combine these two results. We can think of multiplication of two such sums as the sum of terms obtained by taking one element of the first and one element of the second, and multiplying them. Since neither sum involves any negative powers of $x$, we can never choose any term from either which involves $x^{11}$ or higher - such a term can never yield an $x^{10}$. So, we find $$ \begin{align} &[x^{10}](1-x^7-x^8-x^9+x^{15}+x^{16}+x^{17}-x^{24})\sum_{n=0}^{\infty}\binom{n+2}{n}x^{n}\\ =&[x^{10}](1-x^7-x^8-x^9)\sum_{n=0}^{10}\binom{n+2}{n}x^n, \end{align} $$ as claimed. From here, extracting the coefficient by $x^{10}$ should be no problem.