【斯特林數總結】
第二類斯特林數
組合意義：
將n個有標號物品劃分為m個無標號的非空集合的方案數，記為\(n\brace m\)
遞推式
\[\begin{aligned}{0 \brace 0}&=1\\
{n \brace 0}&=0 \quad(n>0)\\
{n \brace m}&={n-1 \brace m-1}+m{n-1 \brace m}\quad(n,m>0)
\end{aligned}
\]
常用公式
考慮一個組合問題：把n個有標號球任意放入m個有標號盒子，求方案數
根據乘法原理依次考慮每個球放入第幾個盒子，方案數即為：
\(m^n\)
我們還可以枚舉放幾個盒子，得到
\(\sum\limits_{i=0}^m\dbinom{m}{i}i!\begin{Bmatrix}n\\i\end{Bmatrix}\)
所以
\(m^n=\sum\limits_{i=0}^m\dbinom{m}{i}i!\begin{Bmatrix}n\\i\end{Bmatrix}\)
利用這個式子可以解決形如
\[https://www.luogu.com.cn/problem/CF932E
\]
浙公網安備 33010602011771號