組合基礎2 第一類斯特林數 第二類斯特林數 基礎部分

記 x n ‾ = x ( x + 1 ) ( x + 2 ) ⋯ ( x + n − 1 ) x^{\overline{n}}=x(x+1)(x+2)\cdots(x+n-1) xn=x(x+1)(x+2)⋯(x+n−1)， x n ‾ = x ( x − 1 ) ( x − 2 ) ⋯ ( x − n + 1 ) x^{\underline{n}}=x(x-1)(x-2)\cdots(x-n+1) xn​=x(x−1)(x−2)⋯(x−n+1)。

第一類斯特林數

定義為 x n ‾ x^{\overline{n}} xn的 m m m次項系數，即 x n ‾ = ∑ i = 0 n [ n i ] x i x^{\overline{n}}=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i xn=∑i=0n​[ni​]xi。組合意義為将 n n n個數分為 m m m個無差別環的方案數。

可在 O ( n log ⁡ n ) O(n\log n) O(nlogn)内求 [ n i ] \begin{bmatrix}n\\i\end{bmatrix} [ni​]。

第二類斯特林數

組合意義為将 n n n個數分為 m m m個無差別組的方案數。定義為 x n = ∑ i = 0 n { n i } x i ‾ x^n=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline{i}} xn=∑i=0n​{ni​}xi​。

可以用容斥原理求斯特林數，枚舉幾個組為空即可。公式為 { n m } = 1 m ! ∑ i = 0 m ( − 1 ) i ( m i ) ( m − i ) n \begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^m(-1)^i\binom{m}{i}(m-i)^n {nm​}=m!1​i=0∑m​(−1)i(im​)(m−i)n容斥求出的組有差別，是以要除以階乘。

枚舉最後一個組含除了最後一個元素還有哪些元素，有公式 { n m } = ∑ i = 1 n − 1 ( n − 1 i − 1 ) { n − i m − 1 } \begin{Bmatrix}n\\m\end{Bmatrix}=\sum_{i=1}^{n-1}\binom{n-1}{i-1}\begin{Bmatrix}n-i\\m-1\end{Bmatrix} {nm​}=i=1∑n−1​(i−1n−1​){n−im−1​}

幂的轉換

由各種方法可得：

x n = ∑ i = 0 n { n i } x i ‾ ( − 1 ) n − i x^n=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}x^{\overline{i}}(-1)^{n-i} xn=i=0∑n​{ni​}xi(−1)n−i x n ‾ = ∑ i = 0 n [ n i ] x i ( − 1 ) n − i x^{\underline{n}}=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i(-1)^{n-i} xn​=i=0∑n​[ni​]xi(−1)n−i

以上兩個定義式和兩個幂的轉換公式可簡記為正降卷升，一歸二歧（“正”指挨個乘）。

把兩個式子拼起來可得斯特林反演。把一個式子帶到另一個裡去可得翻轉公式。口訣：正卷互推，減（卷）接等真。

*2018.12

練習題

幂和

∑ i = 1 n i k = ∑ i = 1 n ∑ j = 0 k { k j } i j ‾ = ∑ j = 0 k { k j } ∑ i = 1 n i j ‾ = ∑ j = 0 k { k j } j ! ∑ i = 1 n ( i j ) = ∑ j = 0 k { k j } j ! ( n + 1 j + 1 ) \begin{aligned} \sum_{i=1}^n i^k &=\sum_{i=1}^n\sum_{j=0}^k \begin{Bmatrix}k\\j\end{Bmatrix}i^{\underline j}\\ &=\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}\sum_{i=1}^ni^{\underline j}\\ &=\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum_{i=1}^n{i\choose j}\\ &=\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!{n+1\choose j+1}\\ \end{aligned} i=1∑n​ik​=i=1∑n​j=0∑k​{kj​}ij​=j=0∑k​{kj​}i=1∑n​ij​=j=0∑k​{kj​}j!i=1∑n​(ji​)=j=0∑k​{kj​}j!(j+1n+1​)​

合作

∑ i = 1 n ( n i ) i k = ∑ i = 1 n ( n i ) ∑ j = 0 k { k j } i j ‾ = ∑ i = 1 n n ! ( n − i ) ! ∑ j = 0 k { k j } ( i − j ) ! = ∑ j = 0 k { k j } ∑ i = 1 n n ! ( n − i ) ! ( i − j ) ! \begin{aligned} \sum_{i=1}^n\binom{n}{i}i^k &=\sum_{i=1}^n\binom ni\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}i^{\underline j}\\ &=\sum_{i=1}^n\frac{n!}{(n-i)!}\sum_{j=0}^k\frac{\begin{Bmatrix}k\\j\end{Bmatrix}}{(i-j)!}\\ &=\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}\sum_{i=1}^n\frac{n!}{(n-i)!(i-j)!} \end{aligned} i=1∑n​(in​)ik​=i=1∑n​(in​)j=0∑k​{kj​}ij​=i=1∑n​(n−i)!n!​j=0∑k​(i−j)!{kj​}​=j=0∑k​{kj​}i=1∑n​(n−i)!(i−j)!n!​​兩個含 i i i的階乘在下面，考慮一次收倆。

= ∑ j = 0 k { k j } ∑ i = 1 n n ! ⋅ ( n − j ) ! ( n − j ) ! ⋅ ( n − i ) ! ( i − j ) ! = ∑ j = 0 k { k j } n ! ( n − j ) ! ∑ i = 1 n ( n − j n − i ) = ∑ j = 0 k { k j } n ! ( n − j ) ! ⋅ 2 n − j \begin{aligned} &=\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}\sum_{i=1}^n\frac{n!\cdot(n-j)!}{(n-j)!\cdot(n-i)!(i-j)!}\\ &=\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}\frac{n!}{(n-j)!}\sum_{i=1}^n\binom{n-j}{n-i}\\ &=\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}\frac{n!}{(n-j)!}\cdot 2^{n-j} \end{aligned} ​=j=0∑k​{kj​}i=1∑n​(n−j)!⋅(n−i)!(i−j)!n!⋅(n−j)!​=j=0∑k​{kj​}(n−j)!n!​i=1∑n​(n−in−j​)=j=0∑k​{kj​}(n−j)!n!​⋅2n−j​