Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

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
share|improve this answer
add comment

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$.

share|improve this answer
    
Why not $x^{10} \cdot x^2 \cdot 1 \cdot 1 \cdot 1 \cdot 1$ –  Abhijit Apr 4 '13 at 2:45
    
@Abhijit: You mean $x^2\cdot1\cdot1\cdot1\cdot x^{10}\cdot1$? I counted it in the second paragraph. There is no $x^2$ in the second factor. –  Brian M. Scott Apr 4 '13 at 2:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.