高等组合学笔记(七): Bell数,第一,二类Stirling数及其递推关系

组合学笔记(七): Bell数,第一,二类Stirling数及其递推关系"/>

高等组合学笔记(七): Bell数,第一,二类Stirling数及其递推关系

Bell数

定义4: n n n元集合 N N N 的所有划分数 b ( n ) b(n) b(n), 称为 B e l l Bell Bell数, 即
b ( n ) = ∑ k = 1 n S ( n , k ) , ( n ≥ 1 ) . b(n)=\sum_{k=1}^nS(n,k),\quad(n\geq1). b(n)=k=1∑n​S(n,k),(n≥1).

定理12: B e l l Bell Bell数 b ( n ) b(n) b(n)具有指数生成函数
∑ n ≥ 0 b ( n ) t n n ! = exp ⁡ ( e t − 1 ) , b ( 0 ) = 1. \sum_{n\geq0}b(n)\frac{t^n}{n!}=\exp(e^t-1),\ b(0)=1. n≥0∑​b(n)n!tn​=exp(et−1), b(0)=1.
且满足递推关系
b ( n + 1 ) = ∑ k = 0 n ( n k ) b ( k ) , ( n ≥ 0 ) . b(n+1)=\sum_{k=0}^n\binom{n}k b(k),\ (n\geq0). b(n+1)=k=0∑n​(kn​)b(k), (n≥0).

证明:

由于
Φ ( t , u ) = ∑ n , k ≥ 0 S ( n , k ) t n n ! u k = ∑ k ≥ 0 ( ∑ n ≥ 0 S ( n , k ) t n n ! ) u k = exp ⁡ ( u ( e t − 1 ) ) \Phi(t,u)=\sum_{n,k\geq0}S(n,k)\frac{t^n}{n!}u^k=\sum_{k\geq0}\left(\sum_{n\geq0}S(n,k)\frac{t^n}{n!}\right)u^k=\exp\big(u(e^t-1)\big) Φ(t,u)=n,k≥0∑​S(n,k)n!tn​uk=k≥0∑​(n≥0∑​S(n,k)n!tn​)uk=exp(u(et−1))
所以我们得到:
Φ ( t , 1 ) = ∑ n , k ≥ 0 S ( n , k ) t n n ! = ∑ k = 0 n ( ∑ n ≥ 0 S ( n , k ) t n n ! ) = exp ⁡ ( e t − 1 ) , \Phi(t,1)=\sum_{n,k\geq0}S(n,k)\frac{t^n}{n!}=\sum_{k=0}^n\left(\sum_{n\geq0}S(n,k)\frac{t^n}{n!}\right)=\exp(e^t-1), Φ(t,1)=n,k≥0∑​S(n,k)n!tn​=k=0∑n​(n≥0∑​S(n,k)n!tn​)=exp(et−1),
由指数生成函数
∑ n ≥ 0 b ( n ) t n n ! = exp ⁡ ( e t − 1 ) \sum_{n\geq0}b(n)\frac{t^n}{n!}=\exp(e^t-1) n≥0∑​b(n)n!tn​=exp(et−1)
两边对 t t t求导,得到:
∑ n ≥ 0 b ( n ) t n − 1 ( n − 1 ) ! = exp ⁡ ( e t − 1 ) ⋅ e t , \sum_{n\geq0}b(n)\frac{t^{n-1}}{(n-1)!}=\exp(e^t-1)\cdot e^t, n≥0∑​b(n)(n−1)!tn−1​=exp(et−1)⋅et,
于是
∑ n ≥ 0 b ( n + 1 ) t n n ! = ∑ k ≥ 0 b ( k ) t k k ! ⋅ ∑ j ≥ 0 t j j ! = ∑ k ≥ 0 b ( k ) t k k ! ⋅ ∑ n − k ≥ 0 t n − k ( n − k ) ! , \sum_{n\geq0}b(n+1)\frac{t^{n}}{n!}=\sum_{k\geq0}b(k)\frac{t^k}{k!}\cdot\sum_{j\geq0}\frac{t^j}{j!}=\sum_{k\geq0}b(k)\frac{t^k}{k!}\cdot\sum_{n-k\geq0}\frac{t^{n-k}}{(n-k)!}, n≥0∑​b(n+1)n!tn​=k≥0∑​b(k)k!tk​⋅j≥0∑​j!tj​=k≥0∑​b(k)k!tk​⋅n−k≥0∑​(n−k)!tn−k​,
比较两端 t n n ! \dfrac{t^n}{n!} n!tn​的系数,得到:
b ( n + 1 ) = ∑ k = 0 n ( n k ) b ( k ) , ( n ≥ 0 ) . b(n+1)=\sum_{k=0}^n\binom{n}k b(k),\ (n\geq0). b(n+1)=k=0∑n​(kn​)b(k), (n≥0).

