一些简单的组合计数知识。

组合计数入门

一、组合数

1.性质

（1）二项式定理

二项式定理：

(a+b)^n=\sum_{i=0}^n \binom{n}{i}a^ib^{n-i}

同理可得：

(1+x)^n=\sum_{i=0}^n\binom{n}{i}x^i

可以得出 $C_n^m$ 就是 $(1+x)^n$ 中 $x^m$ 的系数。

（2）组合恒等式

\binom{n}{m}=\binom{n}{n-m}

\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}

上面是 杨辉三角 的递推式

\sum_{i=0}^n\binom{n}{i}=2^n

每个数都有选或不选两种情况，根据乘法原理，得出 $2^n$ 。

2021.3.1更新：今天数学上的集合中，一个集合所有子集数就是 $2^n$ 可由上面的式子得证。

\sum_{i=0}^n(-1)^i\binom{n}{i}=[n=0]

\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}

2021.4.11更新：这玩意叫 范德蒙恒等式。

\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}

\sum_{i=0}^ni\binom{n}{i}=n2^{n-1}

\sum_{i=0}^ni^2\binom{n}{i}=n(n+1)2^{n-2}

\sum_{i=0}^n\binom{i}{k}=\binom{n+1}{k+1}

\binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k}

2.计算方法

（1） $ExLucas$

当 $n,m$ 很大且 $p$ 不一定是质数时，要考虑用 $ExLucas$ 求解。

先将模数 $p$ 分解质因数成 $p_0^{k_0}p_1^{k_1}...$ 的形式。

再计算所有的 $\binom{n}{m} \ mod \ p_i^{k_i}$ ，再用 $CRT$ 合并。

回归本源 $\binom{n}{m}=\frac{n!}{m!(n-m)!}(mod \ p)$ ，考虑计算除法要逆元，但是除数与模数不互质的情况下是不存在逆元的，所以可以考虑先将除数和被除数中的 $p$ 都提出。

再考虑如何求阶乘：递归、循环节

二、卡特兰数

1.定义

卡特兰数满足以下递推关系：

C_0=1,C_1=1,C_{n+1}=\sum_{i=0}^nC_iC_{n-i}

在一个坐标系中，从原点出发，每次可以向 $x$ 轴或 $y$ 轴正方向移动一个单位，且移动过程中不可以到直线 $y = x$ 的上方，移动到 $(n, n)$ 的移动方案数就是 $C_n$ 。

由上述定义可得：

C_n=\binom{2n}{n}-\binom{2n}{n+1}=\frac{\binom{2n}{n}}{n+1}=\frac{\prod\limits_{i=n+2}^{2 \times n}i}{\prod\limits_{i=1}^{n}i}

2.性质

$C_n$ 等于以下方案数：

（1） $n$ 对括号的合法配对方案数。

（2） $n$ 个节点的二叉树的形态数。

（3） $n + 1$ 个叶子（ $n$ 个非叶节点）的满二叉树的形态数, 走到左儿子 $+1$ , 走到右儿子 $−1$ , 类似于括号匹配。（大致同 $2$ ）

（4） $n$ 个数入栈后出栈的排列总数。

（5）对凸 $n + 2$ 边形进行不同的三角形分割的方案数。（分割线断点仅为顶点，且分割线仅在顶点上相交）

（6） $n$ 层的阶梯切割为 $n$ 个矩形的切法数。

3.规律

OEIS A000108

$0$	$1$	$2$	$3$	$4$	$5$	$6$
$1$	$1$	$2$	$5$	$14$	$42$	$132$

4.例题

UVA10157 Expressions

这是卡特兰数的一种常见模型：括号匹配的方案数。其实直接推 dp 式子也可以推出来卡特兰数。考虑已经确定了一对括号，形如 $(\cdots)\cdots$ ，考虑括号内和括号外的情况，直接转移即可。本题还多了个深度的限制，加一个维度即可。注意高精。

UVA991 Safe Salutations

~~看到 4 时答案为 14 直接卡特兰数~~。还是先考虑确定了一条连线的情况，然后左右两边分类即可。

UVA10223 How many nodes ?

