[Math] Faster way to find coefficient of $x^N$ in $(1 + x + x^2 + x^3 + … + x^A)^K$

Question

I know how to reduce this problem to the convolution of 2 polynomials and then finding the sum of products of certain pairs of coefficients.

I am looking for a faster way or a closed form if possible to find the power of $x^N$ in $(1 + x + x^2 + x^3 + … + x^A)^K$.

I want to avoid iterating over $N$ to find the sum of products of certain coefficients, in the usual solution to this problem.

Is a closed form possible here?

Answer 1

Notice that $$\begin{align} 1+x+x^2+\dots +x^A)^K &= \left( \frac{1-x^{A+1}}{1-x} \right) ^K \\ &= (1-x^{A+1})^K \cdot (1-x)^{-K}\\ &= \sum_i (-1)^i \binom{K}{i} x^{(A+1)i} \cdot \sum_j \binom{j+K-1}{j} x^j \end{align}$$ So the coefficient of $x^N$ is $$\sum (-1)^i \binom{K}{i} \; \binom{j+K-1}{j}$$ where the sum is taken over all pairs of non-negative integers $i,j$ satisfying $(A+1)i+j=N$.