# How to extract coefficients of a generating function like this one, using a computer?

For example if we have the generating function $$G (x) = (1 + x + ... + x^k)^{10}$$ and we want to calculate the coefficient of $$x^{3k}$$: What is the best way to go about it using Matlab or Mathematica?

• Mathematica questions can be asked on mathematica.stackexchange.com – Spenser Jun 30 at 12:01
• I suppose that you could get different answers depending if the answerer is a Matlab or Mathematice user. – Claude Leibovici Jun 30 at 12:10
• I don't mind using either – oxynoia Jun 30 at 12:15
• I am not a Matlab user. What I can tell you is that, using Mathematica, it is a very simple task. Hoping I am not mistaken, for your case, the seqquence would be $$\{120,2850,29050,182005,831204,3039400,9423040,25717285\}$$ – Claude Leibovici Jun 30 at 12:22
• I'm looking for the coefficient of $x^{3k}$, a number dependant on $k$ – oxynoia Jun 30 at 12:28

You can write: \begin{align*} (1 + z + \dotsb + z^k)^{10} &= \left( \frac{1 - z^{k + 1}}{1 - z} \right)^{10} \\ &= (1 - z^{k + 1})^{10} \cdot (1 - z)^{-10} \\ &= \left( \sum_{0 \le r \le 10} (-1)^r \binom{10}{r} z^r \right) \cdot \left( \sum_{s \ge 0} (-1)^s \binom{-10}{s} z^{k s} \right) \\ &= \left( \sum_{0 \le r \le 10} (-1)^r \binom{10}{r} z^r \right) \cdot \left( \sum_{s \ge 0} \binom{10 + s - 1}{s - 1} z^{k s} \right) \\ &= \sum_{r, s \ge 0} (-1)^r \binom{10}{r} \binom{10 + s - 1}{s - 1} z^{r + k s} \end{align*}
From this you wan to pick off coefficients such that $$r + s k = 3 k$$. This means $$r = 0, s = 3$$, $$r = k, s = 2$$, $$r = 2 k, s = 1$$ or $$r = 3 k, s = 0$$.