Menu
    1. 组合数取模
    2. 组合数 LCM
    3. Stirling 数
      1. 第一类斯特林数
      2. 第二类斯特林数
      3. 斯特林近似公式
    4. 小球入盒模型通解
    5. 置换
    6. 生成字典序
      1. 下一排列
    7. 二项式反演
    8. 第 k 小期望
    9. 错排数
    10. Bonuli 数
    11. Catalan 数
    12. Bell 数
      1. 等价类容斥
    13. Grey 码
    14. 扩展 Cayley 公式
    15. 超立方体
    16. 枚举位集 I 的非空子集 J

    组合数学

    post on 31 Jan 2019 about 4438words require 15min
    CC BY 4.0 （除特别声明或转载文章外）
    如果这篇文章帮助到你，可以请我喝一杯咖啡~

    组合数取模

    使用示例

    为方便，记C(n,m)=Cnm=(nm)C(n,m)=C_n^m=\binom{n}{m}。

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

    struct Factorial : Mod
{
	vector<ll> fac, ifac;
	Factorial(int N, ll M) : fac(N, 1), ifac(N, 1), Mod(M)
	{
		for (int i = 2; i < N; ++i)
			fac[i] = mul(fac[i - 1], i), ifac[i] = mul(M - M / i, ifac[M % i]);
		for (int i = 2; i < N; ++i)
			ifac[i] = mul(ifac[i], ifac[i - 1]);
	}
	ll c(int n, int m) { return mul(mul(fac[n], ifac[m]), ifac[n - m]); }
	ll lucas(ll n, ll m) //卢卡斯定理求C(n,m)%M，适用于模数M小于N的情况，或者m较小的时候也可以暴力求
	{
		if (!m)
			return 1;
		if (n < m || n % M < m % M)
			return 0;
		if (n < M && m < M)
			return c(n, m);
		return mul(lucas(n / M, m / M), lucas(n % M, m % M));
	}
};

    组合数 LCM

    (n+1)lcm(C(n,0),C(n,1),…,C(n,k))=lcm(n+1,n,n−1,n−2,…,n−k+1)(n + 1)lcm(C(n,0),C(n,1),\dots,C(n,k))=lcm(n+1,n,n−1,n−2,\dots,n−k+1)

    区间 lcm 的维护：对于一个数，将其分解质因数，若有因子pkp^k，那么拆分出 k 个数 p1,p2,…,pkp^1,p^2,\dots,p^k，权值都为 p，那么区间[l,r][l,r]内所有数的 lcm 的答案=所有在该区间中出现过的数的权值之积，可持久化线段树维护之。

    Stirling 数

    第一类斯特林数

    第一类斯特林数S(p,k)S(p,k)的一个的组合学解释是：将 p 个物体排成 k 个非空循环排列的方法数。

    递推公式：S(p,k)=(p−1)S(p−1,k)+S(p−1,k−1),1≤k≤p−1;S(p,0)=0,p≥1;S(p,p)=1,p≥0S(p,k)=(p−1)S(p−1,k)+S(p−1,k−1),1\leq k\leq p−1;S(p,0)=0,p\ge1;S(p,p)=1,p\ge0

    第二类斯特林数

    第二类斯特林数S(p,k)S(p,k)的一个的组合学解释是：将 p 个物体划分成 k 个非空不可辨别的（可以理解为盒子没有编号）集合的方法数。

    递推公式：S(p,k)=kS(p−1,k)+S(p−1,k−1),1≤k≤p−1;S(p,0)=0,p≥1;S(p,p)=1,p≥0S(p,k)=kS(p−1,k)+S(p−1,k−1),1\leq k\leq p−1;S(p,0)=0,p\ge 1;S(p,p)=1,p\ge0

    卷积形式：S(n,m)=1m!∑k=0m(−1)kC(m,k)(m−k)n=∑k=0m(−1)kk!(m−k)n(m−k)!S(n,m)=\frac{1}{m!}\sum_{k=0}^m(-1)^kC(m,k)(m-k)^n=\sum_{k=0}^m\frac{(-1)^k}{k!}\frac{(m-k)^n}{(m-k)!}

    同时有转化：xk=∑i=1ki!C(x,i)S(k,i)x^k=\sum_{i=1}^ki!C(x,i)S(k,i)

    斯特林近似公式

    n!≈2πn(ne)nn!\approx\sqrt{2\pi n}(\frac{n}{e})^n

    小球入盒模型通解

    k 个球 m 个盒子 空盒子 方案数
    各不相同 各不相同 允许 mkm^k
    各不相同 各不相同 无 m!Stirling2(k,m)m!Stirling2(k,m)
    各不相同 完全相同 允许 ∑i=1mStirling2(k,i)\sum_{i=1}^mStirling2(k,i)
    各不相同 完全相同 无 Stirling2(k,m)Stirling2(k,m)
    完全相同 各不相同 允许 C(m+k−1,k)C(m+k−1,k)
    完全相同 各不相同 无 C(k−1,m−1)C(k−1,m−1)
    完全相同 完全相同 允许 1(1−x)(1−x2)…(1−xm)的xk项的系数\frac{1}{(1−x)(1−x^2)…(1−x^m)}的x^k项的系数
    完全相同 完全相同 无 xm(1−x)(1−x2)…(1−xm)的xk项的系数\frac{x^m}{(1−x)(1−x^2)…(1−x^m)}的x^k项的系数

    置换

    使用示例

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

    struct Permutation : vector<int>
{
	Permutation(int n = 0) : vector<int>(n) {}
	friend Permutation operator*(const Permutation &f, const Permutation &g)
	{
		Permutation ans(f.size());
		for (int i = 0; i < f.size(); ++i)
			ans[i] = g[f[i]];
		return ans;
	}
	friend Permutation inv(const Permutation &f)
	{
		Permutation ans(f.size());
		for (int i = 0; i < f.size(); ++i)
			ans[f[i]] = i;
		return ans;
	}
	friend vector<vector<int>> cycle(const Permutation &f)
	{
		vector<int> vis(f.size(), 0);
		vector<vector<int>> ans;
		for (int i = 0; i < f.size(); ++i)
			if (!vis[i])
			{
				ans.push_back(vector<int>());
				for (int j = i; !vis[j]; j = f[j])
					vis[j] = 1, ans.back().push_back(j);
			}
		return ans;
	}
};

    生成字典序

    下一排列

    对给定的排列a1a2…ana_1a_2\dots a_n，找到aja_j使得aj<aj+1,aj+1>aj+2>⋯>ana_j<a_{j+1},a_{j+1}>a_{j+2}>\dots>a_n即这列数中最后一个相邻递增数对，然后把aj+1,aj+2,…,ana_{j+1},a_{j+2},\dots,a_n中大于aja_j的最小数放到位置 j，然后aj…ana_j\dots a_n中剩余的数从小到大排序放到[j+1,n][j+1,n]中。

    1
