Generating Functions

Why generating function?

For some counting problems, especially the ones that ask you to find out the number of ways to pick some items with a certain total number, it is hard to directly count the number of plans in total as the answer might be very large, while it's also hard to directly apply multiplication or addition rule as the problem might be complex.
To solve these questions, we can use a technique that I'm going to introduce in this article, instead of counting by hand. You only need to design a function called "generating function", and apply some algebra skills that you have learned in high school to dissolve it into a polynomial. Then, the coefficient of each is the answer that you want!

Ordinary Generating Functions

Definition: [Generating Function]
For a sequence of real numbers, we call the function the generating funciton of sequence .

Example 1 [¹]
, gives

Example 2 [¹]
,

Example 3 [¹]
,

Exponential Generating Functions (EGF)

Definition: [Exponential Generating Function]
For a sequence of real numbers, the exponential generating function of the sequence is .

Example 1 [¹]
, gives .

Example 2 [¹]

gives

Example 3 [¹]
# n-permutations of {1, 2, 3, ..., m},

Now, we have known the definition of EGF, but why we need to invent such a special kind of generating function?
Well, the main reason is the coefficient of a single generating function might be too big to converge, or hard to calculate. For example, if you need to choose balls from indistinguishable balls, you have exactly one way to do this. However, if the balls are "distinguishable", or "labelled", there will be totally ways to choose the balls, with in each coefficient. With divided for each , it will greatly reduce each coefficient, making the multiplication of all GF more "calculatable".
Also, the "identity function" of EGF is , which is much easier to be multiplied on other EGF, make it much easier to calculate.

Solve Nonhomogeneous Recurrence Relations (By GF)

Consider with [²], we have If we add them up, it's clear that as all of the remaining items are eliminated by the recurrence relation. Therefore, we have , which gives us the final answer by doing polynomial division.

To Be Continued: Dirichlet series generating function (DGF)

Reference

• [1] [Lecture Notes written by Professor Balázs Boros]
• [2] [Richard A. Brualdi - Introductory Combinatorics (5th Edition)]