这也是卡特兰数的一种模型：二叉树的生成个数。给一个整数 $n$ ，问多少节点可以产生 $n$ 个不同的二叉树。

P1044 [NOIP2003 普及组] 栈

卡特兰数的模型： $n$ 个数入栈后出栈的排列总数。

三、康托展开

1.定义

康托展开是一个全排列到一个自然数的双映射，常用于构建哈希表的空间压缩。康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

简单来说对于一个排列，我们可以通过泰勒展开求出这个排列在所有排列中的排名。（例如一个长度为 $5$ 的排列，那么 $1 \ 2 \ 3 \ 4 \ 5$ 是第 $0$ 个， $1 \ 2 \ 3 \ 5 \ 4$ 是第 $1$ 个）

PS:

康托展开是从0开始的。

rank=\sum_{i=1}^na_i \cdot (i-1)!

其中的 $a_i$ 为在第 $i$ 个数后面小于第 $i$ 个位置上的数的个数，即

a_i=\sum_{j=1}^{i-1}[q_j<q_i]

(其中 $q$ 为给出的序列)

2.逆康托展开

考虑如何将 $rank$ 转化为 $a$ 。可以得出 $(n-1)!>\sum_{i=1}^{n-1}a_i \cdot (i-1)!$ ，所以可以得出

rand \ mod \ (n-1)!=\sum_{i=1}^{n-1}a_i \cdot (i-1)!

\lfloor \frac{rank}{(n-1)!} \rfloor = a_1

于是可以用一个简单的循环计算出 $a$ 。

考虑将 $a$ 变回 $q$ 。

显然 $q_1 = a_1 + 1$ ，既然已经得到了 $q_1$ ，那么后面的数显然不可能为 $q_1$ ，所以可以维护一个集合，集合中开始有 $1 ∼ n$ 中所有的整数，计算每一个 $a_i$ 时就从集合中拿出第 $q_i + 1$ 大的数，将拿出的数从集合中删去，依次操作即可还原出 $q$ 。（可能需要一定的数据结构基础）

3.代码实现（2021.3.1 更新）

（1）康托展开（树状数组）

#include<cstdio>
#define LL long long
const int MOD=998244353;
int N,a[1000003],c[1000003],l[1000003];
LL fac[1000003],ans;
void add(int x,int k)
{
	while(x<=N)
	{
		c[x]+=k;
		x+=l[x];
	}
}
int sum(int x)
{
	int t=0;
	while(x>0)
	{
		t+=c[x];
		x-=l[x];
	}
	return t;
}
int main()
{
	scanf(" %d",&N);
	fac[0]=1;
	for(int i=1;i<N;++i)
	{
		fac[i]=fac[i-1]*i%MOD;
		l[i]=i&-i;
	}
	l[N]=N&-N;
	for(int i=1;i<=N;++i)add(i,1);
	for(int i=1;i<=N;++i)
	{
		scanf(" %d",&a[i]);
		ans=(ans+((sum(a[i])-1)*fac[N-i])%MOD)%MOD;
		add(a[i],-1);
	}
	printf("%lld\n",ans+1);
	return 0;
}

（2）逆康托展开（线段树）

#include<cstdio>
using namespace std;

const int N=4e6;
int pos,t[N],n;

void pushup(int root)
{
	t[root]=t[root<<1]+t[root<<1|1];
}

void build(int root,int l,int r)
{
	if(l==r)
	{
		t[root]=1;
		return;
	}
	int mid=l+((r-l)>>1);
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	pushup(root);
}

int query(int root,int l,int r,int k)
{
	t[root]--;
	if(l==r)
		return l;
	int mid=l+((r-l)>>1);
	if(t[root<<1]>=k)
		return query(root<<1,l,mid,k);
	else
		return query(root<<1|1,mid+1,r,k-t[root<<1]);
}

int main()
{
	scanf("%d",&n);
	build(1,1,n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&pos);
        printf("%d ",query(1, 1, n, pos + 1));
	}
	return 0;
}

四、容斥

1.定义

\left | \bigcup_{i=1}^{ \left | S \right | }S_i \right |=\sum_{T \subseteq S}(-1)^{\left | T \right | +1} \left | \bigcap_{a \in T}a \right |

