# Finding the coefficient of a certain power in a generating function

I want to compute $(t^1+\dots +t^5)(t^2+\dots+ t^6)(t^3+\dots +t^9)$ and find the coefficient of $t^{15}$ for example. $t$ is an indeterminate

Now in Maple this is simply as

p:=sum(t^i,i=1..5)*sum(t^i,i=2..6)*sum(t^i,i=3..9);
coeff(p,t,15);


But I can't seem to learn how to do this in Mathematica.

I have tried using

Series[ %, {t, 1, 10}] * Series[ %, {t, 4, 20}] * Series[ %, {t, 6, 15}]


But it outputs a number(I don't know what this number even is)

Where can I find documentation to solve such a problem?

• What exactly is %?
– Öskå
Sep 4, 2014 at 10:59
• From here @Öskå reference.wolfram.com/language/ref/GeneratingFunction.html. It seems they get what I want, but I exchange $x$ for $t$ Sep 4, 2014 at 11:01
• @Öskå Oh that is embarrassing, % refers to previous entry Sep 4, 2014 at 11:03
• I know, so I was asking what was the previous output, but never mind, the answer is down there :)
– Öskå
Sep 4, 2014 at 11:04
• To closevoters: Did you reallly read the question? Doesn't it really concern Mathematica? Sep 4, 2014 at 17:06

There is a straightforward answer analogous to that in Maple :

Coefficient[ Sum[t^i, {i, 5}] Sum[t^i, {i, 2, 6}] Sum[t^i, {i, 3, 9}], t, 15]

19


This can be verified by expanding the polynomial:

Expand[ Sum[t^i, {i, 5}] Sum[t^i, {i, 2, 6}] Sum[t^i, {i, 3, 9}]]


However you can do it in many different ways e.g. by exploiting CoefficientRules or MonomialList nevertheless the best way for the problem at hand is Coefficient.

It appears more useful when we deal with huge order polynomials and a variable number of them. Then we would rather use also different ways to generate such polynomials, especially more convenient and universal ones.
Here are two alternative ways:

