【Algo】常见组合类数列

常见组合类数列

介绍一些常见具有明显数学规律或递推关系的常见组合类数列。

---

1 常见递推/组合类数列

1.1 基础递推类数列

1. Fibonacci 数列
   F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1

   • 应用：动态规划、斐波那契堆、黄金分割、兔子繁殖问题

2. Lucas 数列
   L(n) = L(n-1) + L(n-2), L(0)=2, L(1)=1

   • 与 Fibonacci 类似，但初始值不同

3. Tribonacci 数列
   T(n) = T(n-1) + T(n-2) + T(n-3)

   • 拓展了 Fibonacci，为三项递推

4. Padovan 数列
   P(n) = P(n-2) + P(n-3)

   • 初始值：P(0)=P(1)=P(2)=1

5. Pell 数列
   P(n) = 2*P(n-1) + P(n-2), P(0)=0, P(1)=1

6. Jacobsthal 数列
   J(n) = J(n-1) + 2*J(n-2), J(0)=0, J(1)=1

7. Tetranacci 数列
   T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4)

---

1.2 组合数学数列

1. Catalan 数列
   C(n) = (2n)! / ((n+1)! * n!)

   • 应用：二叉树计数、括号匹配、堆叠问题等

2. Bell 数列
   B(n) 表示将 n 个元素划分为若干非空子集的方法数

   • 应用：集合划分

3. Stirling 数列（第一类 & 第二类）

   • 第一类：排列圈数计数
   • 第二类：子集划分计数

4. Motzkin 数列
   M(n) = M(n-1) + sum_{k=0}^{n-2} M(k)*M(n-2-k)

   • 应用：无交叉弦结构、路径问题

5. Schröder 数列（小 & 大）

   • 应用：路径计数、括号问题扩展

6. Narayana 数列

   • 与 Catalan 有关，用于细分结构计数

---

1.3 数论/函数类数列

1. Pascal 三角形（二项式系数）
   C(n, k) = n! / (k!(n-k)!)

   • 应用：组合数、概率

2. 阶乘数列
   n! = n * (n-1)!

3. 超级阶乘（Hyperfactorial）
   H(n) = 1^1 * 2^2 * 3^3 * ... * n^n

4. 调和数列
   H(n) = 1 + 1/2 + 1/3 + ... + 1/n

5. 素数数列

   • 应用：加密、筛法（如埃拉托色尼筛）

6. 欧拉数（Eulerian Numbers）

   • 计数排列中特定升序数对的数量

7. 伯努利数（Bernoulli Numbers）

   • 应用：泰勒展开、高阶导数公式等

8. 高斯整数模/黎曼函数相关数列

---

1.4 图论/路径问题相关数列

1. Dyck 路数列（等价于 Catalan）

2. Lattice Path 数列（格点路径）
   C(n + m, n)：从 (0, 0) 到 (n, m) 的路径数

3. Delannoy 数列

   • 每步可以右、上或斜上走

4. Manhattan 路径数

---

1.5 算法和结构设计常用数列

1. Heap 树结构排列数（Catalan 相关）

2. AVL 树高度组合（与 Fibonacci 相关）

3. 哈夫曼编码树结构计数

---

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  
    

3 参考建议

• 可查阅 OEIS（Online Encyclopedia of Integer Sequences）

• 常见序列编号：

  • Fibonacci: A000045
  • Catalan: A000108
  • Bell: A000110
  • Motzkin: A001006