基础组合数学

标签：方案组合 sum 基础数学 binom left displaystyle 钦定

by TheBigYellowDuck

联赛前恶补知识点...

排列数 & 组合数

从 $n$ 元集合中选出 $m$ 个元素的有序排列数记为 $A_n^m$。计算公式为

\[\displaystyle A_n^m=n(n-1)(n-2)\cdots(n-m+1)=\dfrac{n!}{(n-m)!} \]

从 $n$ 元集合中选出 $m$ 个元素的无序排列数记为 $C_n^m$，一般也记作 $\dbinom{n}{m}$。计算公式为

\[\displaystyle \binom{n}{m}=\dfrac{n(n-1)(n-2)\cdots(n-m+1)}{1\times2\times3\times\cdots\times m}=\dfrac{n!}{m!(n-m)!} \]

组合数有一些很好的性质：

\[\displaystyle \binom{n}{m}=\binom{n}{n-m} \]

证明：考虑其组合意义。左式相当于在 $n$ 个元素中选择 $m$ 个的方案数，右式相当于在 $n$ 个元素中放弃 $n-m$ 个的方案数，两种方案数显然相等。

\[\binom{n}{k}=\dfrac{n}{k}\binom{n-1}{k-1} \]

证明：把阶乘形式的定义式写出来即证。

\[\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1} \]

证明：任取一个元素 $i$。若选择它，只需要在剩下的 $n-1$ 个元素中选择 $k-1$ 个。否则需要在剩下的 $n-1$ 个元素中选择 $k$ 个。根据组合数的定义即证。

上指标求和

\[\displaystyle \sum_{i=0}^n\binom{i}{x}=\binom{n+1}{x+1} \]

证明：结合杨辉三角。左边相当于在杨辉三角上选择从最上方开始的一列求和。可以把最上面的 $1$ 拿下来，连续求和能够得到右边。

\[\displaystyle \sum_{i=0}^n\binom{i+x}{i}=\binom{x+n+1}{n} \]

证明：结合杨辉三角。左边相当于在杨辉三角上选择从最左边开始的一条斜线求和。可以把最上面的 $1$ 拿下来，连续求和能够得到右边。

P1641 [SCOI2010] 生成字符串

折线法计数基础题。

考虑用总排列数减去不合法的排列数。我们将 $1$ 看成向量 $(1,1)$，$0$ 看成向量 $(1,-1)$，那么总排列数就是从 $(0,0)$ 走到 $(n+m,n-m)$ 的方案数。路径应该是一条折线。

注意到，合法的方案应该满足任意时刻折线都在 $x$ 轴上方。那么不合法的方案就要经过 $y=-1$ 这条直线。这就是经典的折线法了。

取第一次碰到 $y=-1$ 的时刻 $t$，将 $t$ 之前在 $y=-1$ 上方的直线对称下来，会发现这样的折线数量就是从 $(0,-2)$ 走到 $(n+m,n-m)$ 的方案数。

从 $(0,0)$ 走到 $(n+m,n-m)$ 的方案数为 $\dbinom{n+m}{n}$，而从 $(0,-2)$ 走到 $(n+m,n-m)$ 相当于把一步 $0$ 换成一步 $1$，从而方案数为 $\dbinom{n+m}{m-1}$。相减即为答案。

预处理组合数和逆元就好了。时间复杂度 $\mathcal{O}(n+m)$。

CF1204E Natasha, Sasha and the Prefix Sums

更厉害一点的折线法。

设最大值恰为 $x$ 的方案数为 $f(x)$，则答案为 $\sum x\times f(x)$。而恰好不是很好做，考虑设 $g(x)$ 为最大值 $\geq x$ 的方案数，则答案就是 $\sum g(x)$。

$\pm 1$ 交错的前缀问题，考虑经典折线法。将 $\pm 1$ 分别看成向量 $(1,\pm1)$，在二维平面上从 $(0,0)$ 开始走，最终会走到 $(n+m,n-m)$ 且轨迹是一条折线。$g(i)$ 就是轨迹碰到直线 $y=i$ 的折线数量。

如果起点和终点在 $y=i$ 的上下两侧，那么一定会经过。需要满足 $i\leq n-m$。则有

\[g(i)=\binom{n+m}{n} \]

