斯特林数

斯特林数相关。

斯特林(Stirling)数

第一类斯特林数

默认为无符号。有符号有系数 $(-1) ^ {n - k}$ 。

• 定义：将 $1 \ldots n$ 划分为 $k$ 个圆排列的方案数。
• 记作 $s(n, k)$ 或 ${n \brack k}$ 。
• 求法：${n \brack k} = {n - 1 \brack k - 1}+(n - 1) {n - 1 \brack k}$ 。 $n$ 可以划入一个新的圆中，即 ${n - 1 \brack k - 1}$ ；也可以划入之前任意一个元素后，即 ${n - 1 \brack k - 1}+(n - 1) {n - 1 \brack k}$ 。
• 性质：
  • ${0 \brack 0} = 1$ ；
  • ${n \brack 0} = 0$ ；
  • ${n \brack n} = 1$ ；
  • ${n \brack 1} = (n - 1)!$ ；
  • ${n \brack n - 1} = \binom n 2$ ；
  • ${n \brack 2} = (n - 1)! \sum _ {i = 1} ^ {n - 1} \frac 1 i$ ；
  • ${n \brack n - 2} = 2 \binom n 3 + 3 \binom n 4$ ；
  • $\displaystyle \sum _ {k = 0} ^ n {n \brack k} = n!$ ；
  • $k ^ {\overline n} = \sum _ {i = 0} ^ n {n \brack i} k ^ i$；
  • $k ^ {\underline n} = \sum _ {i = 0} ^ n (-1) ^ {n - i} {n \brack i} k ^ i$ 。

第二类斯特林数

• 定义：将 $1\ldots n$ 划分为 $k$ 个相同集合的方案数。
• 记作 $S(n, k)$ 或 $n \brace k$ 。
• 求法：${n \brace k} = {n - 1 \brace k - 1} + k {n - 1 \brace k}$。 $n$ 可以放入一个新的集合中，即 $n - 1 \brace k - 1$ ；也可以划入之前的集合中，即 $k {n - 1 \brace k}$ 。
• 性质：
  • ${n \brace 0} = 0 ^ n$ ；
  • ${n \brace 1} = 1$ ；
  • ${n \brace n} = 1$ ；
  • ${n \brace 2} = 2 ^{n - 1} - 1$ ；
  • ${n \brace n - 1} = \binom n 2$ ；
  • ${n \brace n - 2} = {\binom n 3} + 3 {\binom n 4} $；
  • ${n \brace 3} = \frac 1 2 (3 ^{n - 1} +1) - 2 ^{n - 1}$ ；
  • ${n \brace n - 3} = {\binom n 4} +10 {\binom n 5} +15 {\binom n 6}$ ；
  • $m ^ n = \displaystyle \sum _ {i = 1} ^ m{ n \brace i} \binom m i i!$ ；
  • $k ^ n = \sum _ {i = 0} ^ n {n \brace i} (-1) ^ {n - i} k ^ {\overline i}$ ；
  • $k ^ n = \sum _ {i = 0} ^ n {n \brace i} k ^ {\underline i}$。
• 通项公式：${n \brace k} = \sum _ {i = 0} ^ k \frac {(-1) ^ {k - i} i ^ n}{i! (k - i)!}$ 。

斯特林反演

$$
F(n) = \sum _ {i = 0} ^ n {n \brace i} G(i) \Longleftrightarrow G(n) = \sum _ {i = 0} ^ n (-1) ^ {n - i} {n \brack i} F(i) \tag 1
$$

$$
F(n) = \sum _ {i = 0} ^ n (-1) ^ {n - i} {n \brace i} G(i) \Longleftrightarrow G(n) = \sum _ {i = 0} ^ n {n \brack i}F(i) \tag 2
$$

$$
F(n) = \sum _ {i = n} {i \brace n} G(i) \Longleftrightarrow G(n) = \sum _ {i = n} (-1) ^ {i - n} {i \brack n} F(i) \tag 3
$$

$$
F(n) = \sum _ {i = n} (-1) ^ {i - n} {i \brace n} G(i) \Longleftrightarrow G(n) = \sum _ {i = n} {i \brack n}F(i) \tag 4
$$