什么是两类斯特林数
斯特林数是组合数学中用来描述“把元素组织成若干部分”的一类计数工具，常见的有两类：第一类斯特林数 和第二类斯特林数 。
它们名字相近，但数的对象完全不同：
第一类斯特林数：数的是排列可以分成多少个循环 ；
第二类斯特林数：数的是集合可以分成多少个非空子集 。
第一类斯特林数
第一类斯特林数通常记作
c ( n , k ) c(n,k) c ( n , k )
或者
[ n k ] \left[{n \atop k}\right] [ k n ]
表示：
将 n n n k k k
这里的“循环”指的是排列的循环表示。
例如 n = 3 n=3 n = 3 1 , 2 , 3 1,2,3 1 , 2 , 3
恰好分成 1 1 1
( 1 2 3 ) , ( 1 3 2 ) (1\ 2\ 3), (1\ 3\ 2) ( 1 2 3 ) , ( 1 3 2 )
所以
c ( 3 , 1 ) = 2 c(3,1)=2 c ( 3 , 1 ) = 2
恰好分成 2 2 2
( 1 ) ( 2 3 ) , ( 2 ) ( 1 3 ) , ( 3 ) ( 1 2 ) (1)(2\ 3), (2)(1\ 3), (3)(1\ 2) ( 1 ) ( 2 3 ) , ( 2 ) ( 1 3 ) , ( 3 ) ( 1 2 )
所以
c ( 3 , 2 ) = 3 c(3,2)=3 c ( 3 , 2 ) = 3
恰好分成 3 3 3
( 1 ) ( 2 ) ( 3 ) (1)(2)(3) ( 1 ) ( 2 ) ( 3 )
所以
c ( 3 , 3 ) = 1 c(3,3)=1 c ( 3 , 3 ) = 1
因此第一类斯特林数关注的是：
一个排列的循环结构。
它的递推式是：
c ( n , k ) = c ( n − 1 , k − 1 ) + ( n − 1 ) c ( n − 1 , k ) c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k)
c ( n , k ) = c ( n − 1 , k − 1 ) + ( n − 1 ) c ( n − 1 , k ) 解释如下：
考虑第 n n n
如果 n n n n − 1 n-1 n − 1 k − 1 k-1 k − 1 c ( n − 1 , k − 1 ) c(n-1,k-1) c ( n − 1 , k − 1 )
如果 n n n n − 1 n-1 n − 1 k k k n − 1 n-1 n − 1 n n n ( n − 1 ) c ( n − 1 , k ) (n-1)c(n-1,k) ( n − 1 ) c ( n − 1 , k )
初始条件为：
c ( 0 , 0 ) = 1 c(0,0)=1
c ( 0 , 0 ) = 1 并且当 n > 0 n>0 n > 0
c ( n , 0 ) = 0 c(n,0)=0
c ( n , 0 ) = 0 当 k > n k>n k > n
c ( n , k ) = 0 c(n,k)=0
c ( n , k ) = 0 需要注意的是，有些资料会使用带符号第一类斯特林数 ，记作 s ( n , k ) s(n,k) s ( n , k )
s ( n , k ) = ( − 1 ) n − k c ( n , k ) s(n,k)=(-1)^{n-k}c(n,k)
s ( n , k ) = ( − 1 ) n − k c ( n , k ) 竞赛中如果只是计数排列循环，通常用的是无符号第一类斯特林数。
第二类斯特林数
第二类斯特林数通常记作
S ( n , k ) S(n,k) S ( n , k )
或者
{ n k } \left\{{n \atop k}\right\} { k n }
表示：
将 n n n k k k
这里的 k k k 没有顺序 。
例如 n = 3 n=3 n = 3 1 , 2 , 3 1,2,3 1 , 2 , 3
划分成 1 1 1
{ 1 , 2 , 3 } \{1,2,3\} { 1 , 2 , 3 }
所以
S ( 3 , 1 ) = 1 S(3,1)=1 S ( 3 , 1 ) = 1
划分成 2 2 2
{ 1 } , { 2 , 3 } \{1\},\{2,3\} { 1 } , { 2 , 3 }
{ 2 } , { 1 , 3 } \{2\},\{1,3\} { 2 } , { 1 , 3 }
{ 3 } , { 1 , 2 } \{3\},\{1,2\} { 3 } , { 1 , 2 }
所以
S ( 3 , 2 ) = 3 S(3,2)=3 S ( 3 , 2 ) = 3
划分成 3 3 3
{ 1 } , { 2 } , { 3 } \{1\},\{2\},\{3\} { 1 } , { 2 } , { 3 }
所以
S ( 3 , 3 ) = 1 S(3,3)=1 S ( 3 , 3 ) = 1
因此第二类斯特林数关注的是：
把不同元素分成若干个没有顺序的非空组。
它的递推式是：
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 ) + k S ( n − 1 , k ) 解释如下：
考虑第 n n n
如果 n n n n − 1 n-1 n − 1 k − 1 k-1 k − 1 S ( n − 1 , k − 1 ) S(n-1,k-1) S ( n − 1 , k − 1 )
如果 n n n n − 1 n-1 n − 1 k k k n n n k S ( n − 1 , k ) kS(n-1,k) k S ( n − 1 , k )
初始条件为：
S ( 0 , 0 ) = 1 S(0,0)=1
S ( 0 , 0 ) = 1 并且当 n > 0 n>0 n > 0
S ( n , 0 ) = 0 S(n,0)=0
S ( n , 0 ) = 0 当 k > n k>n k > n
S ( n , k ) = 0 S(n,k)=0
S ( n , k ) = 0 两类斯特林数的区别
类型
常用记号
计数对象
关键词
第一类斯特林数
c ( n , k ) c(n,k) c ( n , k ) [ n k ] \left[{n \atop k}\right] [ k n ] n n n k k k 排列、循环
第二类斯特林数
S ( n , k ) S(n,k) S ( n , k ) { n k } \left\{{n \atop k}\right\} { k n } n n n k k k 集合划分、分组
一个简单的记忆方式是：
第一类斯特林数和排列 有关；
第二类斯特林数和集合划分 有关。
和多项式的关系
两类斯特林数还可以看成普通幂和阶乘幂之间的转换系数。
第一类斯特林数和下降幂有关。
下降幂定义为：
x n ‾ = x ( x − 1 ) ( x − 2 ) ⋯ ( x − n + 1 ) x^{\underline n}=x(x-1)(x-2)\cdots(x-n+1)
x n = x ( x − 1 ) ( x − 2 ) ⋯ ( x − n + 1 ) 它可以展开成：
x n ‾ = ∑ k = 0 n s ( n , k ) x k x^{\underline n}=\sum_{k=0}^{n}s(n,k)x^k
x n = k = 0 ∑ n s ( n , k ) x k 这里的 s ( n , k ) s(n,k) s ( n , k )
第二类斯特林数则可以把普通幂展开成下降幂：
x n = ∑ k = 0 n S ( n , k ) x k ‾ x^n=\sum_{k=0}^{n}S(n,k)x^{\underline k}
x n = k = 0 ∑ n S ( n , k ) x k 这说明第二类斯特林数可以理解为：
把 n n n
和满射的关系
第二类斯特林数还有一个常用解释。
把 n n n k k k n n n k k k
先把 n n n k k k S ( n , k ) S(n,k) S ( n , k )
再把这 k k k k k k k ! k! k !
所以满射数量为：
k ! S ( n , k ) k!S(n,k)
k ! S ( n , k ) 因此：
$$S(n,k)=\frac{\text{从 } n \text{ 个元素到 } k \text{ 个元素的满射数}}{k!}
$$小例子对比
当 n = 3 n=3 n = 3
第一类斯特林数：
k k k c ( 3 , k ) c(3,k) c ( 3 , k )
1 1 1 2 2 2
2 2 2 3 3 3
3 3 3 1 1 1
第二类斯特林数：
k k k S ( 3 , k ) S(3,k) S ( 3 , k )
1 1 1
2 2 2 3 3 3
3 3 3 1 1 1
虽然这里有些数看起来一样，但它们的含义完全不同。
c ( 3 , 1 ) = 2 c(3,1)=2 c ( 3 , 1 ) = 2 3 3 3
S ( 3 , 1 ) = 1 S(3,1)=1 S ( 3 , 1 ) = 1 3 3 3
一句话总结
第一类斯特林数数的是：n n n k k k
第二类斯特林数数的是：n n n k k k
什么是两类斯特林数
斯特林数是组合数学中用来描述“把元素组织成若干部分”的一类计数工具，常见的有两类：第一类斯特林数 和第二类斯特林数 。
它们名字相近，但数的对象完全不同：
第一类斯特林数：数的是排列可以分成多少个循环 ；
第二类斯特林数：数的是集合可以分成多少个非空子集 。
第一类斯特林数
第一类斯特林数通常记作
c ( n , k ) c(n,k) c ( n , k )
或者
[ n k ] \left[{n \atop k}\right] [ k n ]
表示：
将 n n n k k k
这里的“循环”指的是排列的循环表示。
例如 n = 3 n=3 n = 3 1 , 2 , 3 1,2,3 1 , 2 , 3
恰好分成 1 1 1
( 1 2 3 ) , ( 1 3 2 ) (1\ 2\ 3), (1\ 3\ 2) ( 1 2 3 ) , ( 1 3 2 )
所以
c ( 3 , 1 ) = 2 c(3,1)=2 c ( 3 , 1 ) = 2
恰好分成 2 2 2
( 1 ) ( 2 3 ) , ( 2 ) ( 1 3 ) , ( 3 ) ( 1 2 ) (1)(2\ 3), (2)(1\ 3), (3)(1\ 2) ( 1 ) ( 2 3 ) , ( 2 ) ( 1 3 ) , ( 3 ) ( 1 2 )
所以
c ( 3 , 2 ) = 3 c(3,2)=3 c ( 3 , 2 ) = 3
恰好分成 3 3 3
( 1 ) ( 2 ) ( 3 ) (1)(2)(3) ( 1 ) ( 2 ) ( 3 )
所以
c ( 3 , 3 ) = 1 c(3,3)=1 c ( 3 , 3 ) = 1
因此第一类斯特林数关注的是：
一个排列的循环结构。
它的递推式是：
c ( n , k ) = c ( n − 1 , k − 1 ) + ( n − 1 ) c ( n − 1 , k ) c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k)
c ( n , k ) = c ( n − 1 , k − 1 ) + ( n − 1 ) c ( n − 1 , k ) 解释如下：
考虑第 n n n
如果 n n n n − 1 n-1 n − 1 k − 1 k-1 k − 1 c ( n − 1 , k − 1 ) c(n-1,k-1) c ( n − 1 , k − 1 )
如果 n n n n − 1 n-1 n − 1 k k k n − 1 n-1 n − 1 n n n ( n − 1 ) c ( n − 1 , k ) (n-1)c(n-1,k) ( n − 1 ) c ( n − 1 , k )
初始条件为：
c ( 0 , 0 ) = 1 c(0,0)=1
c ( 0 , 0 ) = 1 并且当 n > 0 n>0 n > 0
c ( n , 0 ) = 0 c(n,0)=0
c ( n , 0 ) = 0 当 k > n k>n k > n
c ( n , k ) = 0 c(n,k)=0
c ( n , k ) = 0 需要注意的是，有些资料会使用带符号第一类斯特林数 ，记作 s ( n , k ) s(n,k) s ( n , k )
s ( n , k ) = ( − 1 ) n − k c ( n , k ) s(n,k)=(-1)^{n-k}c(n,k)
s ( n , k ) = ( − 1 ) n − k c ( n , k ) 竞赛中如果只是计数排列循环，通常用的是无符号第一类斯特林数。
第二类斯特林数
第二类斯特林数通常记作
S ( n , k ) S(n,k) S ( n , k )
或者
{ n k } \left\{{n \atop k}\right\} { k n }
表示：
将 n n n k k k
这里的 k k k 没有顺序 。
例如 n = 3 n=3 n = 3 1 , 2 , 3 1,2,3 1 , 2 , 3
划分成 1 1 1
{ 1 , 2 , 3 } \{1,2,3\} { 1 , 2 , 3 }
所以
S ( 3 , 1 ) = 1 S(3,1)=1 S ( 3 , 1 ) = 1
划分成 2 2 2
{ 1 } , { 2 , 3 } \{1\},\{2,3\} { 1 } , { 2 , 3 }
{ 2 } , { 1 , 3 } \{2\},\{1,3\} { 2 } , { 1 , 3 }
{ 3 } , { 1 , 2 } \{3\},\{1,2\} { 3 } , { 1 , 2 }
所以
S ( 3 , 2 ) = 3 S(3,2)=3 S ( 3 , 2 ) = 3
划分成 3 3 3
{ 1 } , { 2 } , { 3 } \{1\},\{2\},\{3\} { 1 } , { 2 } , { 3 }
所以
S ( 3 , 3 ) = 1 S(3,3)=1 S ( 3 , 3 ) = 1
因此第二类斯特林数关注的是：
把不同元素分成若干个没有顺序的非空组。
它的递推式是：
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 ) + k S ( n − 1 , k ) 解释如下：
考虑第 n n n
如果 n n n n − 1 n-1 n − 1 k − 1 k-1 k − 1 S ( n − 1 , k − 1 ) S(n-1,k-1) S ( n − 1 , k − 1 )
如果 n n n n − 1 n-1 n − 1 k k k n n n k S ( n − 1 , k ) kS(n-1,k) k S ( n − 1 , k )
初始条件为：
S ( 0 , 0 ) = 1 S(0,0)=1
S ( 0 , 0 ) = 1 并且当 n > 0 n>0 n > 0
S ( n , 0 ) = 0 S(n,0)=0
S ( n , 0 ) = 0 当 k > n k>n k > n
S ( n , k ) = 0 S(n,k)=0
S ( n , k ) = 0 两类斯特林数的区别
类型
常用记号
计数对象
关键词
第一类斯特林数
c ( n , k ) c(n,k) c ( n , k ) [ n k ] \left[{n \atop k}\right] [ k n ] n n n k k k 排列、循环
第二类斯特林数
S ( n , k ) S(n,k) S ( n , k ) { n k } \left\{{n \atop k}\right\} { k n } n n n k k k 集合划分、分组
一个简单的记忆方式是：
第一类斯特林数和排列 有关；
第二类斯特林数和集合划分 有关。
和多项式的关系
两类斯特林数还可以看成普通幂和阶乘幂之间的转换系数。
第一类斯特林数和下降幂有关。
下降幂定义为：
x n ‾ = x ( x − 1 ) ( x − 2 ) ⋯ ( x − n + 1 ) x^{\underline n}=x(x-1)(x-2)\cdots(x-n+1)
x n = x ( x − 1 ) ( x − 2 ) ⋯ ( x − n + 1 ) 它可以展开成：
x n ‾ = ∑ k = 0 n s ( n , k ) x k x^{\underline n}=\sum_{k=0}^{n}s(n,k)x^k
x n = k = 0 ∑ n s ( n , k ) x k 这里的 s ( n , k ) s(n,k) s ( n , k )
第二类斯特林数则可以把普通幂展开成下降幂：
x n = ∑ k = 0 n S ( n , k ) x k ‾ x^n=\sum_{k=0}^{n}S(n,k)x^{\underline k}
x n = k = 0 ∑ n S ( n , k ) x k 这说明第二类斯特林数可以理解为：
把 n n n
和满射的关系
第二类斯特林数还有一个常用解释。
把 n n n k k k n n n k k k
先把 n n n k k k S ( n , k ) S(n,k) S ( n , k )
再把这 k k k k k k k ! k! k !
所以满射数量为：
k ! S ( n , k ) k!S(n,k)
k ! S ( n , k ) 因此：
$$S(n,k)=\frac{\text{从 } n \text{ 个元素到 } k \text{ 个元素的满射数}}{k!}
$$小例子对比
当 n = 3 n=3 n = 3
第一类斯特林数：
k k k c ( 3 , k ) c(3,k) c ( 3 , k )
1 1 1 2 2 2
2 2 2 3 3 3
3 3 3 1 1 1
第二类斯特林数：
k k k S ( 3 , k ) S(3,k) S ( 3 , k )
1 1 1
2 2 2 3 3 3
3 3 3 1 1 1
虽然这里有些数看起来一样，但它们的含义完全不同。
c ( 3 , 1 ) = 2 c(3,1)=2 c ( 3 , 1 ) = 2 3 3 3
S ( 3 , 1 ) = 1 S(3,1)=1 S ( 3 , 1 ) = 1 3 3 3
一句话总结
第一类斯特林数数的是：n n n k k k
第二类斯特林数数的是：n n n k k k
YIZHIYANG初来乍到 2026-5-15 23:59:39