组合解释:
b ( n + 1 ) = ∑ k = 0 n ( n k ) b ( k ) , ( n ≥ 0 ) . b(n+1)=\sum_{k=0}^n\binom{n}k b(k),\ (n\geq0). b(n+1)=k=0∑n​(kn​)b(k), (n≥0).
令 P = { x 1 , x 2 , . . . , x n , x } , N = { x 1 , . . . , x n } P=\{x_1,x_2,...,x_n,{\color{red} x}\}, N=\{x_1,...,x_n\} P={x1​,x2​,...,xn​,x},N={x1​,...,xn​}, b ( n + 1 ) b(n+1) b(n+1)为集合 P P P的所有划分数.

固定 x x x, 将 P P P的所有划分进行分类, 取 K ⊂ N K\subset N K⊂N, ∣ K ∣ = k |K|=k ∣K∣=k, ( 0 ≤ k ≤ n ) (0\leq k \leq n) (0≤k≤n)

{ x } ∪ K \{x\}\cup K {x}∪K作为 P P P的划分中的一块, 其余 N \ K N\backslash K N\K任意划分, 并在一起作为 P P P的划分, 得到
b ( n + 1 ) = ∑ k = 0 n ( n k ) b ( n − k ) = ∑ k = 0 n ( n k ) b ( k ) , ( n ≥ 0 ) . b(n+1)=\sum_{k=0}^n\binom{n}k b(n-k)=\sum_{k=0}^n\binom{n}k b(k),\ (n\geq0). b(n+1)=k=0∑n​(kn​)b(n−k)=k=0∑n​(kn​)b(k), (n≥0).
此外, 我们有:
∑ n ≥ 0 b ( n ) t n n ! = exp ⁡ ( e t − 1 ) = e e t e = 1 e ∑ k ≥ 0 e t k k ! = 1 e ∑ k ≥ 0 1 k ! ∑ n ≥ 0 t n k n n ! , \sum_{n\geq0}b(n)\frac{t^n}{n!}=\exp(e^t-1)=\frac{e^{e^t}}{e}=\frac1e\sum_{k\geq0}\frac{e^{tk}}{k!}=\frac1e\sum_{k\geq0}\frac{1}{k!}\sum_{n\geq0}\frac{t^nk^{n}}{n!}, n≥0∑​b(n)n!tn​=exp(et−1)=eeet​=e1​k≥0∑​k!etk​=e1​k≥0∑​k!1​n≥0∑​n!tnkn​,
两边取 [ t n n ! ] \left[\dfrac{t^n}{n!}\right] [n!tn​], 得到:(Bell数的解析表示)
b ( n ) = 1 e ∑ k ≥ 0 k n k ! . b(n)=\frac1e\sum_{k\geq0}\frac{k^n}{k!}. b(n)=e1​k≥0∑​k!kn​.

定理13: 可以直接计算 B e l l Bell Bell数 b ( n ) b(n) b(n),
b ( n ) = Δ n b ( 1 ) , b ( 1 ) = 1. b(n)=\Delta^nb(1), \ b(1)=1. b(n)=Δnb(1), b(1)=1.

证明:

根据
Δ n b ( m ) = ∑ k = 0 n ( − 1 ) n − k ( n k ) b ( m + k ) , \Delta^nb(m)=\sum_{k=0}^n(-1)^{n-k}\binom nkb(m+k), Δnb(m)=k=0∑n​(−1)n−k(kn​)b(m+k),