取出第一次碰到 $y=i$ 的时刻 $t$，将 $t$ 之前的折线沿着 $y=i$ 对称，起点被换到 $(0,2i)$。只需要计算 $(0,2i)$ 走到 $(n+m,n-m)$ 的方案数。

设向上走了 $x$ 步，向下走了 $y$ 步，则有

\[\left\{ \begin{aligned} &n+m=x+y \\ &n-m=2i+x-y \end{aligned} \right. \]

解得 $x=n-i$，$y=m+i$。则有

\[g(i)=\binom{x+y}{x}=\binom{n+m}{n-i} \]

时间复杂度 $\mathcal{O}(n+m)$。

插板法

设当前有 $n$ 个相同的球和 $k$ 个不同的盒子，要将球全部放入盒子中：

盒子不可以为空。考虑用 $k-1$ 个隔板插入到 $n-1$ 个空隙中，自然分成 $k$ 组且每组非空。故方案数为$$\displaystyle \binom{n-1}{k-1}$$本质是求 $x_1+x_2+\cdots+x_k=n$ 的正整数解组数。
盒子可以为空。此时补上 $k$ 个球，做不可以为空的问题。再把补上的 $k$ 个球拿掉，自然可能产生空组。故方案数为$$\displaystyle \binom{n+k-1}{k-1}=\binom{n+k-1}{n}$$本质是求 $x_1+x_2+\cdots+x_k=n$ 的非负整数解组数。
第 $i$ 个盒子至少要放 $a_i$ 个球。先给每个盒子中扔进去 $a_i$ 个球，再做可以为空的问题，自然能够满足要求。故方案数为$$\displaystyle \binom{n-\sum a_i+k-1}{k-1}=\binom{n-\sum a_i+k-1}{n-\sum a_i}$$本质是求 $x_1+x_2+\cdots+x_k=n$ 其中 $x_i\geq a_i\geq 0$ 的非负整数解组数。

ARC110D Binomial Coefficient is Fun

记 $S=\sum a_i$。将 $S$ 个黑球排成一列，每组之间的 $n-1$ 个空隙中放上一块隔板。这样会产生 $n+S$ 个空隙。将不超过 $m-S$ 个白球插入到空隙之中，可以为空，求方案数。

考虑组合意义。令 $b_i$ 为同一组内黑球和白球的总和，容易说明这两个问题是等价的。则答案为

\[\sum_{i=0}^{m-S}\binom{i+n+S-1}{n+S-1}=\binom{n+m}{m-S}=\binom{n+m}{n+S} \]

发现 $n+S$ 大约是 $4\times 10^6$ 级别，直接摁算组合数即可。

时间复杂度 $\mathcal{O}(n+\sum a_i)$。

二项式定理

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

可以得到一些奇妙的结论：

\[\displaystyle \sum_{i=0}^n \binom{n}{i}=2^n$$令 $a=b=1$ 即证。这同时是在杨辉三角上一整行相加的结果。 \]
\[\displaystyle \sum_{i=0}^n (-1)^i\binom{n}{i}=[n=0]$$令 $a=-1,b=1$ 即证。在这里我们认为 $0^0=1$。 \]

多重组合数

将 $n$ 个不同元素分为 $k$ 个集合，使得第 $i$ 个集合中有 $a_i$ 个元素的方案数。记作$$\binom{n}{a_1,a_2,\cdots,a_k}=\dfrac{n!}{a_1!a_2!\cdots a_k!}$$
定义多重集 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$ 其中 $a_i$ 互不相同，$n_i$ 为 $a_i$ 的出现次数。

多重组合数也可以表示为多重集合的排列数。$S$ 的排列数为

\[\binom{\sum n_i}{n_1,n_2,\cdots,n_k} \]

~~不知道目前有什么用，但是既然有人讲过，就简单写一点。~~

容斥原理

设全集 $U$ 总的元素有 $n$ 种不同属性，拥有第 $i$ 种属性的元素构成集合 $S_i$，则有

\[\displaystyle \left|\bigcup_{i=1}^n S_i\right|=\sum_{m=1}^n (-1)^{m-1}\sum_{a_i<a_{i+1}} \left|\bigcap_{i=1}^m S_{a_i}\right| \]

集合的交可以用全集减去集合的补集的并。

\[\left|\displaystyle \bigcap_{i=1}^n S_i\right|=|U|-\left|\bigcup_{i=1}^n \overline {S_i}\right|=|U|+\sum_{m=1}^n (-1)^{m}\sum_{a_i<a_{i+1}} \left|\bigcap_{i=1}^m \overline{S_{a_i}}\right| \]

容斥原理给我们一些反向求解的思路。有些时候，满足条件是困难的，而不满足条件是简单的，就可以考虑容斥原理。

错排公式

对于 $1\sim n$ 的排列 $p$，如果任意 $p_i\neq i$，则称 $p$ 为 $n$ 的一个错排。

记 $D_n$ 为 $n$ 的错排数。可以用容斥原理计算。

先进行容斥建模。

令全集 $U$ 为 $1\sim n$ 的排列构成的集合，每个元素即为一个排列。
每个元素的第 $i$ 种属性即为 $p_i\neq i$。
记 $S_i$ 为满足 $p_i\neq i$ 的排列构成的集合。

则有$$D_n=\left|\displaystyle \bigcap_{i=1}^n S_i\right|=|U|-\left|\bigcup_{i=1}^n \overline {S_i}\right|=n!-\left|\bigcup_{i=1}^n \overline {S_i}\right|$$
其中 $\overline {S_i}$ 即为钦定 $p_i=i$ 的排列数。也就是说，除了第 $i$ 位上有要求，其他位置不限。

考虑计算钦定 $k$ 个位置上满足 $p_i=i$ 的排列总数。我们要先选出这 $k$ 个位置，剩下的 $n-k$ 个位置可以任意排布，故有

\[\sum_{a_i<a_{i+1}}\left|\bigcap_{i=1}^k \overline {S_{a_i}}\right|=\binom{n}{k}(n-k)!=\dfrac{n!}{k!} \]

乘以充斥系数

\[\left|\bigcup_{i=1}^n \overline {S_i}\right|=\sum_{k=1}^n (-1)^{k-1}\sum_{a_i<a_{i+1}}\left|\bigcap_{i=1}^k \overline {S_{a_i}}\right|=n!\sum_{k=1}^n \dfrac{(-1)^{k-1}}{k!} \]

故最终答案为

\[D_n=n!-n!\sum_{k=1}^n \dfrac{(-1)^{k-1}}{k!}=n!\sum_{k=0}^n\dfrac{(-1)^k}{k!} \]

同时，错排数存在递推公式

\[D_n=(n-1)(D_{n-1}+D_{n-2}) \]

以及

\[D_n=nD_{n-1}+(-1)^n \]

二项式反演

\[f(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}g(i)\Longleftrightarrow g(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}f(i)$$可以由多步容斥的过程推得。 \]
考虑其组合意义。记 $f(n)$ 表示至多 $n$ 个的方案数，$g(n)$ 表示恰好 $n$ 个的方案数。则对于任意 $i\leq n$，需要先选出 $i$ 个元素，所以 $g(i)$ 会在 $f(n)$ 中会被计算 $\dbinom{n}{i}$ 次。

如果“恰好”不容易而“不超过”容易，可以处理“不超过”，用上式推出“恰好”。
\[f(n)=\sum_{i=n}^m\binom{i}{n}g(i)\Longleftrightarrow g(n)=\sum_{i=n}^m(-1)^{i-n}\binom{i}{n}f(i)$$这是最常用的二项式反演的形式。证明可以暴力代入。考虑其组合意义。记 $f(n)$ 表示**钦定** $n$ 个的方案数，$g(n)$ 表示**恰好** $n$ 个的方案数。则对于任意 $i\geq n$，由于钦定方式不同，所以 $g(i)$ 在 $f(n)$ 中会被计算 $\dbinom{i}{n}$ 次。如果“恰好”不容易而“钦定”容易，可以处理“钦定”，用上式推出“恰好”。 \]

P6076 [JSOI2015] 染色问题

给定 $n\times m$ 的网格图和 $c$ 种颜色，求满足下列条件的染色方案数：

每个格子可以染一种颜色，也可以不染。

每一行至少有一个格子被染色。

每一列至少有一个格子被染色。

每种颜色至少被使用一次。

数据范围：$n,m,c\leq 400$。

每种颜色都至少使用一次是不容易满足的，而去掉这项条件就可以随便染色。考虑由”恰好“转化为“不超过”，通过二项式反演求解。

令 $f(i)$ 表示使用不超过 $i$ 种颜色满足其他条件的染色方案数，$g(i)$ 表示使用恰好 $i$ 种颜色满足其他条件的染色方案数。则有

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

继续对行列容斥。类似地，令 $h(i)$ 表示选择不超过 $i$ 列染色的方案数。对于任意 $x$ 都可以将 $f(x)$ 理解为在恰好 $m$ 列上染色。则有

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

在给定的 $i$ 列上用 $x$ 种颜色染色，每一行都必须要染一个格子，列没有限制。从而

\[h(i)=\left((x+1)^i-1\right)^n \]

代入 $f(x)$ 的表达式中

\[f(x)=\sum_{i=0}^m (-1)^{m-i}\binom{m}{i}\left((x+1)^i-1\right)^n \]

代入 $g(c)$ 的表达式中

\[g(c)=\sum_{i=0}^c(-1)^{c-i}\binom{c}{i}\sum_{j=0}^m(-1)^{m-j}\binom{m}{j}\left((i+1)^j-1\right)^n \]

整理一下

\[g(c)=\sum_{i=0}^c \sum_{j=0}^m (-1)^{m+c-i-j}\binom{c}{i}\binom{m}{j}\left((i+1)^j-1\right)^n \]

预处理组合数，暴力计算即可。

时间复杂度 $\mathcal{O}(mc\log (mn))$。

P5505 [JSOI2011] 分特产

给定 $m$ 种不同颜色的球，第 $i$ 种颜色有 $a_i$ 个，求将这些球放入 $n$ 个不同盒子的方案数。

盒子不能为空。

数据范围：$n,m,a_i\leq 1000$。

盒子不能为空很难满足，而盒子可以为空就可以随便放。不妨理解为恰好 $0$ 个盒子为空。

令 $f(x)$ 表示钦定 $x$ 个盒子为空的方案数。先选出 $x$ 个盒子，对于每种颜色在剩下的 $n-x$ 个盒子里做插板法即可。从而有

\[\displaystyle f(x)=\binom{n}{x}\prod_{i=1}^m\binom{n-x+a_i-1}{a_i} \]

令 $g(x)$ 表示恰好 $x$ 个盒子为空的方案数，套二项式反演的形式二。

\[g(x)=\sum_{i=x}^n (-1)^{i-x} \binom{i}{x} f(i)=\sum_{i=x}^n (-1)^{i-x} \binom{i}{x}\binom{n}{i}\prod_{j=1}^m\binom{n-i+a_j-1}{a_j} \]

答案就是

\[g(0)=\sum_{i=0}^n (-1)^i\binom{n}{i}\prod_{j=1}^m\binom{n-i+a_j-1}{a_j} \]

预处理组合数暴力算就可以了。

时间复杂度 $\mathcal{O}(nm)$。

P4859 已经没有什么好害怕的了

给定两个长度为 $n$ 的序列 $A,B$。保证这 $2n$ 个数互不相同。

现在要将两个序列中的元素两两配对，形成 $n$ 个数对 $(A_i,B_i)$。求使得 $A_i>B_i$ 的对数比 $A_i<B_i$ 的对数恰好多 $k$ 的方案数。

数据范围：$n\leq 2000$，$0\leq k\leq n$。

观察到 $A_i>B_i$ 的对数是确定的。记 $m=\dfrac{n+k}{2}$，则需要求出恰好 $m$ 对满足要求的方案数。

仍然是考虑钦定。不妨先对 $A$ 先排序，设 $dp(i,j)$ 表示考虑 $A$ 的前 $i$ 小的元素，钦定 $j$ 个满足要求的数对的配对方案数，即不考虑未配对的位置。

设 $cnt_i$ 表示小于 $A_i$ 的 $B_j$ 的个数，转移只需要枚举 $A_i$ 是否配对。故有

\[\displaystyle dp(i,j)=dp(i-1,j)+dp(i-1,j-1)\times (cnt_i-(j-1)) \]

设 $f(i)$ 表示钦定 $i$ 个满足要求的数对的总方案数，即需要给未配对位置配对。故有

\[f(i)=dp(n,i)\times (n-i)! \]

设 $g(i)$ 表示恰好 $i$ 个满足要求的数对的总方案数。代入二项式反演的形式二。

\[\displaystyle g(m)=\sum_{i=m}^n (-1)^{i-m}\binom{i}{m}f(i)=\sum_{i=m}^n (-1)^{i-m}\binom{i}{m}(n-i)!\times dp(n,i) \]

预处理组合数，暴力 dp 代式子求解即可。

时间复杂度 $\mathcal{O}(nk)$。需要注意边界情况 $dp(i,0)=1$。

P6478 [NOI Online #2 提高组] 游戏

小 A 和小 B 正在玩一个游戏：有一棵包含 $n=2m$ 个点的有根树，它的根是 $1$ 号点，初始时两人各拥有 $m$ 个点。游戏的每个回合两人都需要选出一个自己拥有且之前未被选过的点，若对手的点在自己的点的子树内，则该回合自己获胜；若自己的点在对方的点的子树内，该回合自己失败；其他情况视为平局。游戏共进行 $m$ 回合。

对于 $k=0,1,2,\cdots,m$，计算出非平局回合数为 $k$ 的情况数。两种情况不同当且仅当存在一个小 A 拥有的点 $x$，小 B 在 $x$ 被小 A 选择的那个回合所选择的点不同。对 $998244353$ 取模。

数据范围：$n\leq 5000$。

翻译一下，我们要在异色点之间钦定 $m$ 对关系，使得有祖先后代关系的数对恰为 $k$。求方案数。

恰好是困难的，钦定是简单的。经典套路，树形 dp 做钦定，二项式反演转恰好。

设 $dp(u,j)$ 表示以 $u$ 为根的子树中钦定了 $j$ 对祖先关系，且只考虑钦定点对的方案数。不钦定 $u$ 的转移可以做背包合并，钦定 $u$ 就从子树中找一个异色点和 $u$ 构成一对。统计一下子树大小和子树内两种颜色的节点个数就可以转移了。

设 $f(i)$ 为钦定 $i$ 对祖先关系，且考虑全部点对的方案数。则有

\[f(i)=dp(1,i)\times \left(m-i\right)! \]

令 $g(i)$ 为恰好 $i$ 对祖先关系，且考虑全部点对的方案数。代入二项式反演的形式二

\[g(x)=\sum_{i=x}^m(-1)^{i-x}\dbinom{i}{x}f(i) \]

时间复杂度 $\mathcal{O}(n^2)$。

斯特林数

第二类斯特林数 $\displaystyle {n\brace k}$，也记作 $S(n,k)$，表示将 $n$ 个两两不同的元素划分成 $k$ 个互不区分的非空子集的方案数。

第二类斯特林数的递推式为

\[\displaystyle {n\brace k}={n-1\brace k-1}+k\times{n-1\brace k} \]

边界是 $\displaystyle {n\brace 0}=[n=0]$。

用组合意义证明。当加入一个新元素时，可以单独作为一个子集，也可以加入现有的一个子集。

第二类斯特林数的通项公式为

\[\displaystyle {n\brace k}=\sum_{i=0}^k\dfrac{(-1)^{k-i}i^n}{i!(k-i)!} \]

用容斥原理证明。设 $g(i)$ 为将 $n$ 个不同元素划分到 $i$ 个不同的集合的方案数，$f(i)$ 为将 $n$ 个不同元素划分到 $i$ 个不同的非空集合的方案数。则有

\[g(i)=i^n=\sum_{j=0}^i\dbinom{i}{j}f(j) \]

由二项式反演的形式二

\[\begin{aligned} f(i)&=\sum_{j=0}^i (-1)^{i-j}\dbinom{i}{j}g(j) \\ &=\sum_{j=0}^i\dfrac{i!(-1)^{i-j}j^n}{j!(i-j)!} \\ \end{aligned} \]

考虑 $f(i)$ 与 $\displaystyle {n\brace i}$ 的关系，斯特林数要求集合互不区分，从而

\[f(i)={n\brace i}i! \]

代回即证。

第二类斯特林数在用来表示幂时有如下式子，一些需要拆幂和的时候会用到。

\[x^n=\sum_{i=0}^x\dbinom{x}{i}{n\brace i}i! \]

标签：方案,组合,sum,基础,数学,binom,left,displaystyle,钦定
From： https://www.cnblogs.com/duckqwq/p/18132092