2
3
4
5
6
7
8
9
10
11

    bool nextPermutation(ll *b, ll *e) //标准库有这个函数next_permutation
{
	ll *i = e - 1, *j = e - 2;
	while (j >= b && *j >= *(j + 1))
		--j;
	if (j < b)
		return 0;
	while (*i <= *j)
		--i;
	return swap(*i, *j), reverse(j + 1, e), 1;
}

    二项式反演

    f(n)=∑k=0nC(n,k)g(k),g(n)=∑k=0n(−1)n−kC(n,k)f(k)f(n)=\sum_{k=0}^nC(n,k)g(k),g(n)=\sum_{k=0}^n(−1)^{n−k}C(n,k)f(k)

    第 k 小期望

    f(n,k)f(n,k)表示有 n 个变量，和为 1，第 k 小的期望。

    f(n,k)=1n2+(1−1n)f(n−1,k−1),f(n,0)=0f(n,k)=\frac{1}{n^2}+(1-\frac{1}{n})f(n-1,k-1),f(n,0)=0

    错排数

    考虑一个有 n 个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排 列的一个错排。

    n 个元素的错排数DnD_n满足递推公式：D1=0,D2=1,Dn=(n−1)(Dn−2+Dn−1)D_1=0,D_2=1,D_n=(n−1)(D_{n−2}+D_{n−1})

    通项：D(n)=n![(−1)22!+⋯+(−1)n−1(n−1)!+(−1)nn!]=⌊n!e+12⌋D(n)=n![\frac{(-1)^2}{2!}+\dots+\frac{(-1)^{n-1} }{(n-1)!}+\frac{(-1)^n}{n!}]=\lfloor\frac{n!}{e}+\frac{1}{2}\rfloor

    Bonuli 数

    使用示例

    Bn=−1C(n+1,n)(C(n+1,0)B0+C(n+1,1)B1+⋯+C(n+1,n−1)Bn−1)=−1n+1(C(n+1,0)B0+C(n+1,1)B1+⋯+C(n+1,n−1)Bn−1)B_n = -\frac{1}{C(n+1,n)}(C(n+1,0)B_0+C(n+1,1)B_1+\dots+C(n+1,n-1)B_{n-1})=-\frac{1}{n+1}(C(n+1,0)B_0+C(n+1,1)B_1+\dots+C(n+1,n-1)B_{n-1})

    可用于计算任意正整数次数的幂和：∑i=1nik=1k+1∑j=0kC(k+1,j)Bjnk+1−j\sum_{i=1}^ni^k=\frac{1}{k+1}\sum_{j=0}^kC(k+1,j)B_jn^{k+1-j}

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

    struct Bonuli : Factorial
{
	vector<ll> b;
	Bonuli(int N, ll M) : Factorial(N, M), b(N, 0)
	{
		for (int i = b[0] = 1; i < N; ++i)
		{
			for (int j = 0; j < i; ++j)
				b[i] = qadd(b[i], mul(b[j], c(i + 1, j)));
			b[i] = qadd(M, -mul(b[i], mul(fac[i], ifac[i + 1])));
		}
	}
	ll ask(ll n, int k)
	{
		ll r = 0, w = 1, u = add(n, 1);
		for (int i = 1; i <= k + 1; ++i)
			r = qadd(r, mul(mul(b[k + 1 - i], c(k + 1, i)), w = mul(w, u)));
		return mul(r, mul(fac[k], ifac[k + 1]));
	}
};

    Catalan 数

    h1=1,hn=4n−2n+1hn−1=C(2n,n)n+1=C(2n,n)−C(2n,n−1)h_1=1,h_n=\frac{4n−2}{n+1}h_{n−1}=\frac{C(2n,n)}{n+1}=C(2n,n)−C(2n,n−1)。

    在一个格点阵列中，从(0,0)(0,0)点走到(n,m)(n,m)点且不经过对角线x=yx=y的方法数：C(n+m−1,m)−C(n+m−1,m−1),x>y;C(n+m,m)−C(n+m,m−1),x≥yC(n+m−1,m)−C(n+m−1,m−1),x>y;C(n+m,m)−C(n+m,m−1),x\ge y。

    常见的 Catalan 数：括号序的个数、凸多边形三角剖分的方案数等。

    Bell 数

    把 n 个带标号的物品划分为若干不相交集合的方案数称为贝尔数，其递推公式：Bn=∑i=0N−1Cn−1iBiB_n=\sum_{i=0}^{N-1}C_{n-1}^iB_i

    前几项贝尔数：

    1,2,5,15,52,203,877,4140,21147,115975,678570,4213597,27644437,190899322,1382958545,...

    等价类容斥

    考虑容斥，Bell(p)枚举所有等价情况。对于一种情况，强制了一个等价类里面的数都要相同，其它的可以相同也可以不同。

    容斥系数为：(−1)p−等价类个数(每个等价类大小−1)!之积(−1)^{p−等价类个数}(每个等价类大小−1)!之积。

    Grey 码

    格雷序列第 i 个是i^(i>>1)。长为 n 的 01 序列共2n2^n个，下标从0…2n−10\dots 2^n-1。

    扩展 Cayley 公式

    对于 n 个点，m 个连通块的图，假设每个连通块有 a[i]个点，那么用 s−1 条边把它连通的方案数为ns−2a[1]a[2]…a[m]n^{s−2}a[1]a[2]\dots a[m]。

    超立方体

    n 维超立方体有2n−iC(n,i)2^{n−i}C(n,i)个 i 维元素。

    枚举位集 I 的非空子集 J

    1

    for(J=I; J; J=I&J−1) {}

    Related posts