排列组合

一、两个基本原理

1.分类计数原理（加法原理）

1.1 定义

如果完成一件事有 $n$ 类办法，只要选择其中一类办法中的任何一种方法，就可以完成这件事。
若第一类办法中有 $m_1$ 种不同的方法，
第二类办法中有 $m_2$ 种不同的方法……
第 $n$ 类办法中有 $m_n$ 种不同的办法，那么完成这件事共有 $N = m_1 +m_2 +…+m_n$ 种不同的方法

1.2 特点

运用加法原理计数，关键在于合理分类，不重不漏.
要求每一类中的每一种方法都可以独立地完成此任务；
两类不同办法中的具体方法，互不相同(即分类不重)；
完成此任务的任何一种方法，都属于某一类(即分类不漏).
合理分类也是运用加法原理解决问题的难点，不同的问题，分类的标准往往不同.

1.3 加法原理使用条件:

方法分成多个类，每个方法都可以独立完成题目任务
题目出现不确定情况，此时需要分类确定再进行求解
类与类之间必须是不同的，不能有交集，必须有明确分类标准

2.分步计数原理(乘法原理)

2.1 定义

如果完成一件事，必须依次连续地完成 $n$ 个步骤，这件事才能完成.
若完成第一个步骤有 $m_1$ 种不同的方法，
完成第二个步骤有 $m_2$ 种不同的方法……
完成第n个步骤有 $m_n$ 种不同的方法，
那么完成这件事共有 $N = m_1·m_2·.....·m_n$ 种不同的方法

2.2 特点

运用乘法原理计数，关键在于合理分步.
完成这件工作的 $N$ 个步骤，各个步骤之间是相互联系的，任何一步的一种方法都不能完成此工作，必须连续完成这 $N$ 步才能完成此工作；各步
计数相互独立；只要有一步中所采取的方法不同，则对应的完成此工作的方法也不同.

理解“依次连续”和“相互独立”

上一步不管选择哪种方法，对下一步都不能产生干扰
若上一步选择的方法对下一步产生干扰了，则要对上一步的方法进行分类
做完上一步，才能完成下一步.不能跳步
必须所有步骤都完成，任务才能完成.不能漏步

3.两个原理的区别及联系

抓住两个基本原理的区别，不要用混，不同类的方法(其中每一种方法都能把事情从头至尾做完)数之间做加法，
不同步的方法(其中每一种方法都只能完成这件事的一部分)数之间做乘法.

在研究完成一件工作的不同方法数时，要遵循“不重不漏”的原则.
如：从若干件产品中抽出几件产品来检验，把抽出的产品中至多有2件次品的抽法分为两类：
第一类抽出的产品中有2件次品，
第二类抽出的产品中有一件次品，
这样的分类显然漏掉了抽出的产品中无次品的情况.
又如：把能被2、被3或被6整除的数分为三类：
第一类是能被2整除的数，
第二类是能被3整除的数，
第三类是能被6整除的数，
其中第一类、第二类都和第三类有重复，这样的分类是不正确的

在运用乘法原理时要注意，每个步骤都做完，这件事也必须完成.

image.png

二、排列与组合

1.排列

1.1 定义

从n个不同元素中，任意取出m(m≤n)个元素，按照一定顺序排成一列，称为从n个不同元素中取出m个元素的一个排列.

1.2 排列数

从n个不同元素中取出m个元素(m≤n)的所有排列的种数，称为从n个不同元素中取出m个不同元素的排列数，记作 $P_n^m$ 或 $A_n^m$
当m = n时， $P_n^n$ 或 $A_n^n$ 称为全排列.

区别排列和排列数的不同：
“一个排列”是指从n个不同元素中，任取m个元素按照一定的顺序排成一列，不是数；
’'排列数”是指从n个不同元素中，任取m(m≤n)个元素的所有排列的个数，是一个数.
所以符号 $P_n^m$ 只表示排列数，而不表示具体的排列.

1.3 排列数公式

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

注意事项

不同元素：n!
相同元素：1
部分相同： $\frac{n!}{m!}$ （共n个，有m个相同）消序法

消序法：

出现部分相同元素排序
出现固定顺序元素重新排序

4个球平均分成2堆,每堆2个,有几种分法：
$\frac{C_4^2C_2^2}{A_2^2}$

6个球平均分成3堆,每堆2个,有几种分法：
$\frac{C_6^2C_4^2C_2^2}{A_3^3}$

消序：有几堆相同个数的元素，就除以几的阶乘

2.组合

2.1 组合的定义

从n个不同元素中，任意取出m(m≤n)个元素并为一组，称为从n个不同元素中取出m个元素的一个组合.

2.2 组合数

从n个不同元素中，取出m(m≤n)个元素的所有组合的个数，称为从n个不同元素中，取出m个不同元素的组合数，记作 $C_n^m$
①组合数公式： $C_n^m=\frac{n(n-1)···(n-m+1)}{m(m-1)····2·1}=\frac{n!}{m!(n-m)!}=\frac{A_n^m}{m!}$
②排列是先组合再排列： $A_n^m=C_n^m·A_m^m=C_n^m·m!$