斯特林，上升幂，下降幂，普通幂的定义
第二类斯特林数
| n | \(n\brace 0\) | \(n\brace 1\) | \(n\brace 2\) | \(n\brace 3\) | \(n\brace 4\) | \(n\brace 5\) | \(n\brace 6\) | \(n\brace 7\) | \(n\brace 8\) | \(n\brace9\) |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| 1 | \(0\) | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| 2 | \(0\) | \(1\) | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| 3 | \(0\) | \(1\) | \(3\) | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| 4 | \(0\) | \(1\) | \(7\) | \(6\) | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| 5 | \(0\) | \(1\) | \(15\) | \(25\) | \(10\) | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) |
| 6 | \(0\) | \(1\) | \(31\) | \(90\) | \(65\) | \(15\) | \(1\) | \(0\) | \(0\) | \(0\) |
| 7 | \(0\) | \(1\) | \(63\) | \(301\) | \(350\) | \(140\) | \(21\) | \(1\) | \(0\) | \(0\) |
| 8 | \(0\) | \(1\) | \(127\) | \(966\) | \(1701\) | \(1050\) | \(266\) | \(28\) | \(1\) | \(0\) |
| 9 | \(0\) | \(1\) | \(255\) | \(3025\) | \(7770\) | \(6951\) | \(2446\) | \(462\) | \(36\) | \(1\) |
定义 \({n\brace m}\) 表示将 \(n\) 件物品分成 \(m\) 个子集（非空）的方案数。
有
\[{n\brace m} = {n-1\brace m-1} + m{n-1\brace m}
\]
第一类斯特林数
| n | \(n\brack 0\) | \(n\brack 1\) | \(n\brack 2\) | \(n\brack 3\) | \(n\brack 4\) | \(n\brack 5\) | \(n\brack 6\) | \(n\brack 7\) | \(n\brack 8\) | \(n\brace9\) |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| 1 | \(0\) | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| 2 | \(0\) | \(1\) | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| 3 | \(0\) | \(2\) | \(3\) | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| 4 | \(0\) | \(6\) | \(11\) | \(6\) | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| 5 | \(0\) | \(24\) | \(50\) | \(35\) | \(10\) | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) |
| 6 | \(0\) | \(120\) | \(274\) | \(225\) | \(85\) | \(15\) | \(1\) | \(0\) | \(0\) | \(0\) |
| 7 | \(0\) | \(720\) | \(1764\) | \(1624\) | \(735\) | \(175\) | \(21\) | \(1\) | \(0\) | \(0\) |
| 8 | \(0\) | \(5040\) | \(13068\) | \(13132\) | \(6769\) | \(1960\) | \(322\) | \(28\) | \(1\) | \(0\) |
| 9 | \(0\) | \(40320\) | \(109584\) | \(11824\) | \(67284\) | \(22449\) | \(4536\) | \(546\) | \(36\) | \(1\) |
定义 \(n\brack m\) 表示将 \(n\) 件物品分成 \(m\) 个轮换（非空，圆排列）的方案数。
有
\[{n\brack m} = (n-1){n-1\brack m}+{n-1\brack m-1}
\]
上升幂，下降幂，普通幂
\[\begin{aligned}
&x^{\underline{n}} = \frac{x!}{(x-n)!}\\
&x^{\overline{n}} = \frac{(x+n-1)!}{(x-1)!}\\
&x^n = x^n\\
&x^{\overline{n}} = (x+n-1)^{\underline{n}}\\
&x^{\underline{n}} = (x-n+1)^{\overline{n}}\\
\end{aligned}
\]
上升幂，下降幂，普通幂的关系
用下降幂表示普通幂
\[\begin{aligned}
\sum_{i=0}^{n}{n\brace i}x^{\underline{i}} &= \sum_{i=0}^{n}(i{n-1\brace i}+{n-1\brace i-1})x^{\underline{i}}\\
&= \sum_{i=0}^{n}i{n-1\brace i}x^{\underline{i}}+\sum_{i=0}^{n}{n-1\brace i-1}x^{\underline{i}}\\
&= \sum_{i=0}^{n}i{n-1\brace i}x^{\underline{i}}+\sum_{i=1}^{n}{n-1\brace i-1}x^{\underline{i}}\\
&= \sum_{i=0}^{n}i{n-1\brace i}x^{\underline{i}}+\sum_{i=1}^{n}{n-1\brace i-1}x^{\underline{(i-1)+1}}\\
&= \sum_{i=0}^{n}i{n-1\brace i}x^{\underline{i}}+\sum_{i=0}^{n-1}{n-1\brace i}x^{\underline{i+1}}\\
&= \sum_{i=0}^{n-1}i{n-1\brace i}x^{\underline{i}}+\sum_{i=0}^{n-1}{n-1\brace i}x^{\underline{i}}(x-i)\\
&= \sum_{i=0}^{n-1}i{n-1\brace i}x^{\underline{i}}+{n-1\brace i}x^{\underline{i}}(x-i)\\
&= x\sum_{i=0}^{n-1}{n-1\brace i}x^{\underline{i}}\\
&= x \times x^{n-1} = x^{n}\\
\end{aligned}
\]
用普通幂表示上升幂
\[\begin{aligned}
\sum_{i=0}^{n}{n\brack i}x^{i} &= \sum_{i=0}^{n}((n-1){n-1\brack i}+{n-1\brack i-1})x^i\\
&= \sum_{i=0}^{n}(n-1){n-1\brack i}x^i+\sum_{i=0}^{n}{n-1\brack i-1}x^i\\
&= \sum_{i=0}^{n}(n-1){n-1\brack i}x^i+\sum_{i=1}^{n}{n-1\brack i-1}x^{(i-1)+1}\\
&= \sum_{i=0}^{n}(n-1){n-1\brack i}x^i+\sum_{i=0}^{n-1}{n-1\brack i}x^{i+1}\\
&= (n-1+x)\sum_{i=0}^{n}{n-1\brack i}x^i\\
&= (x+n-1)x^{\overline{n-1}}\\
&= x^{\overline{n}}\\
\end{aligned}
\]
用普通幂表示下降幂
\[\begin{aligned}
x^{\underline{n}} &= (-1)^n(-x)^{\overline{n}}\\
&= (-1)^n\sum_{i=0}^{n}{n\brack i}(-x)^i\\
&= \sum_{i=0}^{n}{n\brack i}(-1)^{n-i}x^i\\
\end{aligned}
\]
用上升幂表示普通幂
\[\begin{aligned}
x^n &= (-1)^n(-x)^n\\
&= (-1)^n\sum_{i=0}^{n}{n\brace i}(-x)^{\underline{i}}\\
&= (-1)^n\sum_{i=0}^{n}{n\brace i}(-1)^ix^{\underline{i}}\\
&= \sum_{i=0}^{n}{n\brace i}(-1)^{n-i}x^{\underline{i}}\\
\end{aligned}
\]
整理一下
\[\begin{aligned}
&x^n = \sum_{i=0}^{n}{n\brace i}x^{\underline{i}}\\
&x^n = \sum_{i=0}^{n}{n\brace i}(-1)^{n-i}x^{\overline{i}}\\
&x^{\overline{n}} = \sum_{i=0}^{n}{b\brack i}x^i\\
&x^{\underline{n}} = \sum_{i=0}^{n}{n\brack i}(-1)^{n-i}x^i\\
\end{aligned}
\]
表示普通幂时用第二类斯特林数，表示上升幂，下降幂用第一类斯特林数，用大数表示小数时用 \((-1)^{n-i}\)。