标签：begin end 斯特林 元素 Bmatrix 集合

斯特林数

这一部分是我在阅读《具体数学》时做的一些类似于摘抄的东西。

不过补上了很多没有给出的证明。

第二类斯特林数

我们记 \(\begin{Bmatrix}n\\k\end{Bmatrix}\) 表示把 \(n\) 个物品分为 \(k\) 个非空集合的方案数，读作“\(n\) 集合 \(k\)”。称为“第二类斯特林数”或“斯特林集合数”。

我们从一些基础的情况出发：

1. \(\begin{Bmatrix}n\\1\end{Bmatrix} = 1\)：把 \(n\) 个元素全部归为 \(1\) 个集合。

2. \(\begin{Bmatrix}n\\n\end{Bmatrix} = 1\)：把 \(n\) 个元素各成一个集合。

3. \(\begin{Bmatrix}n\\0\end{Bmatrix} = [n = 0]\)。

4. \(\begin{Bmatrix}n\\k\end{Bmatrix} = 0(n < k)\)。

接下来从组合意义上考虑它的归纳式：

我们新加入第 \(n\) 个元素，最后得到了 \(k\) 个非空集合。考虑如何操作第 \(n\) 个元素：

1. 放到一个新的集合中，则原来有 \(k-1\) 个集合，\(\begin{Bmatrix}n\\k\end{Bmatrix} \gets \begin{Bmatrix}n-1\\k-1\end{Bmatrix}\)；

2. 放入原来的任一个集合中，则原来有 \(k\) 个集合，并且第 \(n\) 个元素有 \(k\) 个不同的集合可供选择，\(\begin{Bmatrix}n\\k\end{Bmatrix} \gets k\begin{Bmatrix}n-1\\k\end{Bmatrix}\)。

因此有：

\[\begin{Bmatrix}n\\k\end{Bmatrix} = k\begin{Bmatrix}n-1\\k\end{Bmatrix}+\begin{Bmatrix}n-1\\k-1\end{Bmatrix} \tag{1.1} \]

得到第二类斯特林数表：

\(n\)	\(\begin{Bmatrix}n\\0\end{Bmatrix}\)	\(\begin{Bmatrix}n\\1\end{Bmatrix}\)	\(\begin{Bmatrix}n\\2\end{Bmatrix}\)	\(\begin{Bmatrix}n\\3\end{Bmatrix}\)	\(\begin{Bmatrix}n\\4\end{Bmatrix}\)	\(\begin{Bmatrix}n\\5\end{Bmatrix}\)	\(\begin{Bmatrix}n\\6\end{Bmatrix}\)
\(0\)	\(1\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)
\(1\)	\(0\)	\(1\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)
\(2\)	\(0\)	\(1\)	\(1\)	\(0\)	\(0\)	\(0\)	\(0\)
\(3\)	\(0\)	\(1\)	\(3\)	\(1\)	\(0\)	\(0\)	\(0\)
\(4\)	\(0\)	\(1\)	\(7\)	\(6\)	\(1\)	\(0\)	\(0\)
\(5\)	\(0\)	\(1\)	\(15\)	\(25\)	\(10\)	\(1\)	\(0\)
\(6\)	\(0\)	\(1\)	\(31\)	\(90\)	\(65\)	\(15\)	\(1\)

标签：begin,end,斯特林,元素,Bmatrix,集合
From： https://www.cnblogs.com/bikuhiku/p/stirling_numbers.html