Finding the coefficient of a certain power in a generating function

Question

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?

Answer 1

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!

Answer 2

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