这是台湾清华赵启超教授离散数学14A14B课程的笔记。

Generating Functions

Def
Given a sequence $a_0, a_1, a_2, \dotsc ,a_n, \dotsc$, the generating function for this sequence is defined by

$A(x)=a_0+a_1x+a_2x^2+\dotsc +a_nx^n+\dotsc = \sum _{n\ge 0}a_nx^n$

Remark:

1. $A(x)=\sum _{n\ge 0} a_nx^n$ is a "formal" power series.
2. We ignore the convergence issuses of $A(x)$.
3. $A(z)=\sum _{n\ge 0}a_nz^{-n}$ is usually called the $z$ transform of $\{a_n\}$

Example 1
Find the generating function for $a_n=\begin{pmatrix}m\\n\end{pmatrix},n=0,1,\dotsc,m$. $A(x)=\sum _{n=0}^m a_nx^n=\sum _{n=0}^m \begin{pmatrix}m\\n\end{pmatrix}x^n=(1+x)^m$

DEF
The formal derivative of $A(x)=\sum _{n\ge 0} a_nx^n$ is defined as $A^\prime (x)=\sum _{n\ge1}na_nx^{n-1}$

Remark: The usual rules for derivatives still hold for formal derivatives.

Example 2
$a_n=n\lambda ^n, n\ge 0$ Find the corresponding generating function.

$A(x)=0+\lambda x+2\lambda ^2x^2+3\lambda ^3 x^3+\dotsc$

consider $B(x)=1+\lambda x+\lambda ^2x^2+\lambda ^3 x^3+\dotsc$
so $B^\prime(x)=\lambda + 2\lambda ^2x+3\lambda ^3x^2+\dotsc$
therefore $A(x)=xB^\prime(x)$
since $B(x)=\frac{1}{1-\lambda x},B^\prime(x)=\frac{\lambda}{(1-\lambda x)^2}$
$\therefore A(x)=\frac{\lambda x}{(1-\lambda x)^2}$