第一类斯特林数
定义
[ n m ] \begin{bmatrix}n\\m\end{bmatrix} [nm] 或 s ( n , m ) s(n,m) s(n,m) ，表示 n n n 个不同的数分成 m m m 个无序圆排列的方案数。
这个是可以递推的，考虑最后一个数单独成环还是加入到前面的环中，有：
[
n
m
]
=
[
n
−
1
m
−
1
]
+
(
n
−
1
)
[
n
−
1
m
]
\begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\m\end{bmatrix}
[nm]=[n−1m−1]+(n−1)[n−1m]
因此可以
O
(
n
m
)
O(nm)
O(nm) 求出
{
[
i
j
]
∣
i
∈
[
0
,
n
]
,
j
∈
[
0
,
m
]
}
\{\begin{bmatrix}i\\j\end{bmatrix}|i\in[0,n],j\in[0,m]\}
{[ij]∣i∈[0,n],j∈[0,m]}。
性质
-
n
!
=
∑
i
=
1
n
[
n
i
]
n!=\sum\limits_{i=1}^{n}\begin{bmatrix}n\\i\end{bmatrix}
n!=i=1∑n[ni]
一个排列本质上就是由若干个圆排列组成，于是我们可以枚举圆排列的数量。 -
x
n
‾
=
∑
i
=
0
n
[
n
i
]
x
i
x^{\overline{n}}=\sum\limits_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i
xn=i=0∑n[ni]xi
其中， x n ‾ = x ( x + 1 ) . . . ( x + n − 1 ) x^{\overline{n}}=x(x+1)...(x+n-1) xn=x(x+1)...(x+n−1)，称之为 x x x 的 n n n 次上升幂。对于这个式子，我们可以考虑归纳证明。考虑 k = n − 1 k=n-1 k=n−1 时， x i x^i xi 的系数，记作 f ( n − 1 , i ) f(n-1,i) f(n−1,i)； k = n k=n k=n 时，乘多了个 x + n − 1 x+n-1 x+n−1，那么 f ( n , i ) = f ( n − 1 , i − 1 ) + ( n − 1 ) f ( n − 1 , i ) f(n,i)=f(n-1,i-1)+(n-1)f(n-1,i) f(n,i)=f(n−1,i−1)+(n−1)f(n−1,i)，发现这就是第一类斯特林数的递推式呀。 -
x
n
‾
=
∑
i
=
0
n
(
−
1
)
n
−
i
[
n
i
]
x
i
x^{\underline{n}}=\sum\limits_{i=0}^{n}(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}x^i
xn=i=0∑n(−1)n−i[ni]xi
其中， x n ‾ = x ( x − 1 ) . . . ( x − n + 1 ) x^{\underline{n}}=x(x-1)...(x-n+1) xn=x(x−1)...(x−n+1)，称之为 x x x 的 n n n 次下降幂。该式的证明，我就不证了。
第二类斯特林数
定义
{
n
m
}
\begin{Bmatrix}n\\m\end{Bmatrix}
{nm} 或
S
(
n
,
m
)
S(n,m)
S(n,m)，表示
n
n
n 个不同的数分成
m
m
m 个无序集合的方案数。
这个也是可以递推的，考虑最后一个数单独作为一个集合或者是放入之前的集合中，有：
{
n
m
}
=
{
n
−
1
m
−
1
}
+
m
{
n
−
1
m
}
\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\m\end{Bmatrix}
{nm}={n−1m−1}+m{n−1m}
因此可以
O
(
n
m
)
O(nm)
O(nm) 求出
{
{
i
j
}
∣
i
∈
[
0
,
n
]
,
j
∈
[
0
,
m
]
}
\{\begin{Bmatrix}i\\j\end{Bmatrix}|i\in[0,n],j\in[0,m]\}
{{ij}∣i∈[0,n],j∈[0,m]}。
性质
-
m
n
=
∑
i
=
0
n
C
m
i
{
n
i
}
i
!
m^n=\sum\limits_{i=0}^{n}C_m^i\begin{Bmatrix}n\\i\end{Bmatrix}i!
mn=i=0∑nCmi{ni}i!
考虑该式的组合意义： n n n 个不同的球，放入 m m m 个不同的盒子中，每个盒子可以空的方案数。我们可以放了球的盒子个数 i i i，那么有 C m i C_m^i Cmi 种选法，然后把 n n n 个球放进 i i i 个不同盒子中，方案数为 { n m } i ! \begin{Bmatrix}n\\m\end{Bmatrix}i! {nm}i!。 - 如果将上式的组合数乘进式子里，我们可以得到：
m n = ∑ i = 0 n { n i } m i ‾ m^n=\sum\limits_{i=0}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}m^{\underline{i}} mn=i=0∑n{ni}mi
求斯特林数
第一类斯特林数 · 行
求
[
n
0
]
,
[
n
1
]
.
.
.
,
[
n
n
]
\begin{bmatrix}n\\0\end{bmatrix},\begin{bmatrix}n\\1\end{bmatrix}...,\begin{bmatrix}n\\n\end{bmatrix}
[n0],[n1]...,[nn]，其中
n
≤
1
0
5
n\leq 10^5
n≤105。
考虑生成函数
x
n
‾
=
∑
i
=
0
n
[
n
i
]
x
i
x^{\overline{n}}=\sum\limits_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i
xn=i=0∑n[ni]xi。
我们只需要快速求出
x
n
‾
x^{\overline{n}}
xn 的各项系数即可。可以用分治
F
F
T
FFT
FFT 在
O
(
n
l
o
g
2
n
)
O(nlog^2n)
O(nlog2n) 求出。但是分治
N
T
T
NTT
NTT 太
n
a
i
v
e
naive
naive 了，这个是可以倍增
N
T
T
NTT
NTT 来求的。
考虑从
x
n
‾
x^{\overline{n}}
xn 推到
x
2
n
‾
x^{\overline{2n}}
x2n。首先显然有
x
2
n
‾
=
x
n
‾
(
x
+
n
)
n
‾
x^{\overline{2n}}=x^{\overline{n}}(x+n)^{\overline{n}}
x2n=xn(x+n)n。
假设我们已经求出了
x
n
‾
x^{\overline{n}}
xn，记作
f
(
x
)
f(x)
f(x)，现在要求
f
(
x
+
n
)
f(x+n)
f(x+n)。
而
f
(
x
+
n
)
=
∑
i
=
0
n
f
i
(
x
+
n
)
i
=
∑
i
=
0
n
f
i
∑
j
=
0
i
C
i
j
x
j
n
i
−
j
=
∑
j
=
0
n
x
j
j
!
∑
i
=
j
n
n
i
−
j
(
i
−
j
)
!
i
!
f
i
f(x+n)=\sum\limits_{i=0}^{n}f_i(x+n)^i=\sum\limits_{i=0}^{n}f_i\sum\limits_{j=0}^{i}C_i^jx^jn^{i-j}=\sum\limits_{j=0}^{n}\frac{x^j}{j!}\sum\limits_{i=j}^{n}\frac{n^{i-j}}{(i-j)!}i!f_i
f(x+n)=i=0∑nfi(x+n)i=i=0∑nfij=0∑iCijxjni−j=j=0∑nj!xji=j∑n(i−j)!ni−ji!fi
后面那一部分是个卷积形式，记
g
j
=
∑
i
=
j
n
n
i
−
j
(
i
−
j
)
!
i
!
f
i
g_j=\sum\limits_{i=j}^{n}\frac{n^{i-j}}{(i-j)!}i!f_i
gj=i=j∑n(i−j)!ni−ji!fi，翻转一下
i
!
f
i
i!f_i
i!fi 后，我们可以用
N
T
T
NTT
NTT 快速求出
g
j
g_j
gj。
时间复杂度是
T
(
n
)
=
T
(
n
/
2
)
+
O
(
n
l
o
g
n
)
=
O
(
n
l
o
g
n
)
T(n)=T(n/2)+O(nlogn)=O(nlogn)
T(n)=T(n/2)+O(nlogn)=O(nlogn)。
第一类斯特林数 · 列
求
[
0
k
]
,
[
1
k
]
.
.
.
,
[
n
k
]
\begin{bmatrix}0\\k\end{bmatrix},\begin{bmatrix}1\\k\end{bmatrix}...,\begin{bmatrix}n\\k\end{bmatrix}
[0k],[1k]...,[nk]，其中
n
≤
1
0
5
n\leq 10^5
n≤105。
设
f
(
1
,
x
)
f(1,x)
f(1,x) 为
k
=
1
k=1
k=1 时
[
0
1
]
,
[
1
1
]
.
.
.
,
[
n
1
]
\begin{bmatrix}0\\1\end{bmatrix},\begin{bmatrix}1\\1\end{bmatrix}...,\begin{bmatrix}n\\1\end{bmatrix}
[01],[11]...,[n1] 的
E
G
F
EGF
EGF，那么
f
(
1
,
x
)
=
∑
i
=
0
n
(
i
−
1
)
!
i
!
x
i
f(1,x)=\sum\limits_{i=0}^{n}\frac{(i-1)!}{i!}x^i
f(1,x)=i=0∑ni!(i−1)!xi。那么
f
(
k
,
n
)
=
f
(
1
,
n
)
k
k
!
f(k,n)=\frac{f(1,n)^k}{k!}
f(k,n)=k!f(1,n)k，除掉
k
!
k!
k! 是因为环之间是没有顺序的。
然后多项式快速幂即可，复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)。
第二类斯特林数 · 行
求
{
n
0
}
,
{
n
1
}
.
.
.
,
{
n
n
}
\begin{Bmatrix}n\\0\end{Bmatrix},\begin{Bmatrix}n\\1\end{Bmatrix}...,\begin{Bmatrix}n\\n\end{Bmatrix}
{n0},{n1}...,{nn}，其中
n
≤
1
0
5
n\leq 10^5
n≤105。
其实，第二类斯特林数还可以这样求。我们可以先给集合标序，然后再把方案数除掉
m
!
m!
m!，这样做可行的原因是没有非空集合，每一种填数方案都会重复
m
!
m!
m! 次。所以根据容斥原理，我们可以枚举空的集合的个数
i
i
i，然后有
{
n
m
}
=
1
m
!
∑
i
=
0
m
(
−
1
)
i
C
n
i
(
m
−
i
)
n
\begin{Bmatrix}n\\m\end{Bmatrix}={1 \over m!} \sum\limits_{i=0}^{m}(-1)^iC_n^i(m-i)^n
{nm}=m!1i=0∑m(−1)iCni(m−i)n。发现这是个卷积的形式，于是可以用
N
T
T
NTT
NTT 在
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) 求出。
第二类斯特林数 · 列
求
{
0
k
}
,
{
1
k
}
.
.
.
,
{
n
k
}
\begin{Bmatrix}0\\k\end{Bmatrix},\begin{Bmatrix}1\\k\end{Bmatrix}...,\begin{Bmatrix}n\\k\end{Bmatrix}
{0k},{1k}...,{nk}，其中
n
≤
1
0
5
n\leq 10^5
n≤105。
和求第一类斯特林数的方法是一样的。
设
f
(
1
,
x
)
f(1,x)
f(1,x) 为
k
=
1
k=1
k=1 时
{
0
1
}
,
{
1
1
}
.
.
.
,
{
n
1
}
\begin{Bmatrix}0\\1\end{Bmatrix},\begin{Bmatrix}1\\1\end{Bmatrix}...,\begin{Bmatrix}n\\1\end{Bmatrix}
{01},{11}...,{n1} 的
E
G
F
EGF
EGF，那么
f
(
1
,
x
)
=
∑
i
=
0
n
{
i
1
}
i
!
x
i
=
∑
i
=
0
n
1
i
!
x
i
f(1,x)=\sum\limits_{i=0}^{n}\frac{\tiny{\begin{Bmatrix}i\\1\end{Bmatrix}}}{i!}x^i=\sum\limits_{i=0}^{n}\frac{1}{i!}x^i
f(1,x)=i=0∑ni!{i1}xi=i=0∑ni!1xi。那么
f
(
k
,
n
)
=
f
(
1
,
n
)
k
k
!
f(k,n)=\frac{f(1,n)^k}{k!}
f(k,n)=k!f(1,n)k，除掉
k
!
k!
k! 是因为集合之间是没有顺序的。
然后多项式快速幂即可，复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)。