数学(1)——排列组合
Reywmp
·
·
个人记录
排列组合是很基础的数学内容，根据字面意思分为 排列 和 组合 ，解决排列组合有很多方法，枚举，列表，以及套公式等等。
排列组合定义
排列指的是从 n 个元素中，任取 m 个元素按照顺序进行不同的排列，有 线排列，重排列 和 圆排列 等，排列的个数叫做 排列数，用 \mathrm A_n^m 或 \mathrm P_n^m 表示。
组合是指从 n 个元素中，任取 m 个为一组的组合，组合所有的搭配个数叫做 组合数，用 \mathrm C_n^m 或 \displaystyle\binom{n}{m} 表示。
虽然也有定义，但是我们一般只考虑 m\leq n , n,m\in\mathbb N 的情况。
加法与乘法原理
- 加法原理：达到一个目标有 n 种方法，a_i 表示第 i 种方法有多少个，所以解决问题的办法共有 \displaystyle \sum_{i=1}^na_i 种。
- 乘法原理：达到一个目标需要经历 n 步，a_i 表示第 i 步有多少种方法，所以解决问题的办法共有 \displaystyle \prod_{i=1}^n a_i 种。
排列组合的一些公式
基本计算式
排列：首先基本的计算公式有
\mathrm A_n^m=n(n-1)(n-2)\dots(n-m+1)=\frac{n!}{(n-m)!}
可以考虑对于一个数列，不难发现第 i 个位置有 n-i+1 个选择，以此推出上式。
组合：有
\mathrm C_n^m=\frac{\mathrm A_n^m}{m!}=\frac{n!}{m!(n-m)!}
我们在排列中选出 m 人，但是由于组合不考虑排列，所以除去 m 个人的全排列，所以得出上式。
关于二项式
组合数其实又称二项式系数。
我们拿出来一个叫做杨辉三角的玩意：
\begin{matrix}
&&&&&&1&\\
&&&&&1&&1\\
&&&&1&&2&&1\\
&&&1&&3&&3&&1\\
&&1&&4&&6&&4&&1\\
&1&&5&&10&&10&&5&&1\\
1&&6&&15&&20&&15&&6&&1\\
&&&&&&\vdots
\end{matrix}
这个东西奥妙太深了，我们来领悟一下。
其实我们应该知道，杨辉三角的第 i 行的数，表示的是 (x+y)^{i-1} 这个式子展开后各项系数。
不信可以来举几个例子看一下：
$(x+y)^3={\color{red}1}x^3+{\color{red}3}x^2y+{\color{red}3}xy^2+{\color{red}1}y^3$ 发现是第 $4$ 行的四个数。
$\vdots
继续往下列仍然会成立的。
我们还可以通过奇怪的方法来验证这个结论。
我们给 (x+y)^{i-1} 这个式子带入 x=1,y=1 得到 2^{i-1}
我们在杨辉三角中验证得：
\begin{matrix}
&&&&&&1&&&&&&&=1=2^0\\
&&&&&1&+&1&&&&&&=2=2^1\\
&&&&1&+&2&+&1&&&&&=4=2^2\\
&&&1&+&3&+&3&+&1&&&&=8=2^3\\
&&1&+&4&+&6&+&4&+&1&&&=16=2^4\\
&1&+&5&+&10&+&10&+&5&+&1&&=32=2^5\\
1&+&6&+&15&+&20&+&15&+&6&+&1&=64=2^6\\
&&&&&&\vdots
\end{matrix}
发现他又成立辣！
所以这些系数是怎么得到的呢，我们抽象化地引入组合数的概念。
如果说我们写开一个 (x+y)^n 的式子观察
(x+y)\times(x+y)\times(x+y)\dots\times(x+y)
我们考虑每次提取一个同类项 x^ay^b ，显然 a+b=n ，那么我们单独考虑 x 的话，我们发现就是从那 n 个 (x+y) 因子中提出 a 个 x ，不同的 x^a 与 y^b 相乘组成不同的 x^ay^b ，这样整个问题就成为了 n 个 x 选 a 个的组合数问题。
这样第 i 行第 j 个数可以表示为 \displaystyle\binom{i-1}{j-1}
所以杨辉三角甚至可以表示为：
\begin{matrix}
&&&&&&\binom{0}{0}&\\
&&&&&\binom{1}{0}&&\binom{1}{1}\\
&&&&\binom{2}{0}&&\binom{2}{1}&&\binom{2}{2}\\
&&&\binom{3}{0}&&\binom{3}{1}&&\binom{3}{2}&&\binom{3}{3}\\
&&\binom{4}{0}&&\binom{4}{1}&&\binom{4}{2}&&\binom{4}{3}&&\binom{4}{4}\\
&\binom{5}{0}&&\binom{5}{1}&&\binom{5}{2}&&\binom{5}{3}&&\binom{5}{4}&&\binom{5}{5}\\
\binom{6}{0}&&\binom{6}{1}&&\binom{6}{2}&&\binom{6}{3}&&\binom{6}{4}&&\binom{6}{5}&&\binom{6}{6}\\
&&&&&&\vdots
\end{matrix}
于是从中可以看出一些组合数的性质
比如从杨辉三角的上下位置关系入手：
有：
\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}
可以考虑建立模型推导，或者直接暴力展开去证明这个式子。
以及对称性：
\binom{n}{k}=\binom{n}{n-k}
包括根据定义得出的递推式：
\displaystyle \binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}
还有我们之前看每行的和得出来的：
\left\{\begin{aligned}
\displaystyle\binom{n}{0}+\binom{n}{1}+\dots+\binom{n}{n}=\sum_{i=0}^n\binom{n}{i}&=2^n&(x=1,y=1)\\
\displaystyle\sum_{i=0}^n(-1)^i\binom{n}{i}&=0 &(x=1,y=-1)
\end{aligned}\right.
还有一些通过定义和组合意义证明的式子：
-
\displaystyle \sum_{l=0}^n\binom{l}{k}=\binom{n+1}{k+1}
-
-
还有比较重要的 范德蒙德卷积
\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}
组合意义证明的话，就是理解为 n 和 m 个物体的两堆中选择 k 个物品。
考虑二项式定理证明。
\begin{aligned}
\sum_{i=0}^{n+m}\binom{n+m}{i}x^i&=(1+x)^{n+m}\\
&=(1+x)^n(1+x)^m\\
&=(\sum_{i=0}^n\binom{n}{i}x^i)(\sum_{j=0}^m\binom{m}{j}x^j)\\
&=\sum_{i=0}^{n+m}(\sum_{k=0}^i\binom{n}{k}\binom{m}{i-k})x^i\\
\therefore \sum_{k=0}^i\binom{n}{k}\binom{m}{i-k}&=\binom{n+m}{i}
\end{aligned}
整理一下，证毕。
范德蒙德卷积有一些推论：
-
\displaystyle \sum_{i=1}^n\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}
证明：
\sum_{i=1}^{n}\binom{n}{i}\binom{n}{i-1}=\sum_{i=0}^{n-1}\binom{n}{i}\binom{n}{i+1}=\sum_{i=0}^{n-1}\binom{n}{i}\binom{n}{n-1-i}
根据范德蒙德卷积得：
\sum_{i=0}^{n-1}\binom{n}{i}\binom{n}{n-1-i}=\binom{2n}{n-1}
还有：
-
\displaystyle\sum_{i=0}^n\binom{n}{i}^2=\sum_{i=0}^n\binom{n}{i}\binom{n}{n-i}=\binom{2n}{n};
-
\displaystyle\sum_{i=0}^m\binom{n}{i}\binom{m}{i}=\sum_{i=0}^m\binom{n}{i}\binom{m}{m-i}=\binom{n+m}{m};
我们可以考虑一个带权的二项式系数的和为：
\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}^nk\binom{n}{k}^2=n\binom{2n-1}{n-1}
上式其实可以通过\displaystyle \binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}=\frac{n}{k}\binom{n-1}{n-k} 得到。
大概就是这么多。
圆排列
线排列是有起点的，圆排列考虑围成了一个环，没有所谓起点。所以不考虑不同位置的 m 个起点，圆排列(\mathrm Q_n^m) 公式为：
\mathrm Q_n^m=\frac{\mathrm A_n^m}{m}=\frac{n!}{m\times (n-m)!}
重排列
有多重集 \mathbf M=\{n_1\times b_1,n_2\times b_2,\dots,n_k\times b_k \}
其全排列个数为 \displaystyle\frac{N!}{n_1!\times n_2!\times \dots\times n_k!}=\frac{N!}{\prod_{i=1}^k n_i} ,(N=\sum_{i=1}^kn_i)
证明，考虑对于这 N 个元素，虽然有重复，但是不考虑的话还是有全排列个数 N! ，对于任何一个重复 n_i 次的元素自身多计算了 n_i! 个排列，所以得到上式。
\text{组合数学部分}\texttt{——2021.01.31~2.1} \text{写在笔记本电脑前}
Reference：
-
-
\textit{Concrete Mathematics Chapter 5}