04-27 22:03 北京大学附属中学算法工程师发布于四川

关注

【Note】组合数学（初级）

排列组合

排列组合是组合数学中的基础。排列就是指从给定个数的元素中取出指定个数的元素进行排序；组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。在高中初等数学中，排列组合多是利用列表、枚举等方法解题。——OI-Wiki

一般思路

排列与组合组合数学的研究对象中,根据有无顺序,一般分为排列问题和组合问题。排列与组合的根本区别在于前者与元素的顺序有关,后者与元素的顺序无关。在排列与组合的问题中, 经常会出现计数问题, 解决计数问题的思路一般有以下三种：

只取要的。即把各种符合条件的情形枚举出来,再利用加法原理求和；
先全部取,再减去不要的。即把所有可能的情形枚举出来,再减去不符合条件的情形；
先取后排。即先把各步中符合条件的排列或组合计算出来,再根据乘法原理求积。

加法原理和乘法原理

加法原理

一道题的解法有 $n$ 类，第 $i$ 类有 $a_i$ 个解法，那么这道题总共有 $a_1+a_2+a_3+\cdots+a_{n-1}+a_n$ 种不同的解法。

乘法原理

解决一道题需要 $n$ 个步骤，第 $i$ 个步骤有 $a_i$ 种做法，那么这道题的解法共有 $a_1\times a_2\times a_3\times\cdots\times a_{n-1}\times a_n$ 种解法。

某种样式的运动服由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有 $4\times2=8$ 种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，此时有 $4\times(4-1)=12$ 种着色方案（条纹和底色不能是同一种颜色）。

在乘法法则中要注意事件 A 和事件 B 的相互独立，以及一些隐含规则。

排列与组合基础

前置知识

$n!$ 表示 $n$ 的阶乘，即 $n!=1\times2\times3\times\cdots\times(n-1)\times n$ 。特别的， $0!=1$

排列数

从 $n$ 个不同元素中取出 $m$ 个元素组成一个排列，可以组成的所有排列的个数叫做排列数，用符号 $A_n^m$ 表示。

排列数的计算公式如下： $A_n^m=n(n-1)(n-2)\cdots(n-m-1)=\frac{n!}{(n-m)!}$

可以理解为有 $n$ 个人排队，总共有 $m$ 个位置，第一个位置可以从 $n$ 个人里面选，第二个位置可以从 $n-1$ 个人里面选，以此类推，第 $m$ 个位置可以从 $n-m+1$ 个人里面选。

全排列则是排列数的一种特殊情况，即 $m=n$ 。其排列数为： $A_n^n=\frac{n!}{(n-n)!}=n!$

组合数

定义及公式

从 $n$ 个不同元素中，任取 $m(m\leq n)$ 个元素组成一个集合（叫做一个组合），可以组成集合的个数叫做组合数，也被称为二项式系数。用符号 $\begin{pmatrix}n\\m\end{pmatrix}$ （或 $C_n^m$ ）表示。

组合数的计算公式如下： $\begin{pmatrix}n\\m\end{pmatrix}=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}$

可以这样理解：从 $n$ 个人中选 $m$ 个人，选出 $m$ 个人排列的话有 $A_n^m$ 种排法。同样的 $m$ 个人，组合不考虑顺序，所以只会有 $1$ 种组合，但却有 $m!$ 种排列（相当于 $m$ 个人进行全排列）。所以我们要将多出的 $m!$ 种排列除掉。

性质一

$\begin{pmatrix}n\\m\end{pmatrix}=\begin{pmatrix}n\\n-m\end{pmatrix}$

解释：从 $n$ 个元素中选 $m$ 个也就等价于从 $n$ 个元素中选出 $m$ 个元素排除，从而选出剩余的 $n-m$ 个元素。

公式证明如下： $\begin{pmatrix}n\\m\end{pmatrix}=\frac{n!}{m!(n-m)!}=\frac{n!}{(n-m)![n-(n-m)]!}=\begin{pmatrix}n\\n-m\end{pmatrix}$

性质二

$\begin{pmatrix}n\\m\end{pmatrix}=\begin{pmatrix}n-1\\m\end{pmatrix}+\begin{pmatrix}n-1\\m-1\end{pmatrix}$

解释：我们在对 $n$ 个元素中的一个做选与不选的决定后，还剩 $n$ 个数。

如果没选它，还可以选 $m$ 个数，还有 $\begin{pmatrix}n-1\\m\end{pmatrix}$ 种组合；
如果选了它，还可以选 $m-1$ 个数，还有 $\begin{pmatrix}n-1\\m-1\end{pmatrix}$ 种组合。

公式证明如下： $\begin{pmatrix}n\\m\end{pmatrix}=\frac{n!}{m!(n-m)!}=\frac{[m+(n-m)](n-1)!}{m!(n-m)!}=\frac{m(n-1)!+(n-m)(n-1)!}{m!(n-m)!}\\\ \\=\frac{m(n-1)!}{m!(n-m)!}+\frac{(n-m)(n-1)!}{m!(n-m)!}=\frac{(n-1)!}{(m-1)!(n-m)!}+\frac{(n-1)!}{m!(n-m-1)!}=\begin{pmatrix}n-1\\m\end{pmatrix}+\begin{pmatrix}n-1\\m-1\end{pmatrix}$

插板法

插板法是用于求一类给相同元素分组的方案数的一种技巧，也可以用于求一类线性不定方程的解的组数。

正整数解的数目

问题一：现有 $n$ 个完全相同的元素，要求将其分为 $m$ 组，每组至少有一个元素，一共有多少种分法？

由于每组至少一个元素， $n$ 个元素两两之间有 $n-1$ 个空，只需要插入 $m - 1$ 个板子，就可以分为 $m$ 组。因为元素是完全相同的，所以答案就是 $\begin{pmatrix}n-1\\m-1\end{pmatrix}$ 。

本质上是在求解方程 $x_1+x_2+x_3+\cdots+x_m=n$ 的正整数的个数。

非负整数解的数目

问题二：现有 $n$ 个完全相同的元素，要求将其分为 $m$ 组，允许组为空，一共有多少种分法？

假设我们借来 $m$ 个元素，现在有 $n+m$ 的元素，那么有 $n+m-1$ 个空位，我们在其中插入 $m-1$ 个板子，这样形成 $m$ 组，并且保证了每一组不为空。此时，我们再拿出去借来的 $m$ 个元素，就变成了分为 $m$ 组，并且组内元素可以为空。所以答案为 $\begin{pmatrix}n+m-1\\m-1\end{pmatrix}=\begin{pmatrix}n+m-1\\(n-1)-(m-1)\end{pmatrix}=\begin{pmatrix}n+m-1\\n\end{pmatrix}$ .