Times @@ (Sum[t^i, {i, ##}] & @@@ {{5}, {2, 6}, {3, 9}})


Instead of Sum one can exploit powerful Mathematica capabilities to deal with lists ( see the Listable attribute) :

Times @@ (Total[t^Range[##]] & @@@ {{5}, {2, 6}, {3, 9}})


In both ways we can generate arbitrarily involved polynomial expressions of the given type.

Edit

It's rather surprising how Coefficient appears to be much faster if we expand given polynomial as observed by mathe.

Let's compare timings for a huge polynomial expression:

(*Coefficient without Expand*)
Coefficient[ Sum[t^i, {i, 500}] Sum[t^i, {i, 20, 600}] Sum[t^i, {i, 30, 900}],
t, 1500] // AbsoluteTiming

{256.218000, 125750}

(*MichaelE2's approach *)

power = 1500;
(p1 = Series[Sum[t^i, {i, 500}], {t, 0, power}];
p2 = Series[Sum[t^i, {i, 20, 600}], {t, 0, power}];
p3 = Series[Sum[t^i, {i, 30, 900}], {t, 0, power}];
SeriesCoefficient[p1 p2 p3, power]) // AbsoluteTiming

{1.272000, 125750}

(*Coefficient with Expand*)

Coefficient[ Sum[t^i, {i, 500}] Sum[t^i, {i, 20, 600}] Sum[t^i, {i, 30, 900}]
// Expand, t, 1500] // AbsoluteTiming

{0.147000, 125750}


Conclusion: Expand is crucial for higher degree polynomials!

• I see, very nice, thank you! Sep 4, 2014 at 11:05
• I recommend to wait for different answers before accepting one at least a few hours, then you will see how many ways to solve probelems there are in Mathematica. Sep 4, 2014 at 11:18
• Probably a good idea, since I will pick up syntax(like my original fail visible in OP comments) Sep 4, 2014 at 11:21
• @Algebra Since you've got quite nice answers to your question you should at least read them, then upvote if they are helpful or if they are misleading downvote and decide which one is the best accepting it. Sep 11, 2014 at 21:17
• Sorry, I do greatly appreciate these answers and will thoroughly read them over the weekend. Thank you for your time! Sep 11, 2014 at 23:34

@Artes's use of Coefficient certainly seems the most straightforward and probably the best for small examples. If the polynomials have very many terms, the use of SeriesData to represent the polynomials will give better performance. The multiplication of series is efficient in Mathematica. One should note that it is truncated beyond the maximum degree represented, so we need to take care to specify it appropriately.

The format of SeriesData is given in the documentation:

SeriesData[x, x0, coeffs, nmin, nmax, den]


This represents a series in the variable x centered at x0. The argument coeffs is a list of coefficients beginning with the least degree which is specified by nmin. The argument nmax is the maximum power represented; if the list coeffs is shorter than nmax - nmin + 1, the missing coefficients are taken to be zero. The argument den is the denominator of the powers, used to represent fractional powers; we will only use den = 1. SeriesCoefficient will extract a coefficient.

Here is one way to apply this idea to the OP's example:

power = 15;
p1 = Series[Sum[t^i, {i, 5}], {t, 0, power}];
p2 = Series[Sum[t^i, {i, 2, 6}], {t, 0, power}] ;
p3 = Series[Sum[t^i, {i, 3, 9}], {t, 0, power}];
SeriesCoefficient[p1 p2 p3, power]
(*
19
*)


Speed

The difference in speed comes mainly from the efficiency of multiplying the series compared to the differentiation/multiplication of the polynomial (or however Coefficient works).

power = 1500;
(p1 = Series[Sum[t^i, {i, 500}], {t, 0, power}];
p2 = Series[Sum[t^i, {i, 20, 600}], {t, 0, power}] ;
p3 = Series[Sum[t^i, {i, 30, 900}], {t, 0, power}];
SeriesCoefficient[p1 p2 p3, power]) // AbsoluteTiming
(*
{0.610942, 125750}
*)

Coefficient[Sum[t^i, {i, 500}] Sum[t^i, {i, 20, 600}] Sum[t^i, {i, 30, 900}], t, 1500] //
AbsoluteTiming
(*
{151.011174, 125750}
*)


The interesting thing about the multiplication of series is that it seems to be cached by the system. So if you want several coefficients, the multiplication is not recomputed. Subsequent calls are much faster:

SeriesCoefficient[p1 p2 p3, power] // AbsoluteTiming
SeriesCoefficient[p1 p2 p3, 500] // AbsoluteTiming
(*
{0.000034, 125750}
{0.000013, 101475}
*)


Of course one could have saved the product in variable, prod = p1 p2 p3. But I thought it was worth noting.

Remark: If the lowest degree in one or more polynomials is high, then more time can be saved by reducing the maximum power of the other series. For example, we can save a tenth of a second:

power = 1500;
mind1 = 1; mind2 = 20; mind3 = 30;
(p1 = SeriesData[t, 0, Table[1, {i, 500}], 1, power - (mind2 + mind3) + 1, 1];
p2 = SeriesData[t, 0, Table[1, {i, 20, 600}], 20, power - (mind1 + mind3) + 1, 1] ;
p3 = SeriesData[t, 0, Table[1, {i, 30, 900}], 30, power - (mind1 + mind2) + 1, 1];
SeriesCoefficient[p1 p2 p3, power]) // AbsoluteTiming
(*
{0.498997, 125750}
*)


Remark 2: I just noticed I snuck in the direct generation of coefficients, basically replacing Sum by Table, without comment. That also speeds up the computation, but only a little. I might also add that if other coefficients are desired, power in the last line may be replaced by any integer less than or equal to power.

• Nice performance +1! Sep 4, 2014 at 17:08
• Try Coefficient[Sum[t^i,{i,500}] Sum[t^i,{i,20,600}] Sum[t^i,{i,30,900}]//Expand,t,1500]//AbsoluteTiming. Sep 9, 2014 at 11:43
• @mathe Wow, what a surprising difference! (I get 0.013 sec by way of comparison.) I don't know if that's worth a separate answer. It's a simple adjustment but a major improvement you've discovered. Sep 9, 2014 at 12:10