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.

Is there a computationally efficient way of calculating the coefficients of the polynomial expansion of expressions like $(1+x^a)^m(1+x^b)^n$ for arbitrary positive integers $m,n,a,b$ (and especially with $a=1$ and $b=2$)? The bi-binomial expansion $\sum_{i=0}^m\sum_{j=0}^n \binom{m}{i}\binom{n}{j}x^{ai+bj}$ doesn't really solve the problem, as adding up the contribution from all the possible combinations of, say, $k = ai+bj$ is still quite inefficiet...

And, by the way, I need all the coefficients at the same time, so some kind of fast iterative relation works fine too!

share|improve this question

2 Answers 2

Since you're after all coefficients, why not just first compute lines $m$ and $n$ of Pascals triangle, then allocate an array $c$ of coefficients indexed by $0$ to $am+bn$, initialised to $0$, and then perform

for i from 0 to n
  for j from 0 to m
    c[a*i+b*j] +:= Pascal_row_m[i]*Pascal_row_n[j]

This avoids any search for proper $(i,j)$ combinations, they all come together in the right place magically.

share|improve this answer
    
I have actually though of this before. It's just that this method scales as $\mathcal{O}(m\times n)$, which I had hoped could be improved... –  Sleort Jan 11 '13 at 10:38
    
I think that hope is mighty optimistic. Indeed for unrelated large $a$ and $b$ you get $O(mn)$ different nonzero coefficients to compute. –  Marc van Leeuwen Jan 11 '13 at 10:49
    
Sure. But when a and b are related, $a = 1, b=2$... –  Sleort Jan 11 '13 at 10:55

The canonical way to solve this kind of problem is via Stirling's theorem or normal approximation. I doubt if there are quick ways to solve this precisely because the complexity is exponential.

share|improve this answer
    
I would disagree with the uses of both "canonical" and "solve". –  Marc van Leeuwen Jan 11 '13 at 10:33
    
Thanks for the reminder. –  Bombyx mori Jan 11 '13 at 10:37

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.