# [学习笔记] 生成函数基础

## 形式幂级数

### 定义

$$A(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n = \sum_{n=0}^{\infty} a_n x^n$$

$$A(x) = 1 + x + x^2 + x^3 + \cdots + x^n$$

### 泰勒展开

$$f(x) = f(a) + \frac{f'(a)}{1!} (x-a) + \frac{f^{(2)}(a)}{2!}(x-a)^2 + \cdots + \frac{f^{(n)}(a)}{n!} (x-a)^n + R_n(x)$$

### 麦克劳林展开

$$f(x) = f(0) + \frac{f'(0)}{1!} x + \frac{f^{(2)}(0)}{2!}x^2 + \cdots + \frac{f^{(n)}(0)}{n!} x^n + R_n(x)$$

$$A(x) = \frac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots + x^n$$

$$f(0) = 1$$

$$f'(x) = \frac{0 – (-1)}{(1-x)^2} = \frac{1}{(1-x)^2}$$

$$f^{(2)}(x) = \frac{0 – 2 \times (1 – x)}{(1-x)^4} = \frac{2}{(1-x)^3}$$

$$f^{(n)}(x) = \frac{0 – n! \times (1-x)}{(1-x)^{2n}} = \frac{n!}{(1-x)^n}$$

## 一般生成函数 OGF

### 定义

$$A(x) = \sum_{n=0}^{\infty}a_n x^n$$

### 运算

#### 加减运算

$$F(x) \pm G(x) = \sum_{i=0}^{\infty} (f_i \pm g_i) [x^i]$$

#### 放缩

$$cF(x) = \sum_{i=0}^{\infty} cf_i [x^i]$$

#### 乘法

$$F(x) G(x) = \sum_{k=0}^{\infty} \sum_{i=0}^k f_i g_{k-i} [x^k]$$

#### 求导

$$F'(x) = \sum_{k=0}^{\infty} (k+1) f_{k+1} [x^n]$$

#### 积分

$$\int_0^x F(t) \mathrm{d}t = \sum_{k=0}^{\infty} [k > 0] \frac{f_{k-1}}{k} [x^k]$$

#### 右移

$$x^m F(x) = \sum_{k=0}^{\infty} [k \geq m] f_{k-m} [x^k]$$

#### 左移

$$\frac{F(x) – \sum_{k=0}^{m-1} f_k [x^k]}{x^m} = \sum_{k=0}^{\infty} f_{k+m} [x^k]$$

### 常用形式

$$[1, 1, 1, 1, \cdots] \Leftrightarrow \frac{1}{1-x} \\$$

$$[1, 2, 3, 4, \cdots] \Leftrightarrow \frac{1}{(1-x)^2}$$

$$\sum_{k=0}^{\infty} \sum_{i=0}^k 1 [x^k] = \sum_{k=0}^{\infty} k [x^k]$$

$$[1, -1, 1, -1, \cdots] \Leftrightarrow \frac{1}{1+x}$$

$$[1, a, a^2, a^3 \cdots] \Leftrightarrow \frac{1}{1-ax}$$

$$F(cx) = \sum_{k=0}^{\infty} c^k f_k [x^k]$$

$$\frac{1}{(1-x)^m}$$

$$\frac{1}{(1-x)^m} = \prod_{i=1}^m \frac{1}{1-x} = (1 + x + x^2 + \cdots + x^n)^m$$

$$f_1 + f_2 + f_3 + \cdots +f_m = k$$

$$\frac{1}{(1-x)^m} = \sum_{k=0}^n {m+k-1 \choose m-1} [x^k]$$

$$(1-x)^{-m}$$

$$\frac{1}{(1-ax)^m} = \sum_{k=0}^n a^k {m + k – 1 \choose m – 1} [x^k]$$

## 指数生成函数 EGF

### 定义

$$A(x) = \sum_{n=0}^{\infty} \frac{a_n}{n!} x^n$$

### 运算

#### 加法

$$F(x) \pm G(x) = \sum_{k=0}^{\infty} (f_i \pm g_i) \left[ \frac{x^k}{k!} \right]$$

#### 放缩

$$cF(x) = \sum_{k=0}^{\infty} cf_i \left[ \frac{x^k}{k!} \right]$$

#### 乘法

\begin{aligned} F(x)G(x) & = \sum_{k=0}^{\infty} \sum_{i=0}^k \left( \frac{f_i}{i!} \times \frac{g_{k-i}}{(k-i)!} \right) [x^k] \\ & = \sum_{k=0}^{\infty} \sum_{i=0}^k \left( \frac{f_i}{i!} \times \frac{g_{k-i}}{(k-i)!} \times k!\right) \left[\frac{x^k}{k!} \right] \\ & = \sum_{k=0}^{\infty} \sum_{i=0}^k \left( f_i \times g_{k-i} \times \frac{k!}{i!(k-i)!}\right) \left[ \frac{x^k}{k!} \right] \\ & = \sum_{k=0}^{\infty} \sum_{i=0}^k \left( f_i \times g_{k-i} \times {k \choose i}\right) \left[ \frac{x^k}{k!} \right] \end{aligned}

#### 求导

$$F'(x) = \sum_{k=0}^{\infty} f_{k+1} \left[ \frac{x^k}{k!} \right]$$

#### 积分

$$\int_0^x F(t) \mathrm{d}t = \sum_{k=0}^{\infty} [k > 0] f_{k-1} \left[ \frac{x^k}{k!} \right]$$

### 常用形式

$$[1, 1, 1, 1, \cdots] \Leftrightarrow e^x$$

\begin{aligned} F(x) & = 1 + \frac{1}{1!} x + \frac{1}{2!} x^2 + \cdots + \frac{1}{n!} x^n \\ & = 1 + 1 \left[ \frac{x}{1!} \right] + 1 \left[ \frac{x^2}{2!} \right] + \cdots + 1 \left[ \frac{x^n}{n!} \right] \end{aligned}

$$[1, -1, 1, -1, \cdots] \Leftrightarrow e^{-x}$$

$$[1, 0, 1, 0, \cdots] \Leftrightarrow \frac{e^x + e^{-x}}{2}$$

$$[0, 1, 0, 1, \cdots] \Leftrightarrow \frac{e^x – e^{-x}}{2}$$