令 m = 1 m=1 m=1, 得到:
Δ n b ( 1 ) = ∑ k = 0 n ( − 1 ) n − k ( n k ) b ( 1 + k ) = ∑ k = 0 n ( − 1 ) n − k ( n k ) ∑ i = 0 k ( k i ) b ( i ) = ∑ i = 0 n b ( i ) ∑ k = i n ( − 1 ) n − k ( n k ) ( k i ) = ∑ i = 0 n b ( i ) ( n i ) ∑ k = i n ( − 1 ) n − k ( n − i k − i ) = ∑ i = 0 n b ( i ) ( n i ) ∑ j = 0 n − i ( − 1 ) j ( n − i j ) = ∑ i = 0 n b ( i ) δ n , i = b ( n ) \begin{aligned} \Delta^nb(1)&=\sum_{k=0}^n(-1)^{n-k}\binom nkb(1+k)\\ &=\sum_{k=0}^n(-1)^{n-k}\binom nk\sum_{i=0}^k\binom{k}i b(i)\\ &=\sum_{i=0}^nb(i)\sum_{k=i}^n(-1)^{n-k}\binom nk\binom{k}i \\ &=\sum_{i=0}^nb(i)\binom n{i}\sum_{k=i}^n(-1)^{n-k}\binom{n-i}{k-i} \\ &=\sum_{i=0}^nb(i)\binom n{i}\sum_{j=0}^{n-i}(-1)^{j}\binom{n-i}{j} \\ &=\sum_{i=0}^nb(i)\delta_{n,i}=b(n) \end{aligned} Δnb(1)​=k=0∑n​(−1)n−k(kn​)b(1+k)=k=0∑n​(−1)n−k(kn​)i=0∑k​(ik​)b(i)=i=0∑n​b(i)k=i∑n​(−1)n−k(kn​)(ik​)=i=0∑n​b(i)(in​)k=i∑n​(−1)n−k(k−in−i​)=i=0∑n​b(i)(in​)j=0∑n−i​(−1)j(jn−i​)=i=0∑n​b(i)δn,i​=b(n)​
其中:
δ n , i = { 1 , n = i 0 , n ≠ i \delta_{n,i}=\begin{cases}1,&n=i\\0,&n\ne i\end{cases} δn,i​={1,0,​n=in​=i​
或者直接从差分定义式出发也可证明 ∑ k = i n ( − 1 ) n − k ( n k ) ( k i ) = δ n , i \sum_{k=i}^n(-1)^{n-k}\binom nk\binom{k}i=\delta_{n,i} ∑k=in​(−1)n−k(kn​)(ik​)=δn,i​.

利用差分公式计算Bell数:
Δ n b ( 1 ) = b ( n ) , b ( 1 ) = 1 Δ b ( n ) = b ( n + 1 ) − b ( n ) b ( n + 1 ) = b ( n ) + Δ b ( n ) Δ b ( n + 1 ) = Δ b ( n ) + Δ 2 b ( n ) \begin{aligned} \Delta^nb(1)&=b(n),\ b(1)=1\\ \Delta b(n)&=b(n+1)-b(n)\\ b(n+1)&=b(n)+\Delta b(n)\\ \Delta b(n+1)&=\Delta b(n)+\Delta^2b(n) \end{aligned} Δnb(1)Δb(n)b(n+1)Δb(n+1)​=b(n), b(1)=1=b(n+1)−b(n)=b(n)+Δb(n)=Δb(n)+Δ2b(n)​
绘制一个表格, 利用上述的递推关系即可依次得出, 具体请看A000110 - OEIS.

  11 22 3 55 7 10 1515 20 27 37 52

第二类Stirling数的递推关系式

定理A:
S ( n , k ) = S ( n − 1 , k − 1 ) + k S ( n − 1 , k ) , ( n ≥ k ≥ 1 ) S ( n , 0 ) = S ( 0 , k ) = 0 , ( n , k ≥ 1 ) , S ( 0 , 0 ) = 1. \begin{aligned} S(n,k)&=S(n-1,k-1)+kS(n-1,k), (n\geq k\geq1)\\ S(n,0)&=S(0,k)=0, \ (n,k\geq1),\quad S(0,0)=1. \end{aligned} S(n,k)S(n,0)​=S(n−1,k−1)+kS(n−1,k),(n≥k≥1)=S(0,k)=0, (n,k≥1),S(0,0)=1.​

证明: (分析方法)

根据
∑ k = 0 n S ( n , k ) ( x ) k = x n = x n − 1 ⋅ x , \sum_{k=0}^nS(n,k)(x)_k=x^n=x^{n-1}\cdot x, k=0∑n​S(n,k)(x)k​=xn=xn−1⋅x,
得到:
∑ k = 0 n S ( n , k ) ( x ) k = x ⋅ ∑ k = 0 n − 1 S ( n − 1 , k ) ( x ) k = ∑ k = 0 n − 1 S ( n − 1 , k ) ( x ) k ( ( x − k ) + k ) = ∑ k = 0 n − 1 S ( n − 1 , k ) ( x ) k + 1 + ∑ k = 0 n − 1 k S ( n − 1 , k ) ( x ) k \begin{aligned} \sum_{k=0}^nS(n,k)(x)_k&=x\cdot \sum_{k=0}^{n-1}S(n-1,k)(x)_k\\ &=\sum_{k=0}^{n-1}S(n-1,k)(x)_{k}\big((x-k)+k\big)\\ &=\sum_{k=0}^{n-1}S(n-1,k)(x)_{k+1}+\sum_{k=0}^{n-1}kS(n-1,k)(x)_k \end{aligned} k=0∑n​S(n,k)(x)k​​=x⋅k=0∑n−1​S(n−1,k)(x)k​=k=0∑n−1​S(n−1,k)(x)k​((x−k)+k)=k=0∑n−1​S(n−1,k)(x)k+1​+k=0∑n−1​kS(n−1,k)(x)k​​
比较两端 [ ( x ) k ] [(x)_k] [(x)k​], 即得.

定理B: S ( n , k ) S(n,k) S(n,k)满足"垂直"递推关系(对 n n n计算, k k k不变)

1. S ( n , k ) = ∑ l = k − 1 n − 1 ( n − 1 k ) S ( l , k − 1 ) , S(n,k)=\sum_{l=k-1}^{n-1}\binom{n-1}kS(l,k-1), S(n,k)=l=k−1∑n−1​(kn−1​)S(l,k−1),

2. S ( n , k ) = ∑ l = k n S ( l − 1 , k − 1 ) k n − l . S(n,k)=\sum_{l=k}^nS(l-1, k-1)k^{n-l}. S(n,k)=l=k∑n​S(l−1,k−1)kn−l.

证明:

1.下式
∑ n ≥ 0 S ( n , k ) t n n ! = 1 k ! ( e t − 1 ) k \sum_{n\geq0}S(n,k)\frac{t^n}{n!}=\frac1{k!}(e^t-1)^k n≥0∑​S(n,k)n!tn​=k!1​(et−1)k
两端对 t t t求导, 得到:
∑ n ≥ 1 S ( n , k ) t n − 1 ( n − 1 ) ! = 1 ( k − 1 ) ! ( e t − 1 ) k − 1 e t = e t ∑ l ≥ 0 S ( l , k − 1 ) t l l ! = ∑ m ≥ 0 t m m ! ∑ l ≥ 0 S ( l , k − 1 ) t l l ! ( l e t l + m = n − 1 ) \begin{aligned} \sum_{n\geq1}S(n,k)\frac{t^{n-1}}{(n-1)!}&=\frac1{(k-1)!}(e^t-1)^{k-1}e^t\\ &=e^t\sum_{l\geq0}S(l,k-1)\frac{t^l}{l!}\\ &=\sum_{m\geq0}\frac{t^m}{m!}\sum_{l\geq0}S(l,k-1)\frac{t^l}{l!}\qquad (let\ l+m=n-1) \end{aligned} n≥1∑​S(n,k)(n−1)!tn−1​​=(k−1)!1​(et−1)k−1et=etl≥0∑​S(l,k−1)l!tl​=m≥0∑​m!tm​l≥0∑​S(l,k−1)l!tl​(let l+m=n−1)​
比较两端 [ t m − 1 ( m − 1 ) ! ] \left[\frac{t^{m-1}}{(m-1)!}\right] [(m−1)!tm−1​], 得.

---

2.根据有理生成函数, 得到:
∑ n ≥ 0 S ( n , k ) u n = u k ( 1 − u ) ( 1 − 2 u ) ⋯ ( 1 − k u ) = u 1 − k u ⋅ u k − 1 ( 1 − u ) ( 1 − 2 u ) ⋯ ( 1 − ( k − 1 ) u ) = u 1 − k u ⋅ ∑ l ≥ 0 S ( l , k − 1 ) u l = ∑ m ≥ 0 k m u m + 1 ⋅ ∑ l ≥ 0 S ( l , k − 1 ) u l ( l e t m + l + 1 = n ) \begin{aligned} \sum_{n\geq0}S(n,k)u^n&=\frac{u^k}{(1-u)(1-2u)\cdots(1-ku)}=\frac{u}{1-ku}\cdot\frac{u^{k-1}}{(1-u)(1-2u)\cdots\big(1-(k-1)u\big)}\\ &=\frac{u}{1-ku}\cdot \sum_{l\geq0}S(l,k-1)u^l\\ &=\sum_{m\geq0}k^mu^{m+1}\cdot\sum_{l\geq0}S(l,k-1)u^l\qquad(let\ m+l+1=n) \end{aligned} n≥0∑​S(n,k)un​=(1−u)(1−2u)⋯(1−ku)uk​=1−kuu​⋅(1−u)(1−2u)⋯(1−(k−1)u)uk−1​=1−kuu​⋅l≥0∑​S(l,k−1)ul=m≥0∑​kmum+1⋅l≥0∑​S(l,k−1)ul(let m+l+1=n)​
比较两端 [ u n ] [u^n] [un], 得.

或者从 S ( n , k ) = S ( n − 1 , k − 1 ) + k S ( n − 1 , k ) S(n,k)=S(n-1, k-1)+kS(n-1,k) S(n,k)=S(n−1,k−1)+kS(n−1,k), 一直递归右端第二项得到.

定理C: S ( n , k ) S(n,k) S(n,k)满足"水平"递推关系(对 k k k计算, n n n不变)

1. S ( n , k ) = ∑ j = 0 n − k ( − 1 ) j ⟨ k + 1 ⟩ j S ( n + 1 , k + j + 1 ) , S(n,k)=\sum_{j=0}^{n-k}(-1)^j\langle k+1\rangle_jS(n+1, k+j+1), S(n,k)=j=0∑n−k​(−1)j⟨k+1⟩j​S(n+1,k+j+1),

2. k ! S ( n , k ) = k n − ∑ j = 0 k − 1 ( k ) j S ( n , j ) . k!S(n,k)=k^n-\sum_{j=0}^{k-1}(k)_jS(n,j). k!S(n,k)=kn−j=0∑k−1​(k)j​S(n,j).

证明:

1. S ( n , k ) = S ( n + 1 , k + 1 ) − ( k + 1 ) S ( n , k + 1 ) S(n,k)=S(n+1, k+1)-(k+1)S(n,k+1) S(n,k)=S(n+1,k+1)−(k+1)S(n,k+1)一直递归右端第二项得.
2. 从 k n = ∑ i = 0 k S ( n , i ) ( k ) i = k ! S ( n , k ) + ∑ i = 0 k − 1 ( k ) i S ( n , i ) k^n=\sum_{i=0}^kS(n,i)(k)_i=k!S(n,k)+\sum_{i=0}^{k-1}(k)_iS(n,i) kn=∑i=0k​S(n,i)(k)i​=k!S(n,k)+∑i=0k−1​(k)i​S(n,i), 得.

组合解释:

• k ! S ( n , k ) k!S(n,k) k!S(n,k)表示 n n n个不同的球放入 k k k个不同的盒子, 且每个盒子至少一个球的不同放法数.

• k n k^n kn表示将 n n n个不同的球放入 k k k个不同的盒子, 盒子中球数不限
  k ! S ( n , k ) = k n − 有 空 盒 的 放 法 数 { 1 个 空 盒 : ( k 1 ) ( k − 1 ) ! S ( n , k − 1 ) 2 个 空 盒 : ( k 2 ) ( k − 2 ) ! S ( n , k − 2 ) ⋮ k!S(n,k)=k^n-有空盒的放法数 \begin{cases} 1个空盒:\binom k1(k-1)!S(n,k-1)\\ 2个空盒:\binom k2(k-2)!S(n,k-2)\\ \vdots \end{cases} k!S(n,k)=kn−有空盒的放法数⎩⎪⎪⎨⎪⎪⎧​1个空盒:(1k​)(k−1)!S(n,k−1)2个空盒:(2k​)(k−2)!S(n,k−2)⋮​

定理D: 第二类Stirling数满足"斜"递推关系
S ( n , k ) = δ n , k + ∑ i = 0 k − 1 ( k − i ) S ( n − i − 1 , k − i ) . S(n,k)=\delta_{n,k}+\sum_{i=0}^{k-1}(k-i)S(n-i-1,k-i). S(n,k)=δn,k​+i=0∑k−1​(k−i)S(n−i−1,k−i).

证明:
S ( n , k ) = S ( n − 1 , k − 1 ) + k S ( n − 1 , k ) S(n,k)=S(n-1, k-1)+kS(n-1,k) S(n,k)=S(n−1,k−1)+kS(n−1,k)
重复迭代右端第一项, 得.

置换与第一类Stirling数

由第二类Stirling数构成的矩阵为一个Stirling三角 ( S n k ) = ( S ( n , k ) ) n , k ≥ 0 (S_{nk})=\big(S(n,k)\big)_{n,k\geq0} (Snk​)=(S(n,k))n,k≥0​.
( S n k ) = ( S ( n , k ) ) n , k ≥ 0 = ( 1 0 1 0 0 1 1 0 1 3 1 0 1 7 6 1 ⋮ ⋮ ⋮ ⋮ ⋱ 1 ) (S_{nk})=\left(S(n,k)\right)_{n,k\geq0}= \begin{pmatrix} 1&&&&&\\ 0&1&&&\Large0&\\ 0&1&1&&\\ 0&1&3&1&&\\ 0&1&7&6&1&\\ \vdots&\vdots&\vdots&\vdots&&\ddots\\ &&&&&&1 \end{pmatrix} (Snk​)=(S(n,k))n,k≥0​=⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛​10000⋮​1111⋮​137⋮​16⋮​01​⋱​1​⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞​
无穷可逆下三角矩阵,

且 x n = ∑ k = 0 n S ( n , k ) ( x ) k x^n=\sum\limits_{k=0}^nS(n,k)(x)_k xn=k=0∑n​S(n,k)(x)k​, (两组多项式基的表示矩阵), 用 ( s ( n , k ) ) n , k ≥ 0 \big(s(n,k)\big)_{n,k\geq0} (s(n,k))n,k≥0​表示 ( S ( n , k ) ) n , k ≥ 0 \big(S(n,k)\big)_{n,k\geq0} (S(n,k))n,k≥0​的逆矩阵,即得到:
( x ) n = ∑ k = 0 n s ( n , k ) x k . (x)_n=\sum_{k=0}^ns(n,k)x^k. (x)n​=k=0∑n​s(n,k)xk.

定义1: 第一类Stirling数 s ( n , k ) s(n,k) s(n,k)由下述生成函数定义:
( x ) n = ∑ k = 0 n s ( n , k ) x k . (x)_n=\sum_{k=0}^ns(n,k)x^k. (x)n​=k=0∑n​s(n,k)xk.
展开左端的下阶乘, 得到 s ( n , k ) s(n,k) s(n,k)有符号, 称为第一类有符号Stirling数, 对应的还有第一类无符号Stirling数.

反演关系
{ f n = ∑ k = 0 n S ( n , k ) g k g n = ∑ k = 0 k s ( n , k ) f k \begin{cases} f_n=\sum\limits_{k=0}^nS(n,k)g_k\\ g_n=\sum\limits_{k=0}^ks(n,k)f_k \end{cases} ⎩⎪⎪⎨⎪⎪⎧​fn​=k=0∑n​S(n,k)gk​gn​=k=0∑k​s(n,k)fk​​

定义2: 第一类Stirling数的双变量生成函数
Ψ ( t , u ) = ∑ n , k ≥ 0 s ( n , k ) t n n ! u k = ∑ n ≥ 0 ( ∑ k ≥ 0 s ( n , k ) u k ) t n n ! = ∑ n ≥ 0 ( u ) n t n n ! = ∑ n ≥ 0 ( u n ) t n = ( 1 + t ) u \Psi(t,u)=\sum_{n,k\geq0}s(n,k)\frac{t^n}{n!}u^k=\sum_{n\geq0}\left(\sum_{k\geq0}s(n,k)u^k\right)\frac{t^n}{n!}\\ =\sum_{n\geq0}(u)_n\frac{t^n}{n!}=\sum_{n\geq0}\binom unt^n=(1+t)^u Ψ(t,u)=n,k≥0∑​s(n,k)n!tn​uk=n≥0∑​(k≥0∑​s(n,k)uk)n!tn​=n≥0∑​(u)n​n!tn​=n≥0∑​(nu​)tn=(1+t)u
针对上式, 还可立即得出单变量指数型生成函数
∑ n ≥ 0 ( ∑ k ≥ 0 s ( n , k ) u k ) t n n ! = ( 1 + t ) u = exp ⁡ ( u ln ⁡ ( 1 + u ) ) = ∑ k ≥ 0 ln ⁡ k ( 1 + t ) k ! u k \sum_{n\geq0}\left(\sum_{k\geq0}s(n,k)u^k\right)\frac{t^n}{n!}=(1+t)^u=\exp\big(u\ln(1+u)\big)=\sum_{k\geq0}\frac{\ln^k(1+t)}{k!}u^k n≥0∑​(k≥0∑​s(n,k)uk)n!tn​=(1+t)u=exp(uln(1+u))=k≥0∑​k!lnk(1+t)​uk
比较两端 [ u k ] [u^k] [uk], 得到:
Ψ k ( t ) = ∑ n ≥ 0 s ( n , k ) t n n ! = ln ⁡ k ( 1 + t ) k ! . \Psi_k(t)=\sum_{n\geq0}s(n,k)\frac{t^n}{n!}=\frac{\ln^k(1+t)}{k!}. Ψk​(t)=n≥0∑​s(n,k)n!tn​=k!lnk(1+t)​.

定义3: 第一类无符号Stirling数
s ˉ ( n , k ) = ∣ s ( n , k ) ∣ = ( − 1 ) n − k s ( n , k ) . \bar{s}(n,k)=\big|s(n,k)\big|=(-1)^{n-k}s(n,k). sˉ(n,k)=∣∣​s(n,k)∣∣​=(−1)n−ks(n,k).
定理1 第一类Stirling数具有水平生成函数
( x ) n = ∑ k = 0 n s ( n , k ) x k ⟨ x ⟩ n = ∑ k = 0 n s ˉ ( n , k ) x k (x)_n=\sum_{k=0}^ns(n,k)x^k\\ \ \langle x\rangle_n=\sum_{k=0}^n\bar{s}(n,k)x^k (x)n​=k=0∑n​s(n,k)xk ⟨x⟩n​=k=0∑n​sˉ(n,k)xk

由于 ( x ) n = ( − 1 ) n ⟨ x ⟩ n (x)_n=(-1)^{n}\langle x\rangle_n (x)n​=(−1)n⟨x⟩n​.

定理2 第一类Stirling数具有水平生成函数
Ψ n ( u ) = ∑ k = 1 n s ( n , k ) u n − k = ( 1 − u ) ( 1 − 2 u ) ⋯ ( 1 − ( n − 1 ) u ) Ψ n ( − u ) = ∑ k = 1 n s ˉ ( n , k ) u n − k = ( 1 + u ) ( 1 + 2 u ) ⋯ ( 1 + ( n − 1 ) u ) \ \ \Psi_n(u)=\sum_{k=1}^ns(n,k)u^{n-k}=(1-u)(1-2u)\cdots(1-(n-1)u)\\ \Psi_n(-u)=\sum_{k=1}^n\bar{s}(n,k)u^{n-k}=(1+u)(1+2u)\cdots(1+(n-1)u)   Ψn​(u)=k=1∑n​s(n,k)un−k=(1−u)(1−2u)⋯(1−(n−1)u)Ψn​(−u)=k=1∑n​sˉ(n,k)un−k=(1+u)(1+2u)⋯(1+(n−1)u)

证明: 在定理1中令 x = 1 u x=\frac1u x=u1​, 即证.

定理3 对固定的 n n n和变量 k k k, s ˉ ( n + 1 , k + 1 ) \bar{s}(n+1,k+1) sˉ(n+1,k+1)是前 n n n个正整数的初等对称函数, 即对于 l = 1 , 2 , . . . , n l=1,2,...,n l=1,2,...,n, 有
s ˉ ( n + 1 , n + 1 − l ) = ∑ 1 ≤ i 1 < i 2 < ⋯ < i l ≤ n i 1 i 2 ⋯ i l , \bar s(n+1, n+1-l)=\sum_{1\leq i_1<i_2<\cdots<i_l\leq n}i_1i_2\cdots i_l, sˉ(n+1,n+1−l)=1≤i1​<i2​<⋯<il​≤n∑​i1​i2​⋯il​,
换言之, 第一类无符号Stirling数 s ˉ ( n , k ) \bar s(n,k) sˉ(n,k)是 [ n − 1 ] [n-1] [n−1]中所有 n − k n-k n−k个不同的整数的乘积之和(乘积共有 ( n − 1 k − 1 ) \binom{n-1}{k-1} (k−1n−1​)个).

证明:
⟨ x ⟩ n = ∑ k = 0 n s ˉ ( n , k ) x k ⟹ ⟨ x ⟩ n + 1 = ∑ k = 0 n + 1 s ˉ ( n + 1 , k ) x k \langle x\rangle_n=\sum_{k=0}^n\bar{s}(n,k)x^k\Longrightarrow \langle x\rangle_{n+1}=\sum_{k=0}^{n+1}\bar{s}(n+1,k)x^k ⟨x⟩n​=k=0∑n​sˉ(n,k)xk⟹⟨x⟩n+1​=k=0∑n+1​sˉ(n+1,k)xk
右端两边同时除以 x x x, 得到
⟨ x + 1 ⟩ n = ( x + 1 ) ( x + 2 ) ⋯ ( x + n ) = ∑ k = 0 n s ˉ ( n + 1 , k + 1 ) x k , \langle x+1\rangle_{n}=(x+1)(x+2)\cdots(x+n)=\sum_{k=0}^{n}\bar{s}(n+1,k+1)x^k, ⟨x+1⟩n​=(x+1)(x+2)⋯(x+n)=k=0∑n​sˉ(n+1,k+1)xk,
于是 s ˉ ( n + 1 , k + 1 ) = [ x k ] ⟨ x + 1 ⟩ n \bar{s}(n+1,k+1)=[x^k]\langle x+1\rangle_n sˉ(n+1,k+1)=[xk]⟨x+1⟩n​为 [ n ] [n] [n]中所有 n − k n-k n−k个不同整数乘积之和.

---

又由
∑ k = 0 n s ˉ ( n , k ) u n − k = ( 1 + u ) ( 1 + 2 u ) ⋯ ( 1 + ( n − 1 ) u ) \sum_{k=0}^n\bar{s}(n,k)u^{n-k}=(1+u)(1+2u)\cdots(1+(n-1)u) k=0∑n​sˉ(n,k)un−k=(1+u)(1+2u)⋯(1+(n−1)u)
得到
∑ l = 0 n + 1 s ˉ ( n + 1 , n − l + 1 ) u l = ( 1 + u ) ( 1 + 2 u ) ⋯ ( 1 + n u ) \sum_{l=0}^{n+1}\bar{s}(n+1,n-l+1)u^{l}=(1+u)(1+2u)\cdots(1+nu) l=0∑n+1​sˉ(n+1,n−l+1)ul=(1+u)(1+2u)⋯(1+nu)
得到
s ˉ ( n + 1 , n − l + 1 ) = [ u l ] ( 1 + u ) ( 1 + 2 u ) ⋯ ( 1 + n u ) = ∑ 1 ≤ i 1 < i 2 < ⋯ < i l ≤ n i 1 i 2 ⋯ i l , \bar{s}(n+1,n-l+1)=[u^l](1+u)(1+2u)\cdots(1+nu)\\ \qquad\qquad\quad=\sum_{1\leq i_1<i_2<\cdots<i_l\leq n}i_1i_2\cdots i_l, sˉ(n+1,n−l+1)=[ul](1+u)(1+2u)⋯(1+nu)=1≤i1​<i2​<⋯<il​≤n∑​i1​i2​⋯il​,

第一类Stirling数的递推关系式

定理A:

1. s ( n , k ) = s ( n − 1 , k − 1 ) − ( n − 1 ) s ( n − 1 , k ) , ( n , k ≥ 1 ) , s ( n , 0 ) = s ( 0 , k ) = 0 , ( n , k ≥ 1 ) , s ( 0 , 0 ) = 1 s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k), (n,k\geq1),\\ s(n,0)=s(0,k)=0, (n,k\geq1),s(0,0)=1 s(n,k)=s(n−1,k−1)−(n−1)s(n−1,k),(n,k≥1),s(n,0)=s(0,k)=0,(n,k≥1),s(0,0)=1

2. s ˉ ( n , k ) = s ˉ ( n − 1 , k − 1 ) + ( n − 1 ) s ˉ ( n − 1 , k ) , ( n , k ≥ 1 ) , s ˉ ( n , 0 ) = s ˉ ( 0 , k ) = 0 , ( n , k ≥ 1 ) , s ˉ ( 0 , 0 ) = 1 \bar s(n,k)=\bar s(n-1,k-1)+(n-1)\bar s(n-1,k), (n,k\geq1),\\ \bar s(n,0)=\bar s(0,k)=0, (n,k\geq1), \bar s(0,0)=1 sˉ(n,k)=sˉ(n−1,k−1)+(n−1)sˉ(n−1,k),(n,k≥1),sˉ(n,0)=sˉ(0,k)=0,(n,k≥1),sˉ(0,0)=1

⇒ s ( n , 1 ) = ( − 1 ) n − 1 ( n − 1 ) ! , s ( n , n − 1 ) = − ( n 2 ) , s ( n , n ) = 1 \Rightarrow s(n,1)=(-1)^{n-1}(n-1)!,\quad s(n,n-1)=-\binom n2, s(n,n)=1 ⇒s(n,1)=(−1)n−1(n−1)!,s(n,n−1)=−(2n​),s(n,n)=1.

⇒ s ˉ ( n , 1 ) = ( n − 1 ) ! , s ˉ ( n , n − 1 ) = ( n 2 ) , s ˉ ( n , n ) = 1 \Rightarrow \bar s(n,1)=(n-1)!,\quad \bar s(n,n-1)=\binom n2, \bar s(n,n)=1 ⇒sˉ(n,1)=(n−1)!,sˉ(n,n−1)=(2n​),sˉ(n,n)=1.

证明: 用生成函数
∑ k = 0 n s ( n , k ) x k = ( x ) n = ( x ) n − 1 ( x − n + 1 ) = ∑ k = 0 n s ( n − 1 , k ) x k ( x − ( n − 1 ) ) \sum_{k=0}^ns(n,k)x^k=(x)_n=(x)_{n-1}(x-n+1)\\ =\sum_{k=0}^ns(n-1,k)x^k(x-(n-1)) k=0∑n​s(n,k)xk=(x)n​=(x)n−1​(x−n+1)=k=0∑n​s(n−1,k)xk(x−(n−1))
比较 [ x k ] [x^k] [xk], 得.

无符号情况同理.

第一类Stirling数的组合解释:

令 S n \mathcal{S}_n Sn​表示 [ n ] [n] [n]到 [ n ] [n] [n]所有双射构成的集合(置换群)

例如: 置换
π = ( 1 2 3 4 5 6 7 4 2 7 1 3 6 5 ) ∈ S 7 , \pi=\binom{1\ 2\ 3\ 4\ 5\ 6\ 7}{4\ 2\ 7\ 1\ 3\ 6\ 5}\in\mathcal{S}_7, π=(4 2 7 1 3 6 51 2 3 4 5 6 7​)∈S7​,
轮换表达式 π = ( 14 ) ( 2 ) ( 375 ) ( 6 ) \pi=(14)(2)(375)(6) π=(14)(2)(375)(6) ⇒ \Rightarrow ⇒ 4个轮换的乘积.

第一类无符号Stirling数 s ˉ ( n , k ) \bar s(n,k) sˉ(n,k)表示的是 S n \mathcal{S}_n Sn​中恰好有 k k k个轮换的置换的个数.

例子:

1. s ˉ ( n , n ) = 1 \bar s(n,n)=1 sˉ(n,n)=1, { ( 1 ) } \{(1)\} {(1)}.

2. s ˉ ( n , n − 1 ) = ( n 2 ) \bar s(n,n-1)=\binom n2 sˉ(n,n−1)=(2n​), n n n个元素中任取两个构成一个2元轮换, 其余 n − 2 n-2 n−2为1元轮换.

3. s ˉ ( n , 1 ) = ( n − 1 ) ! \bar s(n,1)=(n-1)! sˉ(n,1)=(n−1)!, 所有元素放在一起为一个轮换, 显然为 ( n − 1 ) ! (n-1)! (n−1)!.(圆排列)

4. 递推关系
   s ˉ ( n , k ) = s ˉ ( n − 1 , k − 1 ) + ( n − 1 ) s ˉ ( n − 1 , k ) , \bar{s}(n,k)=\bar s(n-1,k-1)+(n-1)\bar s(n-1,k), sˉ(n,k)=sˉ(n−1,k−1)+(n−1)sˉ(n−1,k),
   s ˉ ( n , k ) \bar s(n,k) sˉ(n,k)表示 S n \mathcal{S}_n Sn​中恰有 k k k个轮换的置换的个数.

   1. 若1单独作为一个轮换, 共有 s ˉ ( n − 1 , k − 1 ) \bar s(n-1, k-1) sˉ(n−1,k−1)个;
   2. 若1在其他 n − 1 n-1 n−1个元素构成的 k k k个轮换中(则1不单独作为一个轮换), 则1可以在其余 n − 1 n-1 n−1个元素前面形成不同的轮换, 共有 ( n − 1 ) s ˉ ( n − 1 , k ) (n-1)\bar s(n-1,k) (n−1)sˉ(n−1,k)个.