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

You can use higher order differentials. That is, assuming $A,K\in\Bbb{N}$, if $$f(x)=(1 + x + x^2 + x^3 + ... + x^A)^K$$ then the coefficient of $x^n$ in $f(x)$, i.e., $a_n$, is $$a_n=\frac{f^{(n)}(0)}{n!}$$ where $$f^{(n)}(x)=\frac{\mathrm{d}^n}{\mathrm{d}x^n}f(x)$$ This is a closed-from solution, but I don't know that's what you're looking for.

Answer 2

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

Answer 3

You can use the Multinomial Theorem. The general formula for the coefficient of $(x_0+x_1+x_2+...x_m)^n$ is $\frac {n!}{r_0!r_1!r_2!...}x_0^{r_0}x_1^{r_1}x_2^{r_2}...$ where $\sum_{k=0}^mr_k=n$.

In your case, you can use the powers of $x$ for the stuff inside the parentheses.

You need to make sure to add up all terms that would end up with the same power.

For instance to find the coefficient of $x^2$ in $(1+x+x^2+x^3+x^4)^5$, you need to add the coefficients of the terms you would get for $(1)^4*(x)^0*(x^2)^1*(x^3)^0*(x^4)^0*(x^5)^0$ ($x^2$ times a bunch of ones) and $(1)^3*(x)^2*(x^2)^0*(x^3)^0*(x^4)^0*(x^5)^0$ ($x$ times $x$ times a unch of ones), which would be $\frac{5!}{4!0!1!0!0!}+\frac{5!}{3!2!0!0!0!}=5+10=15$.