斯特林数

第二类斯特林数(斯特林子集数)

定义

\(S_2(n,k)=\begin{Bmatrix}n\\k\end{Bmatrix}\)

表示将 \(n\) 个不同的元素，划分为 \(k\) 个不区分的集合(不允许空集)的方案数。

递推公式

组合意义

插入一个新元素时，有两种方案：

① 将新元素单独放入一个子集，有 \(S_2(n-1,k-1)\) 种。

② 将新元素放入已有的 \(k\) 个子集，有 \(k*S_2(n-1,k)\) 种。

推论

令 \(G_i\) 为将 \(n\) 个不同的元素，划分到 \(i\) 个不同的集合(允许空集)内，\(F_i\) 为将 \(n\) 个不同的元素，划分到 \(i\) 个不同的集合(不允许空集) 。

则有 \(G_i=i^n\)，显然有 \(G_i=\sum_{j=0}^iC_i^j*F_j\)

根据二项式反演有

因为 \(F_i\) 与 \(S_2(n,i)\) 的区别在于，\(F_i\) 是有序的，所以 \(F_i=S_2(n,i)*i!\)

所以

同一行

1
2
3
4

{ 多项式基础模版 }
int n;
cin >> n;
cout << other::Stirling2Row(n) << "\n";

同一列

1
2
3
4

{ 多项式基础模版 }
int n, k;
cin >> n >> k;
cout << other::Stirling2Col(n, k);

第一类斯特林数(斯特林轮换数)

定义

\(S_1(n,k)=\begin{bmatrix}n\\k\end{bmatrix}\)

表示将 \(n\) 个两两不同的元素，划分为 \(k\) 个不区分的轮换(非空)的方案数。

递推公式

组合意义

插入一个新元素时，有两种方案：

① 将新元素置于一个单独的轮换中，共有 \(S_1(n-1,k-1)\) 种。

② 将新元素放入已有的轮换中的任意一个位置，共有 \((n-1)*S_1(n-1,k)\) 种。

同一行

1
2
3
4

{ 多项式基础模版 }
int n;
cin >> n;
cout << other::Stirling1Row(n) << "\n";

同一列

1
2
3
4

{ 多项式基础模版 }
int n, k;
cin >> n >> k;
cout << other::Stirling1Col(n, k);

上升幂与普通幂的相互转化

下降幂与普通幂的互相转化

性质