Learning Notes on Generating Functions

Generating Function is a way to represent a sequence of number using coefficients of a polynomial.

The two most commonly used generating functions is:

1. Ordinary generating function (OGF)
$$G(a_n; x) = \sum_{n = 0}^{\infty}a_n x^n $$

2. Exponential generating function (EGF)
$$EG(a_n; x) = \sum_{n = 0}^{\infty}a_n \frac{ x^n }{n!} $$

The first one is used in combination, while the second is used in permutations.

For the second one, suppose we have two EGFs $f$ and $g$, then $$f(x) g(x) = \sum_{n=0}^{\infty} (\sum_{i=0}^{n} {{n}\choose{i}} f_i g_{n-i}) \frac{x^n}{n!}$$

Related Problems:

1. Representing $(x_1 + x_2 + .. + x_n)^k$: Codechef PSUM, HackerRank A Summation Problem
First of all, we can solve the problem in a knapsack fashion for the No. of the number item and the sum of items we are considering. Then we can keep a EGF $f$ s.t. the $i$-th term is the sum of all possible $(a_1 + a_2 + … )^i$. Then by multiplying $g(i) = \sum_{i = 0}^{k} \frac{{ v_i }^k}{n!}$, we put the $i$-th item in and permute with the terms in the sum.

2. Generating Functions and Knapsack Problem: Asia Shenyang 2018 M
In this problem we try to formulate knapsack problem to a generating function: $$\prod_{i = l}^{r} \frac{1 – x^{(a + 1) b}}{1 – x^b}$$. Also we have $$\frac{1}{1 – x^k} = 1 + x^k + x^{2k} + x^{3k} + …$$. Then we can precompute the prefix product and inverse product. To answer a query, we need to calculate the coefficients with the terms of powers $\leq c$ in the product.
Note:
1. From the generating function, we can also see undoing complete knapsack (where each item can be used many times) is the doing 0/1 knapsack (where each item can be used at most once) with a opposite coefficient. Just like the “add” and “del” function in this submission.
2. In each query, directly computing the product will be too costly. A neat trick is to make each coefficient the prefix sum of the correpsonding position for one of the polynomial beforehand, and then just take the coefficient of $x^c$ in the product. Then each query can be answer in $O(C)$.

3. Exponential Generating Functions: ZOJ4069
First key observation is that if $m < n$ (we also need to handle other cases very carefully), it must be composed by a $n – m$ chains. For one chain, the number ways it can be compsed by $n$ vertices is $\frac{n!}{2}$ if $n \geq 2$ and $1$ if $n = 1$. Then after dividing $n!$ for each term, the EGF is in a nice form $EG = \frac{1}{2}(2x+ x^2 + x^3 + x^4…) = x {(1 + \frac{1}{1 – x})}$. Suppose the coefficient of $x^n$ in $EG^m$ is $k$. The answer will be $\frac{k \cdot n!}{(n – m)!}$ because we didn’t specify the order of the $n – m$ chains. We can brute-forcedly calculate the answer since the form is not complicated.

Reference:
1. Generating Function – Wikipedia