How to efficiently compute the coefficients in a bi-binomial expansion?

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!

-

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.

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

-
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