数论——组合数学入门

排列组合

排列就是指从给定个数的元素中取出指定个数的元素进行排序；组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。--------OI Wiki

乘法原理和加法原理

加法原理，就好比一个工作，有 \(n\) 个解决的方案，第 \(i\) 项方案有 \(a_{i}\) 种不同的实现方式，所以这个工作有 \(a_{1}+a_{2}+a_{3}+\ldots+a_{n}\) 种方式来解决。

乘法原理，就好比一个工作，有 \(n\) 个步骤，第 \(i\) 步有 \(a_{i}\) 种方法来完成，所以这个工作的方式有 \(a_{1}\times a_{2}\times a_{3}\times \ldots \times a_{n}\) 种方式来解决。

排列数

给定 \(n\) 个数，从中选取 \(m\) 个数形成一个排列，可能的排列的数量，用 \(A_{n}^{m}\) 来表示（给定的数都为正整数）。

排列的计算公式：

\[A_{n}^{m}=n\times (n-1)\times (n-2)\times \ldots \times (n-m+1)=\frac{n!}{(n-m)!},n,m\in \mathbb{N^{*}}，m\le n \]

其实就是分子分母同乘一个 \((n-m)!\)。

其中 \(n!=1\times 2\times 3\times \ldots \times n\)。

全排列就是当 \(n=m\) 的时候的一种特殊情况，此时 \(A_{n}^{n}=n!\)。

组合数

区别就是，排列数是要求顺序的，而组合数是从 \(n\) 个元素里面选取 \(m\) 个数组成一个集合，问有多少种可能，通常用 \(C_{n}^{m}\) 来表示。

组合数计算公式：

\[C_{n}^{m}=\frac{n!}{m!(n-m)!} \]

可以发现只比排列的公式分母多了一个 \(m!\)，因为不考虑顺序，所以可以想到，挑出来的 \(m\) 个元素组成的集合，里面的排列数是 \(m!\)，而这里面的元素组成的集合都是相同的，也就是这 \(m\) 个数本来应该算一个，但是排列里面是算了 \(m!\)，所以排列的公式除以 \(m!\) 即为我们要求的答案。

现在人们习惯用 \(\binom{n}{m}\) 表示 \(n\) 个元素里面选 \(m\) 个，但是我个人觉得不如用 \(C_{n}^{m}\) 直观，但我们还是要了解这个表示方式。

插板法

为什么叫插板法呢，因为他是用于解决把一些相同种类的元素分成不同的几组的一种方式， \(n\) 个元素分成 \(k\) 组，每一组至少有一个元素，就相当于拿 \(k-1\) 个板子放到 \(n-1\) 个空里，故因此而得名。

因为元素是完全相同的，所以我们根据上面的组合数可以得出公式：

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

本质是求 \(x_{1}+x_{2}+\ldots +x_{k}=n\) 的正整数解的组数。

改一下题目，如果要是允许有空的组呢？

如果这样的话，直接插板是不行的，因为有可能出现一堆板子都插到一个空隙里，这样的话求组合数就是错误的了。

所以我们先借来 \(k\) 个元素，在这 \(n+k-1\) 个空隙里插板，保证我们的每一组里面都是至少有 \(1\) 个元素，这样我们就把这个问题转化成了上一个问题，我们也可以得出公式：

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

可以想象一下，我们是先借了 \(k\) 个元素来保证我们的每一组里面都至少有一个元素，那么我们就按照第一个问题一样求解，最后把所有的板子都拿走，那么答案是不会有所变化的。

本质上是求 \(x_{1}+x_{2}+\ldots +x_{k}=n\) 的非负整数解的组数。

我们来加一些限制：如果说对于第 \(i\) 组我们需要至少分到 \(a_{i}\) 个元素，\(\sum a_{i}\le n\)，我们又该怎么去求解呢？

和上面一样，本质上就是求 \(x_{1}+x_{2}+\ldots+x_{k}=n，x_{i}\ge a_{i}\) 的解的组数。

我们浅想一下，设 \(x_{i}'=x_{i}-a_{i}\)，所以 \(x_{i}=x_{i}'+a_{i}\)，那么我们要求的就是：

