加法和乘法原理

基本：

分类考虑加法原理。

分步考虑乘法原理。

排列组合

盒子与球都有标号。

$$A_n^m=n(n-1)(n-2)\dotsb (n-m+1)=\frac{n!}{(n-m)!}$$

盒子无标号，球有标号。

$$C_n^m=\frac{n(n-1)(n-2)\dotsb (n-m+1)}{m!}=\frac{n!}{m!(n-m)!}$$

组合相对于排列的区别就是去掉了顺序，对于 $n>m,{n \choose m}=0$。

$\color{red}{二项式定理}$

设 $n$ 是正整数，对一切 $x$ 和 $y$ 有：

$$(x+y)^n=\sum_{k=0}^n {n \choose m}x^ky^{n-k}\\ \Longrightarrow (ax+by)^n=\sum_{k=0}^n {n \choose m}a^k x^kb^{n-k}y^{n-k}$$

$\color{blue}{[NOIP2011 提高组] 计算系数}$

P1313 [NOIP2011 提高组] 计算系数

给定一个多项式 $(by+ax)^k$，已知 $a,b,k,n,m$ 请求出多项式展开后 $x^n\times y^m$ 项的系数。

$0\le k\le 1000$，$0\le n,m\le k$，$n+m=k$，$0\le a,b\le 10^6$。

结果就是 ${k \choose m}a^nb^m$，当且仅当 $n+m=k$。

组合数基本公式

$${n \choose m}={n-1 \choose m-1}+{n-1 \choose m} \tag{1}$$

$${n \choose m}={n\choose n-m}\tag{2}$$

$${n \choose m}={\frac{n}{k}}{n-1\choose k-1} \tag{3}$$

$$\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=\sum_{i=0}^n\binom{n}{i}=2^n\tag{4}$$

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

$${n+r+1 \choose r}=\sum_{i=0}^{r}{n+i \choose i} \tag{7}$$

证：

$${n+r+1 \choose r}={n+r \choose r}+{n+r \choose r-1}$$

$${n+r+1 \choose r}={n+r \choose r}+{n+r-1 \choose r-1}+{n+r-1 \choose r-2}$$

展开最后一项直至最后一项为 ${0 \choose -1}$ ,无意义为 $0$。

证毕

$${n \choose m}\times {m \choose r}={n\choose r}\times {n-r \choose m-r}\tag{8}$$

$$m\times {n \choose m}=n\times {n-1 \choose m-1}\tag{9}$$

证：

据上式 $r=1$ 得证

证毕

$${n+m \choose r}=\sum_{i=0}^r{n\choose i}\times {m \choose r-i}\tag{10}$$

证：

组合意义，分成 $n,m$，枚举一边，另一边对应。

证毕

$$\sum_{i=0}^ni\times {n\choose i}=n\times 2^{n-1}\tag{11}$$

证：

据
$m\times {n \choose m}=n\times {n-1 \choose m-1}$得

$$\sum_{i=0}^nn\times {n-1 \choose i-1}$$

$$n\times \sum_{i=0}^n {n-1 \choose i-1}$$