通过这个公式就可以在只能直接计算交集，不能直接计算并集的时候可以计算出并集的大小。

2.二项式反演

如果对于任意的自然数 $n$ 存在

f(n)=\sum_{i=0}^n \binom{n}{i} g(i)

那么得到以下结论

g(n)=\sum_{i=0}^n(-1)^{n-i} \binom{n}{i}f(i)

在具体的题目中， $f(i)$ 一般是指至少（至多）选 $i$ 个的方案数， $g(i)$ 是指恰好选 $i$ 个的方案数。

二项式反演存在另一形式：

如果对于任意的自然数 $n$ 存在

f(k)=\sum_{i=k}^n \binom{i}{k} g(i)

那么得到以下结论

g(k)=\sum_{i=k}^n(-1)^{k-i} \binom{i}{k}f(i)

3.min-max容斥

\max \ S=\sum_{T \subseteq S}(-1)^{\left | T \right |+1}\min \ T

(把 $\max$ 变为 $\min$ ， $\min$ 变为 $\max$ 也成立)

通过这个公式可以在 $\min$ 和 $\max$ 间转换。

感性认知一下这个式子。

设 $a_i$ 为 $S$ 中第 $i$ 大的数（ $a_1$ 为最大值，也就是说序列从大到小排），那么对于 $a_i$ 为最小值的的集合的个数为 $2^{i-1}$ 。（只能选比 $a_i$ 大的数，比 $a_i$ 大的数的个数为 $i − 1$ ，每个数优选与不选两种情况，自然 $2^{i-1}$ 种选法）

把 $2^{i-1}$ 用二项式定理展开后为 $\sum_{j=0}^{i-1} \binom{i-1}{j}$ ，假设容斥系数为 $f(j)$ ，那么需要构造出

\sum_{j=0}^{i-1}\binom{i-1}{j}f(j)=[i=1]

可以发现这个与组合恒等式中的 $\sum_{i=0}^n(-1)^i\binom{n}{i}=[n=0]$ 非常相似，所以可以得到 $f(j)$ 为 $(-1)^j$ 。再经过简单整理后就可以得到 $\min - \max$ 容斥的公式。

举个例子， $S=\{1,2,3\}$ ，我们要求 $S$ 中的最大值。 $S$ 所有的子集为 $\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}$ ，按照上面的公式我们就可以将所有的除最大值之外的所有值消去，只留下最大值 $3$ 。

五、奇怪的排列

1.不相邻的排列

从 $1 ∼ n$ 中选出 $k$ 个不同元素，并且如果选择了 $a$ ，那么 $a + 1$ 就不能选择。求不同的选择方案数。

假如说选择的数从小到大为 $a_1,a_2,...,a_k$ ，对于任意 $i\in[1,n)$ 要满足 $a_i+1 \ne a_{i+1}$ ，所以可以在选择 $a_i$ 的同时把 $a_i + 1$ 拿走，也就是忽略掉 $a_i+1$ ，，这样没有被忽略的数的个数就变成了 $n − k + 1$ ，所以答案就 $\binom{n-k+1}{k}$ 。

2.错位排列

一个排列 $a$ 是错位排列是指对于任意的 $a_i \ne i$ 。

求有多少不同的长度为 $n$ 的排列是错位排列。

可得递推式：

d_1=0,d_2=1,d_i=(i-1)(d_{i-1}+d_{i-2}) (i>2)

六、计数原理

1.加法原理

（1）例题：

UVA11401 Triangle Counting

考虑最长边 $x$ ，有 $y+z > x $，变形为 $x - y < z < x$ ，然后发现有 $\frac{(x-1)(x-2)}{2}$ ，然后 $y=z$ 不符合条件，减去 $\frac{x-2}{2}$ ，结果为 $\frac{(x-2)^2}{4}$ 。

UVA11480 Jimmy's Balls

题意：

求 $a+b+c = n$ 且 $a>b>c$ 的方案数。

思路:

还是考虑 $a$ 最大，然后 $b+c=n-a$ ，显然有 $(n-a)/2$ 种，注意奇偶性。

Creator's World