\[(x_{1}'+a_{1})+(x_{2}'+a_{2})+\ldots+(x_{k}'+a_{k})=n \]

\[x_{1}'+x_{2}'+\ldots +x_{k}'=n-a_{1}-a_{2}-\ldots-a_{k} \]

\[x_{1}'+x_{2}'+\ldots +x_{k}'=n-\sum a_{i} \]

那么我们知道 \(x_{i}'\) 是一个非负的整数，所以我们可以直接用问题二的公式：

\[\binom{n-\sum a_{i}+k-1}{n-\sum a_{i}} \]

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

二项式定理

二项式就是由两项组成的式子，比如 \(2x\) 是一项式，\(2x+3y\) 是二项式，\(2x+3y+4z\) 是三项式，以此类推。

主要是用来解决 \((a+b)^{n}\) 的完全展开式的问题，其实是有规律可循的，我们可以通过这个定理快速获得第 \(i\) 项。

举一个最常见的例子：初中的完全平方公式 \((a+b)^{2}=a^{2}+2^{ab}+b^{2}\)。

或者高中的完全立方公式 \((a+b)^{3}=a^{3}+3a^{2}b+3ab^{3}+b^{3}\)。

相信你已经发现了他们系数的规律，那就是杨辉三角，其实就是用来解释 \((a+b)^{n}\) 的各项的系数才有的杨辉三角，这个东西很奇妙，我们后面会提到他和组合数的关系。

公式就是

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

为什么呢，你可以考虑一下，我们在推导完全立方公式的时候，我们是一项一项暴力拆开成 \(n\) 个 \((a+b)\) 相乘然后拆开合并的同类项，那么我们暴力拆一下可以知道，每一项都是从 \(n\) 个 \((a+b)\) 中选 \(a\) 或者 \(b\) 相乘得到的，也就是说，我们可以把展开后的第 \(i\) 项看作是选了 \(i\) 个 \(a\) 和 \(n-i\) 个 \(b\) 然后相乘得到的，而这样的组合方案是 \(\binom{n}{i}\)，所以我们得到展开后第 \(i\) 项就是 \(\binom{n}{i}a^{n-i}b^{i}\) ，累加后就得到了上面的公式。

组合数性质

下面挑几个会的证明一下，不会的先咕了。

1. \[\binom{n}{m}=\binom{n}{n-m} \]

证明：

\[\binom{n}{n-m}=\frac{n!}{[n-(n-m)]!(n-m)!}=\frac{n!}{m!(n-m)!}=\binom{n}{m} \]

2. \[\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1} \]

3. \[\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1} \]

证明：从 \(n\) 个数里面选 \(m\) 个数，就等同于第一个数选了，然后从 \(n-1\) 个中选 \(m-1\) 个数和第一个数没选，从 \(n-1\) 个数中选 \(m\) 个数的方案的和。或者你可以看看杨辉三角

4. \[\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{n}=\sum_{i=0}^{n}\binom{n}{i}=2^{n} \]

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

证明：当 \(m\) 为奇数的时候，由性质 \(1\) 得，两项一一对应和为 \(0\) ，显然成立；当 \(m\) 为偶数的时候，利用 \(\binom{n}{0}=\binom{n-1}{0},\binom{m}{m}=\binom{m-1}{m-1}\) 替换，再用递推式得到：

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

\[=\binom{n-1}{0}-\binom{n}{1}+\ldots-\binom{n}{n-1}+\binom{n}{n} \]

\[=\binom{n-1}{0}-(\binom{n-1}{0}+\binom{n-1}{1})+\ldots-(\binom{n-1}{n-2}+\binom{n-1}{n-1})+\binom{n-1}{n-1}=0 \]

6. \[\sum_{i=0}^{m}\binom{n}{i}\binom{m}{m-i}=\binom{n+m}{m}(n\ge m) \]

证明：

在 \((n+m)\) 个数中选 \(r\) 个数，在前 \(n\) 个中选 \(i\) 个数的方案有 \(\binom{n}{i}\) 种，在后 \(m\) 个里选 \((r-i)\) 个数的方案数为 \(\binom{m}{r-i}\) 种，相乘求和即可得到

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

一开始的式子就是这个式子的 \(r=m\) 的情况。

7. \[\sum_{i=0}^{n}\binom{n}{i}^{2}=\binom{2n}{n} \]

证明：其实是 \(6\) 的特殊情况，取 \(n=m\) 即可。

8. \[\sum_{i=0}^{n}i\binom{n}{i}=n2^{n-1} \]

证明：把左边拆开得到：

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

\[=n\times \sum_{i=0}^{n}\frac{(n-1)!}{(n-i)!(i-1)!} \]

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

\[=n\times \sum_{i=0}^{n-1}\binom{n-1}{i}=n\times 2^{n-1} \]

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

证明：和性质 \(8\) 类似，先不证了。

10. \[\sum_{i=0}^{n}\binom{i}{k}=\binom{n+1}{k+1} \]

11. \[\binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k} \]

证明：

\[\binom{n}{r}\times \binom{r}{k}=\frac{n!}{r!(n-r)!}\times\frac{r!}{k!(r-k)!} \]

\[=\frac{n!}{k!(n-r)!(r-k)!} \]

分子与分母同乘 \((n-k)!\)

\[\frac{n!}{k!(n-k)!}\times\frac{(n-k)!}{(r-k)!(n-r)!}=\binom{n}{k}\times \binom{n-k}{r-k} \]

12. \[\sum_{i=0}^{n}\binom{n-i}{i}=F_{n+1} \]

13. \[\binom{n+m+1}{m}=\sum_{i=0}^{m}\binom{n+i}{i} \]

证明：首先对性质 \(3\) 变形：\(\binom{n}{m}+\binom{n}{m-1}=\binom{n+1}{m}\)，并且我们知道 \(\binom{n}{0}=\binom{n+1}{0}=1\)，那么就有：

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

\[=\binom{n+1}{0}+\binom{n+1}{1}+\ldots+\binom{n+m}{m} \]

\[=\binom{n+2}{1}+\binom{n+2}{2}+\ldots+\binom{n+m}{m} \]

最后就会得到：

\[=\binom{n+m+1}{n} \]

其中 \(F\) 指斐波那契数列，\([n=0]\) 表示如果 \(n\) 为 \(0\) 则值为 \(1\)，反之值为 \(0\)。

其实还有二项式反演啥的但是我咕了。

感谢OI Wiki以及bloodstalk的帮助