文章目录
常见组合类数列
介绍一些常见具有明显数学规律或递推关系的常见组合类数列。
1 常见递推/组合类数列
1.1 基础递推类数列
Fibonacci 数列
F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1- 应用：动态规划、斐波那契堆、黄金分割、兔子繁殖问题
Lucas 数列
L(n) = L(n-1) + L(n-2), L(0)=2, L(1)=1- 与 Fibonacci 类似，但初始值不同
Tribonacci 数列
T(n) = T(n-1) + T(n-2) + T(n-3)- 拓展了 Fibonacci，为三项递推
Padovan 数列
P(n) = P(n-2) + P(n-3)- 初始值：P(0)=P(1)=P(2)=1
Pell 数列
P(n) = 2*P(n-1) + P(n-2), P(0)=0, P(1)=1Jacobsthal 数列
J(n) = J(n-1) + 2*J(n-2), J(0)=0, J(1)=1Tetranacci 数列
T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4)
1.2 组合数学数列
Catalan 数列
C(n) = (2n)! / ((n+1)! * n!)- 应用：二叉树计数、括号匹配、堆叠问题等
Bell 数列
B(n)表示将 n 个元素划分为若干非空子集的方法数- 应用：集合划分
Stirling 数列（第一类 & 第二类）
- 第一类：排列圈数计数
- 第二类：子集划分计数
Motzkin 数列
M(n) = M(n-1) + sum_{k=0}^{n-2} M(k)*M(n-2-k)- 应用：无交叉弦结构、路径问题
Schröder 数列（小 & 大）
- 应用：路径计数、括号问题扩展
Narayana 数列
- 与 Catalan 有关，用于细分结构计数
1.3 数论/函数类数列
Pascal 三角形（二项式系数）
C(n, k) = n! / (k!(n-k)!)- 应用：组合数、概率
阶乘数列
n! = n * (n-1)!超级阶乘（Hyperfactorial）
H(n) = 1^1 * 2^2 * 3^3 * ... * n^n调和数列
H(n) = 1 + 1/2 + 1/3 + ... + 1/n素数数列
- 应用：加密、筛法（如埃拉托色尼筛）
欧拉数（Eulerian Numbers）
- 计数排列中特定升序数对的数量
伯努利数（Bernoulli Numbers）
- 应用：泰勒展开、高阶导数公式等
高斯整数模/黎曼函数相关数列
1.4 图论/路径问题相关数列
Dyck 路数列（等价于 Catalan）
Lattice Path 数列（格点路径）
C(n + m, n)：从 (0, 0) 到 (n, m) 的路径数Delannoy 数列
- 每步可以右、上或斜上走
Manhattan 路径数
1.5 算法和结构设计常用数列
Heap 树结构排列数（Catalan 相关）
AVL 树高度组合（与 Fibonacci 相关）
哈夫曼编码树结构计数
2 示例：有规律数列前 10 项对比表
| 序列名 | 定义公式（简写） | 前 10 项数据（从 n = 0 开始） |
|---|---|---|
| Fibonacci | F(n) = F(n-1) + F(n-2) | 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 |
| Lucas | L(n) = L(n-1) + L(n-2), L(0)=2, L(1)=1 | 2, 1, 3, 4, 7, 11, 18, 29, 47, 76 |
| Tribonacci | T(n) = T(n-1) + T(n-2) + T(n-3) | 0, 0, 1, 1, 2, 4, 7, 13, 24, 44 |
| Tetranacci | Sum of last 4 terms | 0, 0, 0, 1, 1, 2, 4, 8, 15, 29 |
| Pell | P(n) = 2·P(n-1) + P(n-2) | 0, 1, 2, 5, 12, 29, 70, 169, 408, 985 |
| Padovan | P(n) = P(n-2) + P(n-3) | 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 |
| Jacobsthal | J(n) = J(n-1) + 2·J(n-2) | 0, 1, 1, 3, 5, 11, 21, 43, 85, 171 |
| Catalan | C(n) = (2n)! / [(n+1)! · n!] | 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862 |
| Bell | B(n): 集合划分数 | 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147 |
| Stirling II | S(n, k): n 元划分为 k 非空子集 | 见注* |
| Motzkin | 路径数计数 | 1, 1, 2, 4, 9, 21, 51, 127, 323, 835 |
| Schröder (小) | 括号路径扩展 | 1, 2, 6, 22, 90, 394, 1806, 8558, 41586, 206098 |
| Narayana | 与 Catalan 相关 | 1, 1, 1, 2, 3, 6, 10, 20, 35, 70 (某列) |
| 阶乘 | n! | 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 |
| 超级阶乘 | ∏(i^i) | 1, 1, 4, 108, 27648, 86400000, … |
| 调和数列 | H(n) = ∑1/k | 0, 1, 1.5, 1.833…, 2.083…, 2.283…, … |
| Delannoy | D(n) = ∑ C(n,k)² | 1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, … |
注解：
Stirling 数（第二类） 通常不是单列，而是二维表格（S(n, k)）。前几行为：
S(0,0)=1 S(1,1)=1 S(2,1)=1, S(2,2)=1 S(3,1)=1, S(3,2)=3, S(3,3)=1