Combinatorics – Finding Coefficient of Generating Function

combinatoricsgenerating-functions

Find the coefficient of $x^{52}$ in $$(x^{10} + x^{11} + \ldots + x^{25})(x + x^2 + \ldots + x^{15})(x^{20} + x^{21}+ \ldots + x^{45})$$

One thing I tried doing was factoring out $x^{10}, x, x^{20}$ from each of the products, respectively, then using the identity of a product of two polynomials to obtain the coefficients…But I ended up with $1$. I can't figure this out and any help would be much appreciated!

Best Answer

The original problem, after factoring out the terms as stated in the post, we have $$ x^{10}(1+x+\ldots+x^{15})\cdot x(1 + x + \ldots+x^{14})\cdot x^{20}(1+x+\ldots+x^{25}) \tag{1} $$ Applying some identities, $(1)$ gives $$ x^{31}\cdot\frac{1-x^{16}}{1-x}\cdot\frac{1-x^{15}}{1-x}\cdot\frac{1-x^{26}}{1-x} \tag{2}$$ Rearranging the terms, we then have $$ x^{31}\cdot(1-x^{16})\cdot(1-x^{15})\cdot(1-x^{26})\cdot \frac{1}{(1-x)^3} \tag{*} $$ The last term in the above product is equal to $$1 + \binom{3}{1}x + \binom{4}{2}x^2 + \ldots \tag3$$ Finally we take the products that can result in $x^{52}$ and obtain the coefficients:

  1. $x^{31}$ (first term in $(*)$) and $x^{21}$ (from $(3)$),
  2. $x^{31}$, $x^{16}$ (second term in $(*)$), $x^5$ in $(3)$
  3. $x^{31}$(first term in $(*)$), $x^{15}$ (third term in $(3)$), and $x^6$ in $(3)$

Since all the coefficients of the polynomials equal $1$ or $-1$ except for the polynomial expanded in $(3)$, we have as our coefficient $$ \binom{21+3-1}{21} - \binom{6+3-1}{6} - \binom{5+3-1}{5} = 204 $$

Note: I hadn't seen Andre's solution prior to typing this.

Related Question