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

Question

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!

Answer 1

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.

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