I have the following generating function:

$ (x + x^2 + x^3 + ... + x^m)^k $

I want to find the coefficient of $x^n$ ($ n \geq k,m $)

I tried to think of it from a combinatorial perspective but couldn't get anywhere.

How do I go about it? Any ideas would be appreciated..

EDIT: As Macavity has pointed out, that is indeed what I'm trying to find.

The recurrence I came up with is:

$$ f(n,k) = \sum_{i=1}^m f(n-i, k-1) $$ where $ f(n,k) = 0 \space if \space n \leq 0 $ or $k \leq 0$

$and \space f(n,1) = 1 \space if n \in [1,m]$

  • $\begingroup$ Partition of $n$ into $k$ positive numbers not exceeding $m$? $\endgroup$ – Macavity May 17 '17 at 12:18
  • $\begingroup$ @Macavity Yes. I have edited the question $\endgroup$ – Rushil Paul May 17 '17 at 12:24

It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a series.

We obtain for $n,k\geq 1$ \begin{align*} \color{blue}{[x^n]}&\color{blue}{(x+x^2+\cdots+x^m)^k}\\ &=[x^n]x^k(1+x+\cdots+x^{m-1})^k\tag{1}\\ &=[x^{n-k}]\left(\frac{1-x^m}{1-x}\right)^k\tag{2}\\ &=[x^{n-k}]\sum_{l=0}^k\binom{k}{l}(-1)^lx^{ml}\sum_{j=0}^\infty\binom{-k}{j}(-x)^j\tag{3}\\ &=\sum_{l=0}^{\min\{\lfloor k/m \rfloor, \lfloor (n-k)/m \rfloor\}}\binom{k}{l}(-1)^l[x^{n-k-ml}]\sum_{j=0}^\infty\binom{k+j-1}{j}x^j\tag{4}\\ &\color{blue}{=\sum_{l=0}^{\min\{\lfloor k/m \rfloor, \lfloor (n-k)/m \rfloor\}}(-1)^l\binom{k}{l}\binom{n-ml-1}{k-1}}\tag{5} \end{align*}


  • In (1) we factor out $x^k$.

  • In (2) we use the geometric series expansion and we apply the rule $$[x^{p-q}]A(x)=[x^p]x^qA(x)$$

  • In (3) we apply the binomial theorem and use the binomial series expansion.

  • In (4) we use the linearity of the coefficient of operator, apply the rule as in (2) and restrict the upper limit of the outer series since the expoent of $x^{n-k-ml}$ is non-negative. We also use the binomial identity \begin{align*} \binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q \end{align*}

  • In (5) we select the coefficient of $x^{n-k-ml}$.

  • $\begingroup$ @Rushil: You're welcome! Good to see the answer is useful! :-) $\endgroup$ – Markus Scheuer May 17 '17 at 17:53
  • $\begingroup$ Is there a way to get rid of the summation as well? $\endgroup$ – Rushil Paul May 17 '17 at 19:17
  • $\begingroup$ @Rushil: I don't see a proper way to simplify the expression. $\endgroup$ – Markus Scheuer May 17 '17 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.