「BUAA Discrete Mathematics Chapter8」特殊计数数列

Part 0

Part 1 Catalan数

定义

Catalan数列是序列

$$C_{0}, C_1, C_2, \cdots , C_n, \cdots$$

其中

$$C_{n} = \frac{1}{n+1}\tbinom{2n}{n} \quad (n = 0, 1, 2, \cdots )$$

是第 $ n $ 个Catalan数。

Part2 差分序列和Stirling数

定理 8.2.1

设序列的通项是 $ n $ 的 $ p $ 次多项式，即：

$$h_n = a_pn^p + a_{p - 1}n^{p - 1} + \cdots + a_1n + a_0$$

则对所有的 $ n \ge 0 $ ， $ \Delta ^ {p + 1} h_n = 0 $

定理 8.2.2

定理 8.2.3

定理 8.2.4

定理 8.2.5

第二类Stirling数 $ S(p, k) $

定理 8.2.6

对每一个满足 $ 0 \le k \le p $ 的整数 $ k $ ，都有：

$$S^{ \# }(p,k) = \sum_{t = 0}^{k}(-1)^{t}$$

定理 8.2.7 （Bell数的递推式）

如果 $ p \ge 1 $ ，则：

$$B_p = \tbinom{p - 1}{0}B_0 + \tbinom{p - 1}{1} B_1 + \cdots + \tbinom{p - 1}{p - 1} B_{p - 1}$$

Bell数 $ B_p $ 给出了将 $ p $ 元素集合分到非空且不可区分盒子的划分数，注意这里没有指定盒子个数。

第一类Stirling数

定理 8.2.8

第一类Stirling数 $ s(p,k) = (p - 1)s(p - 1, k) +

---

• ← Previous Post
• Next Post →

---