常见数列 全0 斐波那契数列： 错排 卡特兰数： 第一类斯特林数 第二类斯特林数 贝尔数 调和级数
[F_i = 0
]
斐波那契数列：
[F_n = F_{n - 1} + F_{n - 2}, F_1 = F_2 = 1
]
错排
递推式：
[D_n = (n - 1) (D_{n - 1} + D{n - 2})
]
考虑最后一个元素插入即可
通项式：
[D_n = n! sum_{i = 0}^{n}(-1)^i frac 1 {i!}
]
带入：
设
[M_i = frac 1 {i!} D_i
]
[i!M_i = (i - 1) ((i - 1)!M_{i - 1} + (i -2)!M_{i - 2})
]
[i M_i = (i - 1)M_{i - 1} + M_{i - 2} = i*M_{i - 1} - M_{i - 1} + M_{i - 2}
]
[i(M_i - M_{i - 1}) = -(M_{i -1} - M_{i - 2})
]
[(i - 1)(M_{i - 1} - M_{i - 2}) = -(M_{i - 2} - M_{i - 3})
]
[(M_i - M_{i - 1}) = (-1) ^ i frac 1 {i!}
]
[M_n = sum_{i = 0} ^ n (-1)^i frac 1 {i!}
]
带回得出
容斥：
设 (i) 个位置的数相同
[D_i = sum_{i = 0} ^ n (-1)^i inom n i (n - i)!
]
[= sum_{i = 0} ^ n (-1) ^ i frac {n !} {i! (n - i)!} (n - i)!
]
[= n! sum_{i = 0} ^ n (-1) ^ i frac 1 {i!}
]
卡特兰数：
[C_0 = 1
]
递推式：
[C_n = sum_{i = 0}^{n - 1} C_i C_{n - 1 - i}
]
新括号 -> $ () $ 旧括号 -> $ |$
[| ( ( ) ) | ( ) ( )
]
通项式：
[C_n = inom {2n} {n} - inom {2n} {n + 1}
]
画图理解。。。
第一类斯特林数
(n) 个相同元素放到 (m) 个非空环上
递推式：
[egin{bmatrix} n \ m end{bmatrix} = egin{bmatrix} n - 1 \ m - 1end{bmatrix} + (n - 1)egin{bmatrix} n - 1 \ mend{bmatrix}
]
考虑第 (n) 个元素, 可以新占一个环，也可以加入一个环
如果是加入环，放的位置只和它的前驱有关，一共有 ((n - 1)) 个前驱
第二类斯特林数
(n) 个相同元素放到 (m) 个非空集合中
[egin{Bmatrix} n \ m end{Bmatrix} = egin{Bmatrix} n - 1 \ m - 1 end{Bmatrix} + m egin{Bmatrix} n - 1 \ m end{Bmatrix}
]
考虑第 (n) 个元素, 可以新占一个集合，也可以加入一个集合
如果是加入集合，放的位置只和它的集合是谁有关，一共有 (m) 个集合
通项：
考虑对集合容斥
先将所有集合标号
(i) 表示选 (i) 个空集合
[egin{Bmatrix} n \ m end{Bmatrix} = frac 1 {m!}sum_{i = 0} ^ m (-1)^i inom m i (m - i) ^n
]
$ dfrac 1 {m!} $ 抵消掉标号的影响
贝尔数
[B_0 = 1
]
(n) 个元素分入若干个非空集合的方案数
[B_n = sum_{i = 0}^n egin{Bmatrix} n \ i end{Bmatrix}
]
递推式：
考虑第 ((n + 1)) 个元素的所在集合大小为 (k + 1)（算上自己）
[B_{n + 1} = sum_{k = 0}^n inom n {n - k} B_{n - k} = sum_{k = 0}^n inom n k B_k
]
调和级数
[H_n = sum _{i = 1} ^ n frac n i = ln~n + O
]
(O) 为常数