本篇文章主要介绍斯特林数的一些推导和性质。
应用的话，不会。
前置芝士
(1) 上升幂和下降幂
上升幂：(x^{overline n} = x imes (x+1) imes (x+2)..... imes (x+n-1))
下降幂：(x^{underline n} = x imes (x-1) imes (x-2)..... imes (x-n+1))
(2) 二项式反演
(f(n) = displaystylesum_{i=0}^{n} (-1)^i {{n}choose {i}}g(i) Rightarrow g(n) = displaystylesum_{i=0}^{n}(-1)^i {nchoose i}f(i))
或者 (f(n) = displaystylesum_{i=0}^{n}{nchoose i}g(i) Rightarrow g(n) = displaystylesum_{i=0}^{n} (-1)^{n-i}{nchoose i} f(i))
(3) 组合数的一些柿子
主要是第二类斯特林数推导过程会用到一些柿子。
(displaystylesum_{i=0}^{n} {ichoose m} = {n+1choose m+1})
因为 (n<m) 的时候 ({nchoose m} = 0), 所以我们的柿子可以写成：(displaystylesum_{i=m}^{n} {ichoose m})
即：({mchoose m} + {m+1choose m} + {m+2choose m}....+{nchoose m})
又因为：({mchoose m} = 1 = {m+1choose m+1})，所以 (m+1choose m+1) 可以和 ({m+1choose m}) 合并，变为：(m+2choose m+1)
然后有：({m+2choose m+1} + {m+2choose m} ={m+3choose m+1}), ({m+3choose m+1} + {m+3choose m} = {m+4choose m+1})
一直合并下去就可以得到 ({n+1choose m+1}) 。
由此可得： (displaystylesum_{i=0}^{n} {ichoose m} = {n+1choose m+1})
第一类斯特林数
第一类斯特林数 (s(n,m)) ,记做 (egin{bmatrix}n\m end{bmatrix}) 。
定义： 将 (n) 个不同的元素分成 (m) 个环的方案数 （环可以旋转，旋转后算一个环）。
递推式： (egin{bmatrix}n\mend{bmatrix} = egin{bmatrix}n-1\m-1end{bmatrix} +(n-1) imes egin{bmatrix} n-1\mend{bmatrix})
其中 (egin{bmatrix}0\0end{bmatrix} = 1, egin{bmatrix} i\0end{bmatrix} = 0 left(i ge 1 ight))
证明如下：考虑新加入的第 (n) 的元素，如果他新开一个环的话，那么剩下的 (n-1) 个元素就要放到 (m-1) 个环中，方案数为 (egin{bmatrix}n-1\m-1end{bmatrix}), 如果他要和某一个元素放在一个环，剩下的 (n-1) 个元素就要放到 (m) 个环中，且第 (n) 个元素可以放到剩下的 (n-1) 个元素的左边或右边，共有 (n-1) 个选择，所以方案数为 ((n-1) imes egin{bmatrix}n-1\mend{bmatrix}) 。
性质1：(displaystylesum_{i=0}^{n} egin{bmatrix}n\iend{bmatrix} = n!)
我们从置换的角度来入手证明这个柿子，一个置换会有若干的循环节， (i) 个循环节的置换总量为 (egin{bmatrix}n\iend{bmatrix}), 所以加起来就不重不漏的统计了所有的置换，总数为 (n!)
性质2：(x^{overline n} = displaystylesum_{i=0}^{n} egin{bmatrix}n\iend{bmatrix} x^i)
考虑用归纳法证明这个柿子。
(x^{overline {n+1}} = (x+n) imes x^{overline n})
(= (x+n) imes displaystylesum_{i=0}^{n}egin{bmatrix}n\iend{bmatrix} x^i)
(= x imes displaystylesum_{i=0}^{n} egin{bmatrix}n\iend{bmatrix} x^i + n imes displaystylesum_{i=0}^{n}egin{bmatrix}n\iend{bmatrix} x^i)
(=displaystylesum_{i=0}^{n} egin{bmatrix} n\iend{bmatrix}x^{i+1} + n imes displaystylesum_{i=0}^{n} egin{bmatrix}n\iend{bmatrix} x^i)
(= displaystylesum_{i=1}^{n+1} egin{bmatrix}n\i-1end{bmatrix}x^i + displaystylesum_{i=0}^{n} n imes egin{bmatrix}n\iend{bmatrix} x^i)
(= displaystylesum_{i=1}^{n}left(egin{bmatrix} n\i-1end{bmatrix} + n imes egin{bmatrix}n\iend{bmatrix} ight) x^i+ egin{bmatrix}n\nend{bmatrix}x^{n+1} + n imes egin{bmatrix} n\0end{bmatrix} x^0)
后面的两个散项看起来不太好看，我们想办法把他们凑成和前面的 (sigma) 中一样的形式。
因为 (egin{bmatrix} n\n+1end{bmatrix} = 0,egin{bmatrix}n\-1end{bmatrix} = 0) 所以我们把这两项带进去不会产生影响，即：
(x^{overline{n+1}} = left(displaystylesum_{i=1}^{n } egin{bmatrix} n\i-1end{bmatrix} + n imes egin{bmatrix}n\iend{bmatrix} ight) x^i + left(egin{bmatrix}{n}\{n}end{bmatrix} + n imes egin{bmatrix} n\n+1end{bmatrix} ight)x^{n+1} + left(egin{bmatrix}n\-1end{bmatrix} + n imes egin{bmatrix}n\0end{bmatrix} ight)x^0)
整理一下可以变成：
(x^{overline{n+1}} = displaystylesum_{i=0}^{n+1} left(egin{bmatrix}n\i-1end{bmatrix}+n imes egin{bmatrix}n\iend{bmatrix} ight) x^i)
你会发现 (x^i) 的系数正好是第一类斯特林数的递推公式，所以：
(x^{overline{n+1}} = displaystylesum_{i=0}^{n+1} egin{bmatrix}n+1\iend{bmatrix}x^i)
然后也就是我们性质2的柿子。
性质3： (x^{underline n} = displaystylesum_{i=0}^{n} (-1)^{n-i}egin{bmatrix}n\iend{bmatrix} x^i)
这个好像可以用二项式反演来证明，但是我不会，这里讲一个比较笨的方法。
(x^{underline n} = (-1)^n (-x)^{overline n} = (-1)^{n} displaystylesum_{i=0}^{n}egin{bmatrix} n\iend{bmatrix}(-x)^i = displaystylesum_{i=0}^{n}(-1)^{n-i}egin{bmatrix}n\iend{bmatrix}x^i)
第一类斯特林数.行
咕咕咕
第一类斯特林数.列
没学呢，咕咕咕。
第二类斯特林数
第二类斯特林数 (s(n,m)) 记做 (egin{Bmatrix}n\mend{Bmatrix}) 。
定义：把 (n) 个不同的元素，放到 (m) 个相同的集合，每个集合不能为空的方案数。
递推式： (egin{Bmatrix}n\mend{Bmatrix} = egin{Bmatrix}n-1\m-1end{Bmatrix} + m imes egin{Bmatrix}n-1\mend{Bmatrix})
其中 (egin{Bmatrix}0\0end{Bmatrix} = 1, egin{Bmatrix}i\0end{Bmatrix} = 0,(ige 1)) 。
性质1：(m^n = displaystylesum_{i=0}^{n} egin{Bmatrix}n\iend{Bmatrix} imes i! imes {mchoose i} = displaystylesum_{i=0}^{n} egin{Bmatrix}n\iend{Bmatrix}m^{underline i})
ps:这里的求和上标既可以是 (n) 也可以是 (m)， 因为当 (n>m) 的时候，({mchoose i} = 0 (i> m))， 当 (n<m) 的时候，(egin{Bmatrix} n\iend{Bmatrix} = 0 (i>n))
这个我们考虑用组合意义来证明。
首先 (m^n) 表示 (n) 个物品放入(m) 个不同的盒子中，每个盒子可以为空的情况数。
我们考虑枚举有多少个非空盒子，首先要从 (m) 个盒子中选出 (i) 个方案数为 (mchoose i) ，然后这个 (n)
个物品要放到 (i) 个盒子中，方案数为 (egin{Bmatrix}n\iend{Bmatrix}),又因为每个盒子不同，所以还要乘上 (i!) 。
因此 (m^n = displaystylesum_{i=0}^{n}egin{Bmatrix}n\iend{Bmatrix} imes i! imes {mchoose i}) 。
我们把组合数拆开可得：
(m^n = displaystylesum_{i=0}^{n} egin{Bmatrix}n\iend{Bmatrix} imes i! imes {m!over i! imes (m-i)!})
(=displaystylesum_{i=0}^{n}egin{Bmatrix}n\iend{Bmatrix} {m!over (m-i)!})
(=displaystylesum_{i=0}^{n} egin{Bmatrix}n\iend{Bmatrix}m^{underline i})
性质1的最右边的那个柿子也推出来了。
性质2： (displaystylesum_{i=0}^{n} i^k = displaystylesum_{i=0}^{k} egin{Bmatrix}k\iend{Bmatrix} imes i! imes {n+1choose i+1})
(displaystylesum_{i=0}^{n}i^k = displaystylesum_{i=0}^{n}sum_{j=0}^{k}egin{Bmatrix}k\jend{Bmatrix} imes j! imes {ichoose j})
交换一下求和顺序则有：
(displaystylesum_{i=0}^{n}i^k = displaystylesum_{i=0}^{k} egin{Bmatrix}k\iend{Bmatrix} imes i! sum_{j=0}^{n} {jchoose i})
根据前置芝士三里面的柿子可得：
(displaystylesum_{i=0}^{n}i^k = displaystylesum_{i=0}^{k}egin{Bmatrix}k\iend{Bmatrix} imes i! imes {n+1choose i+1})
我们性质2的柿子就出来了。
性质3：(m^n = displaystylesum_{i=0}^{m}(-1)^{n-i} imes egin{Bmatrix}n\iend{Bmatrix} imes m^{overline i})
这个自己推一下吧。
第二类斯特林数.行
给你一个 (n), 让你求 (egin{Bmatrix}n\iend{Bmatrix} (0leq ileq n)) 的具体值。
首先我们有 (m^n = displaystylesum_{i=0}^{m}egin{Bmatrix}n\iend{Bmatrix} imes i! imes {mchoose i})
设 (f(i) = i^n), (g(i) = egin{Bmatrix} n\iend{Bmatrix} imes i!) 。
然后就有：(f(m) = displaystylesum_{i=0}^{m}{mchoose i} imes g(i))
然后根据二项式反演可得：(g(m) = displaystylesum_{i=0}^{m}(-1)^{m-i} imes {mchoose i} imes f(i))
即：(egin{Bmatrix}n\mend{Bmatrix} imes m! = displaystylesum_{i=0}^{m}(-1)^{m-i} imes {mchoose i} imes i^n)
所以： (egin{Bmatrix}n\mend{Bmatrix} = displaystylesum_{i=0}^{m}(-1)^{m-i} imes {1over {m!}} imes {mchoose i} imes i^n)
我们把组合数拆开来构成卷积则有：
(egin{Bmatrix}n\mend{Bmatrix} = displaystylesum_{i=0}^{m}(-1)^{m-i} imes {1over {m!}} imes{m!over i! imes (m-i)!} imes i^n)
(egin{Bmatrix}n\mend{Bmatrix} = displaystylesum_{i=0}^{m}(-1)^{m-i} imes{1over i! imes (m-i)!} imes i^n)
(egin{Bmatrix}n\mend{Bmatrix} = displaystylesum_{i=0}^{m}{i^nover i!} imes {(-1)^{m-i}over (m-i)!})
然后我们构造两个多项式 (A(x),B(x), C(x)) 。
其中 (A(x) = displaystylesum_{i=0}^{n} {i^nover i!}x^i), (B(x) = displaystylesum_{i=0}^{n} {-1^iover i!}x^i), (C(x) = displaystylesum_{i=0}^{n} egin{Bmatrix}n\iend{Bmatrix} x^i)。
显然有：(C(x) = A(x)*B(x)) ,直接 (NTT) 即可。
计算出 (C(x)) 之后， (egin{Bmatrix}n\mend{Bmatrix} = [x^m]C(x)) 。
洛谷板子题代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int p = 167772161;
const int N = 1e6+10;
int n,lim,tim,rev[N],jz[N],inv[N],base[N],a[N],b[N];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
int ksm(int a,int b)
{
int res = 1;
for(; b; b >>= 1)
{
if(b & 1) res = res * a % p;
a = a * a % p;
}
return res;
}
void NTT(int *a,int lim,int opt)
{
for(int i = 0; i < lim; i++)
{
if(i < rev[i]) swap(a[i],a[rev[i]]);
}
for(int h = 1; h < lim; h <<= 1)
{
int wn = ksm(3,(p-1)/(h<<1));
if(opt == -1) wn = ksm(wn,p-2);
for(int j = 0; j < lim; j += (h<<1))
{
int w = 1;
for(int k = 0; k < h; k++)
{
int u = a[j + k];
int v = w * a[j + h + k] % p;
a[j + k] = (u + v) % p;
a[j + h + k] = (u - v + p) % p;
w = w * wn % p;
}
}
}
if(opt == -1)
{
int Inv = ksm(lim,p-2);
for(int i = 0; i < lim; i++) a[i] = a[i] * Inv % p;
}
}
signed main()
{
n = read();
jz[0] = 1;
for(int i = 1; i <= n; i++) jz[i] = jz[i-1] * i % p;
inv[n] = ksm(jz[n],p-2);
for(int i = n-1; i >= 0; i--) inv[i] = inv[i+1] * (i+1) % p;
for(int i = 1; i <= n; i++) base[i] = ksm(i,n);
for(int i = 0; i <= n; i++) a[i] = base[i] * inv[i] % p;
for(int i = 0, tmp = 1; i <= n; i++, tmp *= -1) b[i] = (tmp * inv[i] % p + p) % p;
lim = 1, tim = 0;
while(lim <= (n<<1)) lim <<= 1, tim++;
for(int i = 0; i < lim; i++) rev[i] = (rev[i>>1]>>1) | ((i&1)<<(tim-1));
NTT(a,lim,1); NTT(b,lim,1);
for(int i = 0; i < lim; i++) a[i] = a[i] * b[i] % p;
NTT(a,lim,-1);
for(int i = 0; i <= n; i++) printf("%lld ",a[i]);
printf("
");
return 0;
}
第二类斯特林数.列
没写呢，咕咕咕。
普通幂，上升幂和下降幂之间的转换
其实就是把前面的几个柿子总结了一下。
-
(x^{overline n} = displaystylesum_{i=0}^{n}egin{bmatrix}n\iend{bmatrix}x^i)
-
(x^{underline n} = displaystylesum_{i=0}^{n} (-1)^{n-i} egin{bmatrix}n\iend{bmatrix}x^i)
-
(x^n = displaystylesum_{i=0}^{n}egin{Bmatrix}n\iend{Bmatrix} imes x^{underline i})
-
(x^n = displaystylesum_{i=0}^{n}(-1)^{n-i}egin{Bmatrix}n\iend{Bmatrix}x^{overline i})
把这几个柿子记住就好了。
幂的大小顺序：(x^{overline n} >x^n > x^{underline n}), 大幂转化为小幂的时候要乘上 (-1^{n-i})。