Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Having read on Wikipedia about generating functions, I still don't understand what I can do with a generating function.

For example, if I want to compute the first spread polynomial, how can I do that from a generating function, such as these (taken from the Wikipedia article):

$$ \sum_{n=1}^\infty S_n(s)x^n = {sx(1+x) \over (1-x)^3 + 4sx(1-x)}. $$

An exponential one:

$$ \sum_{n=1}^\infty {S_n(s)\over n!} x^n = {1 \over 2} e^x \left [ 1-e^{-2sx} \cos\left (2x \sqrt{s(1-s)}\right )\right ] $$

share|cite|improve this question
Who confronts you with GF like this without giving you the background? -.- – Raphael Nov 13 '10 at 9:19
@Raphael: I would guess that it comes from Wikipedia: – Hans Lundmark Nov 13 '10 at 12:24
In general, you can't always find an explicit formula from a generating function. That's one thing that makes generating functions more useful than explicit formulas. – Qiaochu Yuan Nov 13 '10 at 16:45
@ Raphael: It was just my curiosity – rubik Nov 13 '10 at 19:33
Ah, ok. Well, as Qiaochu says, getting coefficients from a GF can be very hard. It is often relatively easy to find asymptotics, though, e.g. via Residue Theorem and methods to find asymptotics for complex integrals, e.g. method of steepest descent. – Raphael Nov 14 '10 at 0:00
up vote 5 down vote accepted

If you know what Taylor expansion is, then you should know that $S_n(s)$ in e.g.f. is just its $n$th derivative at zero. For the ordinary g.f., it's almost the same, except that you have to divide the derivative by $n!$.

Anyway, if you want to do more with g.f. than this, I strongly advise you to at least look at this wikipedia page and perhaps even into the generatingfunctionology book, which in my opinion does a pretty good job of introducing g.f. to a beginner.

share|cite|improve this answer
Thank you, I downloaded the book! – rubik Nov 13 '10 at 19:21

HINT $\quad\quad $ With $\rm\ \ \alpha\ =\ 1 - 2\ s + 2\ \sqrt{s^2 - s}\ \ $ we have

$$ \rm \frac{s\ x\ (1+x)}{(1-x)^3 + 4\ s\ x\ (1-x)}\ =\ \frac{\alpha}{4\ (x-\alpha)} + \frac{\alpha'}{4\ (x-\alpha')} - \frac{1}{2\ (x-1)} $$

share|cite|improve this answer

Here it's easier to work with the exponential generating function. You just need to find the Taylor series of each term on the RHS. You already know the Taylor series of one term. To find the Taylor series of the other term, use the fact that $\cos t = \frac{e^{it} + e^{-it}}{2}$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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