发布时间：2024-09-27

斯特林数

第一类string数

将1-n划分成k个圆排列的方案数，记作 $s[n,k]或[\frac{n}{k}]$

递归求法：

• n放到新的圆，$[\frac{n-1}{k-1}]$
• n放到已有的圆，$(n-1)[\frac{n-1}{k}]$

第一类string数性质

• $s(0,0)=1,s(n,0)=0,s(n,n)=1$
• $s(n,1)=(n-1)!$
• $s(n,n-1)=C_n^2$，只有一个环有2个元素
• $s(n,2)=(n-1)! \cdot \sum_{i=1}^{n-1}\frac{1}{i}$
• $s(n,n-2)=2 \cdot C_n^3+3 \cdot C_n^4$
• $\sum_{k=0}^ns(n,k)=n!$