3

I want to find the coefficient of $x^{12}$of the following expression: $$(1+x^{2}+x^{4}+x^{6}+x^{8}+x^{10}+x^{12})(1+x^{4}+x^{8}+x^{12})(1+x^{6}+x^{12})(1+x^{8})(1+x^{10})(1+x^{12})$$

The question is: how can I do that without expading this expression?

Thiago
  • 698
  • 2
  • 8
  • 16

2 Answers2

4

You could extend the geometric progressions in each of the factors indefinitely without creating any new contributions to $x^{12}$ (since the added terms are all of too high degree for that). Your problem then is equivalent to finding the number of solutions $a,b,c,d,e,f\in\mathbf N$ (with $0\in\mathbf N$) to the equation $$ 2a+4b+6c+8d+10e+12f=12, $$ as such a solution counts corresponds to picking terms $x^{2a}$, $x^{4b}$, $x^{6c}$, $x^{8d}$, $x^{10e}$, $x^{12f}$ from the respective factors and muliplying them to give $x^{12}$. After dividing by $2$ this gives the equivalent $a+2b+3c+4d+5e+6f=6$. At this point (or earlier) you may recognise that you are counting the partitions of $6$ (with $a,b,c,d,e,f$ giving the multiplicities of $1,2,3,4,5,6$ as part, respectively), so the answer is going to be $11$.

If you consider looking-up to be cheating, you can do computations of this kind by maintaining an array with the coefficients of the current polynomial, and successively incorporating the factors by multiplication. Each factor being a geometric series $S=1+x^d+x^{2d}+\cdots$, there is a trick to doing this efficiently. Let $P$ be multiplied by $S$, then the (new) coefficient of $x^k$ in $PS$ will be equal to the (old) coefficient of $x^k$ in $P$ plus (if $k\geq d$) the (new) coefficient of $x^{k-d}$ in $PS$; this comes from writing $S=1+x^dS$. So to do the multiplication, traverse the array of coefficients from left to right, adding each coefficient to the one $d$ places to its right, until running off the end of the array. Here is a piece of Python code that does it, just to show how easy it is. It prints $11$.

c = [1]*7                # start with c[0]=1, ... c[6]=1
for d in [2,3,4,5,6]:    # process all factors except the first
  for k in range (d,7):  # process terms that need updating
    c[k] += c[k-d]       # add coefficient from d places to the left
c[6]                     # the value that interests us
Marc van Leeuwen
  • 115,048
1

If you pick $x^{12}$ from the first factor, you must pick $1$ from each of the others; that’s one $x^{12}$ term. The same is true mutatis mutandis if you pick $x^{12}$ from the second, third, or the last factor, so altogether you get $4x^{12}$ from terms with a factor of $x^{12}$, and you can now ignore the last factor: for the remaining $x^{12}$ terms you’ll always be choosing the $1$ from it.

If you choose the $x^{10}$ from the fifth factor, you must pair it with the $x^2$ from the first factor; you get one more $x^{12}$ term this way, and you can now ignore the last two factors.

If you choose the $x^8$ from the fourth factor, you can pair it with the $x^4$ from the second factor or with the $x^4$ from the first factor; no other combination works, and you can now ignore the last three factors and look at

$$(1+x^2+x^4+x^6+x^8+x^{10})(1+x^4+x^8)(1+x^6)\;.$$

Indeed, you can ignore the $x^{10}$ in the first factor, since there’s nothing with which it can be usefully combined. And the rest can be counted by inspection: a $4+8$ combination, an $8+4$ combination, a $6+6$ combination, and a $2+4+6$ combination.

Grand total: $4+1+2+4=11$.

Brian M. Scott
  • 616,228