令 $i^{'}=i-1$，根据二项式定理

$$n\times \sum_{i=0}^n {n-1 \choose i-1} =n\times 2^{n-1}$$

则，

$$\sum_{i=0}^ni\times {n\choose i}=n\times 2^{n-1}$$

证毕

插板法

$x_1+x_2+x_3+x_4+x_n=k$ 的正整数解的组数。

${k-1 \choose n-1}$

$x_1+x_2+x_3+x_4+x_n=k$ 的非负整数解的组数。

${k-1+n \choose n-1}$

$x_1+x_2+x_3+x_4+x_n=k$ 满足 $x_i \ge a_i$的组数。

${k-1-\sum a_i +n \choose n-1}$

不相邻排列

$1 \sim n$ 这 $n$ 个自然数中选 $k$ 个，这 $k$ 个数中任何两个数都不相邻的组合有 $\binom {n-k+1}{k}$ 种。

P4071 [SDOI2016] 排列计数

求有多少种 $1$ 到 $n$ 的排列 $a$，满足序列恰好有 $m$ 个位置 $i$，使得 $a_i = i$。

思路1easy

思路2hard

离散与组合数学

多重集合

定义：多重集是指包含重复元素的广义集合。

多重集上的排列

多重集的排列数：

设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$ 表示由 $n_1$ 个 $a_1$，$n_2$ 个 $a_2$，…，$n_k$ 个 $a_k$ 组成的多重集，$S$ 的全排列个数为

$$\frac{n!}{\prod_{i=1}^kn_i!}=\frac{n!}{n_1!n_2!\cdots n_k!}$$

多重集的排列数常被称作 多重组合数，形如以下：

$$\binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{\prod_{i=1}^kn_i!}$$

e.g.$\dbinom{n}{m} \iff \dbinom{n}{m,n-m}$

多重集上的组合

错排列

令 $x=1,y=1$ , $\sum_{i=0}^{n}C_n^i=2^i$。

令 $x=1,y=-1$ , $\sum_{i=0}^{n}(-1)^i \times C_n^i=[n=0]$

假设存在两个函数 $f$，$g$。满足：

$$f_n=\sum_{i=0}^{n}C_n^i \times g_i$$

那么考虑如何反求得 $g_n$ 关于 $f_n$ 的等式。

$$g_n=\sum_{i=0}^{n}[n-i=0] \times C_n^i \times g_i\\ g_n=\sum_{i=0}^{n}\sum_{j=0}^{n-i}(-1)^j \times C_{n-i}^j \times C_n^i \times g_i\\ g_n=\sum_{i=0}^{n}\sum_{j=0}^{n-i}(-1)^j \times C_{n}^j \times C_{n-j}^i \times g_i\\ g_n=\sum_{j=0}^{n}(-1)^j \times C_n^j\sum_{i=0}^{n-j}C_{n-j}^i \times g_i\\ g_n=\sum_{i=0}^{n}(-1)^i \times C_n^i \times f_{n-i}=\sum_{i=0}^{n}(-1)^{n-i} \times C_n^i \times f_{i}$$

所以得到二项式反演的结论：

$$f_n=\sum_{i=0}^{n}C_n^i \times g_i\\ g_n=\sum_{i=0}^{n}(-1)^{n-i} \times C_n^i \times f_{i}\\$$

问题描述：

有 $n$ 个人编号为 $1, ..., n$ ，问这 $n$ 个人站成一排全都站错位置的方案数。

上述站错的定义是：第 $i$ 个人没有站在位置 $i$ 上。

方法1： 递推
设 $f_n$ 表示答案，假设现在考虑到了前 $i$ 个人的方案，即 $f_i$ 。

考虑第 $i$ 个人站位情况：

显然第 $i$ 个人的不能站在位置 $i$ ，假设他站到了位置 $k$ ，显然 $k\in[1,i-1]$ ，那么继续考虑 $k$ 的站位。

• $k$ 站到了位置i，那么剩下的 $i-2$ 个人仍然构成一个原问题，方案数为 $f_{i-2}$ 。

• $k$ 没站到位置i，也即 $k$ 不能站在位置 $i$ ，那么剩下的 $i-1$ 个人仍然构成一个原问题，方案数为 $f_i-1$ 。

所以可以得到 $f$ 的递推关系：

$$f_1=0\ , \ f_2=1\\f_i=(i-1) \times (f_{i-1}+f_{i-2})\ \ i≥3$$

方法2：二项式反演
设 $f_n$ 表示 $n$ 个人随便站位的方案数， $g_n$ 表示 $n$ 个人的都站错的方案数。

容易得到：

$$f_n=n!\\ f_n=\sum_{i=0}^nC_n^i \times g_i$$

直接二项式反演可以得到：

$$g_n=\sum_{i=0}^{n}(-1)^{n-i} \times C_n^i \times f_{i}\\$$

同样可以直接线性的递推出答案。

圆排列

$n$ 个人全部来围成一圈，所有的排列数记为 $\mathrm Q_n^n$。考虑其中已经排好的一圈，从不同位置断开，又变成不同的队列。
所以有

$$\mathrm Q_n^n \times n = \mathrm A_n^n \Longrightarrow \mathrm Q_n = \frac{\mathrm A_n^n}{n} = (n-1)!$$

由此可知部分圆排列的公式：

$$\mathrm Q_n^r = \frac{\mathrm A_n^r}{r} = \frac{n!}{r \times (n-r)!}$$

鸽巢原理/抽屉原理

反证法，构造题。

容斥原理

卡特兰

递推式

该递推关系的解为：

$$H_n = \frac{\binom{2n}{n}{n+1}}(n \geq 2, n \in \mathbf{N_{+}})$$

关于 Catalan 数的常见公式：

$$H_n = \begin{cases} \sum_{i=1}^{n} H_{i-1} H_{n-i} & n \geq 2, n \in \mathbf{N_{+}}\\ 1 & n = 0, 1 \end{cases}$$

$$H_n = \frac{H_{n-1} (4n-2)}{n+1}$$

$$H_n = \binom{2n}{n} - \binom{2n}{n-1}$$

路径计数问题。

所有子集复杂度

枚举 $S$ 的所有子集的子集的时间复杂度是 $O(3^n)$
考虑一种常见的枚举子集方式：

1
2

// s 是 u 的一个非空子集 
for (int s = u; s; s = (s - 1) & u)

显然单次枚举 $S$ 的一个子集是 $O(2^{|S|})$ 的。

复杂度证明：

$$O\left(\sum_{T\subseteq S}2^{|T|}\right)$$

不难发现，$S$ 中大小为 $l$ 的子集个数是 $\dbinom nl$，这是简单的组合数学知识。

转而枚举 $l$，于是原式就化为

$$O\left(\sum_{i=1}^n\dbinom ni 2^i\right)$$

根据二项式定理：

$$\begin{aligned} &=\sum_{i=1}^n \dbinom ni 2^i \\&=\sum_{i=1}^n \dbinom ni 2^i1^{n-i}\\ &=(1+2)^n-1\\ &=3^n-1\end{aligned}$$

于是，枚举 $S$ 的所有子集的子集的时间复杂度是 $O(3^n)$ 的。

证毕。

反演

反演：两个函数或者数列之间的双向（求和）关系

比如前缀和 $and$ 差分。

$f(n) = \sum_{i = 0}^ng(i)$ 就是前缀和

$g(n) = f(n) - f(n - 1)$ 就是差分

这一对关系就是双向的求和关系。

当然这么说的话，求导和积分也就是双向的关系，那么他们也是符合反演的。

定义 $A$ 为关系矩阵。

有 $f = g \times A$，也有 $g = f \times A^{-1}$。

二项式反演

形式一

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

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

形式二

$$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(n) = \sum_{i = n}(-1)^i\binom{i}{n}g(i)$$

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

形式四

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

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

这些形式都是非常对称的。

也就是说 $A[n, i] = (-1)^i\binom{n}{i}$ 是自逆的。

证：

$$(A * A) [d, t] = \sum_{i}A[d, i] A[i, t]$$

$$= \sum_{i = t}^d(-1)^i\binom{d}{i}(-1)^t\binom{t}{i}$$

$$= (-1)^t\sum_{i = t}^d(-1)^{i}\frac{d!i!}{i!(d - i)!t!(i - t)!}$$

$$= (-1)^t\sum_{i = t}^d(-1)^{i}\frac{d!(d - t)!}{(d - t)!(d - i)!t!(i - t)!}$$

$$\frac{d!}{t!(d - t)!} \cdot \frac{(d - t)!}{(d - i)!(i - t)!}$$

$$= \binom{d}{t} \cdot \binom{d - t}{d - i}$$

$$So:$$

$$= (-1)^t\binom{d}{t}\sum_{i = t}^d(-1)^i\binom{d - t}{d - i}$$

$$= (-1)^t\sum_{i = 0}^{d - t}(-1)^{i + t}\binom{d - t}{d - t - i}$$

$$= (-1)^t(-1)^t\binom{d}{t}\sum_{i = 0}^{d - t}(-1)^i\binom{d - t}{i}$$

$$= (-1)^t(-1)^t\binom{d}{t}(1 - 1)^{d - t}$$

$$= (-1)^{2t}\binom{d}{t}(1 - 1)^{d - t} = [d = t]$$

这里的 $(1 - 1)^0 = 0^0$ 为什么是 $1$？（反正当时我是有这个疑惑，记得文化课老师说不能是$1$，但并不知道凭啥不能是 $1$？这个说法到底对不对？？？）

有些人将 $0$ 不能是分母和这个的原因搞混了。 $0$ 不能是分母是因为其会使运算变得混乱，

而这个是不是 $1$ 都可以。

可能需要用到集合论的知识。

要证明$a^0 = 1$ 需要给出映射的定义：

1. $f$ 是 $X$ 和 $Y$ 的笛卡尔积的子集。

2. 对于任意 $x \in X$ ，存在一定的 $y \in Y$ ，使得 $(x, y) \in f$， 也就是常说的 $y = f(x)$，在集合论中对函数的定义是集合之间的映
   射关系。

定义基数：定义 $a^b$ 是由基数为 $b$ 到基数为 $a$ 的集合的映射全体所构成集合的基数。

考虑 $a^0$ 的情况，由一个空集到某一个基数为 $a$ 的集合的映射有多少个。答案是有一个，空映射。为什么空集可以形成映射？看第一条，空集满足了。

看第二条，空集也是满足的。因为数理逻辑里面讲（参考《离散数学》）若 $p$，则 $q$" 在 $p$ 是 $false$ 的时候，这个命题是恒真的。

为什么呢？可以举一个很形象的例子：人们常会说：“如果太阳打西边出来，那我就不姓$Y$ 。” 在这句话里面不管 “我” 姓不姓 $Y$，太阳都是

从东边出来的。也就是说这个 $p$ 对 $q$ 是没有什么影响的。并且在数理逻辑下，$p$ 和 $q$ 可以没有任何的内在联系，请和自然语言进行区分。

这里对 $a$ 并没有加以任何限制，也就是说 $a = 0$ 也是可以的，所以 $0^0 = 1$。

但这个又可以通过代数系统解释出：由于 $0$ 没有逆元，所以 $0^0$ 没有意义，或不存在。

莫比乌斯反演

克罗内克函数

$$\delta(x, y) = \begin{cases} & \text{1} \space\space x = y \\ & \text{0} \space\space \text{otherwise} \end{cases}$$

黎曼函数

$$\zeta(x, y) = \begin{cases} & \text{1} \space\space x \le x y \\ & \text(0) \space\space \text{otherwise} \end{cases}$$

这里的克罗内克函数和黎曼函数均为二变量函数。

当克罗内克函数和黎曼函数的第一个变量都为 $1$ 时，我们得出了完全积性函数$\varepsilon$ 和 $I$ 的定义。

$$So: \begin{cases} & \zeta(1, n) = I(n) \\ & \delta(1, n) = \varepsilon \end{cases}$$

$And:$

$\mu$ 是一个二变量函数 $\mu(x, y)$ ，定义为 $\zeta$ 的逆函数。

$\mu * \zeta = \delta$

$\sum_{x \le z \le y}\mu(x, z) = \delta(x, y)$

莫比乌斯反演定理：

$$G(x) = \sum_{z \le x} F(z) \Longrightarrow F(x) = \sum_{y \le x}G(y)\mu(y, x)$$

证明：

$$= \sum_{y \le x}\mu(y, x)\sum_{z \in X}\zeta(z, y)F(z)\\ = \sum_{z \in X}\sum_{y \le x}\mu(y, x)\zeta(z, y)F(z)\\$$

$$= \sum_{z \in X}\delta(z, x)F(z) = F(x)$$

在实际应用中常使用莫比乌斯函数的 $\mu(1, n)$ 的形式，缩写为 $\mu(n)$，当然你也可以说我们常用到的莫比乌斯函数是 $I$ 的逆函数 $I^{-1}$，大佬莫比乌斯将其命名为 $\mu$。

当然也可以通过这个了解 $\mu$ 取值的定义。

$So$ 也就有了这个：

$$F(n) = \sum_{d | n}f(d)$$

$$g(d) = \sum_{d | n}\mu(d)g(\frac{n}{d})$$

自然这个也可以通过$Dirichlet$ 卷积和积性函数来解释。

狄利克雷卷积 My blog。

由于这篇博客写的时间较早，可能无法谈到更深层的东西，还请见谅。

子集反演

$$g(S) = \sum_{T \subset S}f(T)$$

$$f(S) = \sum_{T \subset S}(-1)^{|S| - |T|} g(T)$$

（一眼看上去，感觉这玩意就纯抽象，比二项式反演还要抽象， 为啥要学这个玩意啊，草。）

证明：

$$\sum_{T \subset S}(-1)^{|S| - |T|}g(T)$$

$$= \sum_{T \subset S}(-1)^{|S| - |T|}\sum_{R \subset T}f(R)$$

$$= \sum_{R \subset S}f(R) \sum_{R \subset T \subset S}(-1)^{|S| - |T|}$$

当 $R = S$ ，可以得知 $\sum_{R \subset T \subset S} (-1)^{|S| - |T|} = 1$，否则任取 $a \in S - R$，$f : T \mapsto T \oplus {a}$ 是双射，故 $\sum_{R \subset T \subset S} (-1)^{|S| - |T|} = 0$

正好难算，至多好算： $f(S) = \sum_{T \subset S}g(T) \Longrightarrow g(S) = \sum_{T \subset S}(-1)^{|S| - |T|}f(T)$

正好难算，至少好算： $f(S) = \sum_{S \subset T}g(T) \Longrightarrow g(S) = \sum_{S \subset T}(-1)^{|T| - |S|}f(T)$

推广莫比乌斯函数：

$$\mu(S) = (-1)^{|S|}[S \space has \space no \space duplicate \space elements]$$

【莫比乌斯函数就是把整数当作质因数集合而来的反演系数！】

这个有点妙啊！

$$f(S) = \sum_{T \subset S}g(T) \Longrightarrow g(S) = \sum_{T \subset S} \mu(S - T)f(T)$$

$$f(S) = \sum_{S \subset T}g(T) \Longrightarrow g(S) = \sum_{T \subset S} \mu(T - s)f(T)$$

证明：

$\mu(A, A) = 1$

设 $B\ne A, \space p = |B| - |A|$

$$\mu(A, B)$$

$$= -\sum_{C: A \subseteq C \subset B} \mu(A, C)$$

$$= -\sum_{C: A \subseteq C \subset B}(-1)^{|C| - |A|}$$

$$= -\sum_{k = 0}^{p - 1}(-1)^k\binom{P}{k}$$

$$= -(-(-1)^p\binom{P}{P} + \sum_{k = 0}^p(-1)^k\binom{P}{k})$$

$$= (-1)^p\binom{P}{P}$$

$$= (-1)^{|B| - |A|}$$

—— 转载自$JLQ's Blog$

这也就是上面那样转化成立的原因。

求组合数

• 有模数
  • 模数小 $(Lucas)$
  • 预处理
• 无模数质因数分解

博弈论之NIM游戏

__END__