讨论详情 - Sanhai

数学
常用生成函数及其泰勒展开
Sam SU @ 2026-7-4 18:04:10

普通型 OGF

闭形式	泰勒展开 (形式幂级数)	系数 / 含义
$\dfrac{1}{1-x}$	$\sum_{n=0}^{\infty}x^n$	$a_n=1$
$\dfrac{x}{1-x}$	$\sum_{n=1}^{\infty}x^n$	上式再乘一个 $x$
$\dfrac{1}{1-x^6}$	$1+x^6+x^{12}+\cdots$	令 $x=x^3$
$\dfrac{1-x^6}{1-x}$	$1+x+x^2+x^3+x^4+x^5$
$\dfrac{1}{1-ax}$	$\sum_{n=0}^{\infty}a_nx^n$	等比数列
$\dfrac{1}{(1-x)^k}$	$\sum_{n=0}^{\infty}\binom{n+k-1}{k-1}x^n$	广义二项式定理， $n$ 个球放入 $k$ 个盒子方案数
$\dfrac{x}{(1-x)^2}$	$\sum_{n=1}^{\infty}n\cdot x^n$
$\dfrac{x(x+1)}{(1-x)^3}$	$\sum_{n=1}^{\infty}n^2\cdot x^n$
$(1+x)^n$	$\sum_{i=0}^n\binom{n}{i}x^i$	二项式系数（有限项）
$(1−x)^{\alpha}$	$\sum_{n=0}^{\infty}(-1)^n\binom{\alpha}{n}x^n$	广义二项式系数
$\dfrac{x}{1-x-x^2}$	$\sum_{n=0}^{\infty}F_nx^n$ （其中 $F0=0$ ， $F1=1$ ）	斐波那契数列
$\dfrac{1}{\sqrt{1-4x}}$	$\sum_{n=0}^{\infty}\binom{2n}{n}x^n$	中心二项式系数
$\dfrac{1-\sqrt{1-4x}}{2x}$	$\sum_{n=0}^{\infty}\frac{1}{n+1}\binom{2n}{n}x^n$	卡特兰数
$\sqrt{1-4x}$	$1-2\sum_{n=1}^{\infty}\frac{1}{n}\binom{2n-2}{n-1}x^n$	展开后代入卡特兰数公式
$\prod_{i=1}^{\infty}\dfrac{1}{1-x^i}$	$\sum_{n=0}^{\infty}p(n)x^n$	分拆数（利用五边形数定理递推）
$\prod_{i=1}^{\infty}(1-x^i)$	$1+\sum_{k=1}^{\infty}(-1)^k(x^{\frac{k(3k-1)}{2}}+x^{\frac{k(3k+1)}{2}})$	欧拉五边形数定理
$\dfrac{x^k}{\prod_{i=1}^k(1-ix)}$	$\sum_{n=k}^{\infty}S(n,k)x^n$	第二类斯特林数 OGF

指数型 EGF

闭形式	泰勒展开 (形式幂级数)	系数 / 含义
$e^x$	$\sum_{n=0}^{\infty}\dfrac{x^n}{n!}$	$a_n=1$
$e^{ax}$	$\sum_{n=0}^{\infty}\dfrac{a^nx^n}{n!}$	带权排列
$\dfrac{1}{1-x}$	$\sum_{n=0}^{\infty}n!\cdot\dfrac{x^n}{n!}$	$a_n=n!$ （排列数）
$−ln⁡(1−x)$	$\sum_{n=1}^{\infty}\dfrac{x^n}{n}$ 或 $\sum_{n=1}^{\infty}(n-1)!\cdot\dfrac{x^n}{n!}$	循环排列数 $(n−1)!$
$\dfrac{e^{-x}}{1-x}$	$\sum_{n=0}^{\infty}D_n\dfrac{x^n}{n!}$ ， $D_n=n!\sum_{i=0}^n\dfrac{(-1)^i}{i!}$	错排数
$e^{e^x-1}$	$\sum_{n=0}^{\infty}B_n\dfrac{x^n}{n!}$	贝尔数
$\dfrac{1}{2-e^x}$	$\sum_{n=0}^{\infty}F_n^*\dfrac{x^n}{n!}$	有序贝尔数（偏好排列数）
$\dfrac{(e^x-1)^k}{k!}$	$\sum_{n=k}^{\infty}S(n,k)\dfrac{x^n}{n!}$	第二类斯特林数（固定 $k$ ）
$\dfrac{(-ln(1-x))^k}{k!}$	$\sum_{n=k}^{\infty}\begin{bmatrix} n \\ k \end{bmatrix}\dfrac{x^n}{n!}$	第一类斯特林数（无符号）
$e^{x+\frac{x^2}{2}}$	$\sum_{n=0}^{\infty}I_n\dfrac{x^n}{n!}$	对合排列数（involution）

目前还没有评论...