# What is a generating function in combinatorics?

I just sat in on a lecture on exponential generating functions in combinatorics (I have no formal education in combinatorics myself). It was quite interesting, but I'm afraid I don't actually understand what the generating function is/does. I've tried doing some minimal research online, but everything I've seen seems to be either too complex or too general to understand well. For example, I know how to find the generating function for permutations of a finite set, $\frac{1}{1-x}$. But what role does $x$ play here, and what does the generating function tell us? I don't see how it's at all related to the species of permutations itself.

• Wikipedia has a short introduction to generating functions. You might especially find the two quotes from Polya and Wilf under "Definitions" interesting. en.wikipedia.org/wiki/Generating_function – awkward Feb 10 '17 at 0:41

## 4 Answers

Suppose you have the sequence $2, 5, 8, 11,...$

One idea might be to have the terms in the sequence as the coefficients of some polynomial. This polynomial is called a generating function of the sequence.

For example:

$$g(x)=2x^1+5x^2+8x^3+11x^4+...$$

All seems fine but how do you recover the sequence if you have the generating function? In this example it is obvious but let's try out a couple of ideas to gain a greater insight.

Notice that differentiation of a power reduces its power by one. We are going to use this idea as a way of sliding the terms of the sequence forwards.

Suppose we want the first term we differentiate $g(x)$ once.

$$g'(x)=2+10x+24x^2+44x^3+....$$

Notice now we can evaluate the polynomial at $x=0$ and find the first term! $g'(0)=2$

The second term is more troublesome, can you see why?

Note the second derivative of the function is $g''(x)=10+48x+132x^2+...$ and that $g''(0)=10$ which is not the 2nd term. All is not lost as we can divide $g''(0)$ by $2$ to recover the second term (we multiplied by $2$ in differentiating). This problem will be exaggerated if we want higher terms in the sequence. The 4th term is found by computing $g^{iv}(0)$ and dividing by $4 \times 3 \times 2$ or $4!$

This situation is a pain and so we may choose to adapt the method.

One idea might be to preload the generating function with the dividing factorials first.

Let's define $$G_1(x)=2\frac{x^1}{1!}+5\frac{x^2}{2!}+8\frac{x^3}{3!}+11\frac{x^4}{4!}+...$$

Now we may differentiate the appropriate number of times and substitute $x=0$ with out hassle.

Finally we can observe the connection to the exponential function as $$e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+...$$

Hope this helps to demystify the exponential at least in part.

• Thank you, that helped tremendously actually! So, is $\frac{1}{1-x}$ considered the generating function because $g(x) = \frac{1}{1-x} = 1 + x + x^2 +...$, so that $g^{(n)}(0) = n!$ – infinitylord Feb 24 '17 at 18:06
• Yes that seems correct. I've used these more to generate moments in stats. Glad to help. – Karl Feb 24 '17 at 18:26

I recommend you to see the book generating functionology by Wilf. It is available online.

The generating function is a power series that is assigned to a sequence. If you have a sequence $\{a_n|n\in \mathbb N\}$ you can assign to this sequence a power series: $\sum\limits_{n=0}^\infty a_nx^n$.

Manipulating the power series using algebra (power series form a ring) can help to find a closed form for the sequence.

• Nice, but the OP asked specifically about exponential generating functions, whereas you have described "ordinary power series" generating functions. – awkward Feb 10 '17 at 0:36

This is really a too-long comment, not a solution, but I can't resist sharing what the statistician Frederick Mosteller had to say about his first encounter with generating functions. He was talking about ordinary power series generating functions (I think), not the exponential generating functions asked about in the OP, but the ideas are similar.

"A key moment in my life occurred in one of those classes during my sophomore year. We had the question: When three dice are rolled what is the chance that the sum of the faces will be 10? The students in this course were very good, but we all got the answer largely by counting on our fingers. When we came to class, I said to the teacher, "That's all very well - we got the answer - but if we had been asked about six dice and the probability of getting 18, we would still be home counting. How do you do problems like that?" He said, "I don't know, but I know a man who probably does and I'll ask him." One day I was in the library and Professor Edwin G Olds of the Mathematics Department came in. He shouted at me, "I hear you're interested in the three dice problem." He had a huge voice, and you know how libraries are. I was embarrassed. "Well, come and see me," he said, and I'll show you about it." "Sure, " I said. But I was saying to myself, "I'll never go." Then he said, "What are you doing?" I showed him. "That's nothing important," he said. "Let's go now."

"So we went to his office, and he showed me a generating function. It was the most marvelous thing I had ever seen in mathematics. It used mathematics that, up to that time, in my heart of hearts, I had thought was something that mathematicians just did to create homework problems for innocent students in high school and college. I don't know where I had got ideas like that about various parts of mathematics. Anyway, I was stunned when I saw how Olds used this mathematics that I hadn't believed in. He used it in such an unusually outrageous way. It was a total retranslation of the meaning of the numbers." [Albers, More Mathematical People].