基本定义

排列组合考的不是计算，而是逻辑思维。

分类加法计数原理

flowchart LR
	A -->|3趟飞机航班| B
	A -->|4列火车| B
	A -->|2艘船| B

从A地到B地一共有 3 + 4 + 2 = 9种方案。

分步乘法计数原理

flowchart LR
	A -->|a| B
	A -->|b| B
	B -->|c| C
	B -->|d| C
	B -->|e| C

从A地到C地，需要先经过B地。

A地到B地有2种方法
B地到C地有3种方法

共有2 * 3 = 6种方法。该题分步来进行，第一步从A地到B地，第二步从B地到C地，每一步的方案数相乘。

可以逐个枚举试一下

A地到B地经过路径a
- ac、ad、ae
A地到B地经过路径b
- bc、bd、be

常见题型

一、特殊元素优先安排

例1：六个人从左至右排成一行，最左端只能排甲或乙，最右端不能排甲，有多少种排法?

特殊元素使最左端和最右端，那么先选最左端，再选最右端，最后选其余4个位置。（先右后左也行）

最左端有两种选法。

此时选最右端就有问题：如果最左端是甲，最右端有5种选法；如果最左端是乙，最右端不能排甲，有4种选法。

甲	*	*	*	*	5种选法
乙	*	*	*	*	4种选法

遇到这种情况：有两种不一样方案，就需要分类。

做题时不需要一开始就想怎么分类，按正常的步骤去做，遇到有不确定的方案时，再去分类。

分成两类，第一类最左端为甲，第二类最右端为乙。最左端已经确定，不需要再选了。步骤变成：先选最右端，最后选其余4个位置。

第一类
1. 最右端：5种
2. 其余4人：$A_4^4$

甲	*	*	*	*	5种选法

第二类
1. 最右端：4种
2. 其余4人：$A_4^4$

乙	*	*	*	*	4种选法

故结果为 $5 \times A_4^4 + 4 \times A_4^4$。

习题

1、用0，1，2，3，4组成一个无重复数字的五位偶数有多少个？

2、A B C D E 5个人出4个人完成 a b c d 四项工作，出任务的4人每人完成一个工作，每个工作安排给一个人，

其中 A B 只会做 a b 这两种工作，其余人可以胜任所有工作，有多少种不同的安排任务的方式？

3、有5张卡片，正反两面分别写有数字0与1，2与3，4与5，6与7，8与9，先从中取出3张排成一列，可以摆成多少个不同的三位数？

解析分割线

解析

1、用0，1，2，3，4组成一个无重复数字的五位偶数有多少个？

五位数，首位不能为0，最后一位只能为0、2、4，该题是特殊元素优先安排。

先选最后一位

再选首位

最后选其余的位。

4种	*	*	*	0
3种	*	*	*	2 \| 4

最后一位如果为0，首位无影响，有4种；最后一位为2或4，首位不能为0，只有3种。

那么分成两类

第一类：最后一位为0
1. 首位无影响，跟其余位一起算，$A_4^4$

4种	*	*	*	0

第二类
1. 最后一位：2种
2. 首位：3种
3. 其余3位：$A_3^3$

3种	*	*	*	2 \| 4

故$2 \times 3 \times A_3^3 + A_4^4$。

2、A B C D E 5个人出4个人完成 a b c d 四项工作，出任务的4人每人完成一个工作，每个工作安排给一个人，

其中 A B 只会做 a b 这两种工作，其余人可以胜任所有工作，有多少种不同的安排任务的方式？

这些题都有两种切入角度：

第一种：人选工作

分成3类：

A，C，D，E

B，C，D，E

A，B，*，*

然后再去分配工作。

第二种：工作选人

此时特殊元素是c、d。因为a、b这两个工作谁都能做，c、d工作只有C、D、E能做。

只需要两步，先确定特殊元素，再确定其余元素。

给c、d选人：从C、D、E里选两个人，$A_3^2$

给a、b选人：从剩余的3人里选两个人，$A_3^2$

故$A_3^2 \times A_3^2$。

3、有5张卡片，正反两面分别写有数字0与1，2与3，4与5，6与7，8与9，先从中取出3张排成一列，可以摆成多少个不同的三位数？

如果按着题目走，先从5张卡片里选3张，再排列，然后卡片正面还是反面，还要判断0|1这张卡片，十分难做。

那么可以跟第2题一样想，换一个切入角度，跳出题目的场景，位置选数，给这三位数逐位选数字：

选百位：0不能选，有9种。

选十位：百位数消耗了1张卡片，剩4张卡片，只有8个数字，有8种。

选个位：百位、十位消耗了2张卡片，剩3张卡片，只有6个数字，有6种。

故结果为$9 \times 8 \times 6$。

二、捆绑法

特点：元素需要相邻。

例题：7人站成一排，其中甲乙相邻且丙丁相邻，共有多少种不同的排法？

将相邻的两个人看作一个人，相当于绑起来。相邻的两个人是有顺序的：甲乙、乙甲，要乘2。

甲乙捆：2种

丙丁捆：2种

全部一起排：此时相当于5个人，$A_5^5$

故结果为$2 \times 2 \times A_5^5$

习题

1、一排9个座位坐了3个三口之家，若每家人坐在一起，则不同的坐法种数为？

2、8个车位，5辆不同的车，车全停一起多少种停法?空车位全在一起多少种停法？

解析分割线

解析

1、一排9个座位坐了3个三口之家，若每家人坐在一起，则不同的坐法种数为？

a1 a2 a3	b1 b2 b3	c1 c2 c3

将同一家的人捆在一起

a1 a2 a3：$A_3^3$

b1 b2 b3：$A_3^3$

c1 c2 c3：$A_3^3$

全部一起排：$A_3^3$

2、8个车位，5辆不同的车，车全停一起多少种停法？空车位全在一起多少种停法？

车全停一起

5辆车捆：$A_5^5$

停大车：4种

空车位停一起

3个空车位捆：空车位之间一样，调换顺序没有区别，1种

全部排：3个空车位看作一个，相当于6，$A_6^6$

三、插空法

特点：元素需要不相邻。

例题：某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目。如果将这两个新节目插入原节目单中，那么不同插法的种数为？且两个新节目不相邻，那么不同插法的种数为?

直接插入无要求：第一个节目从6个空插入有6种；第二个节目插入时，此时多了一个节目，有7个空，插入有7种。

不相邻：5个节目有6个空隙，从6个空里插两个节目，$A_6^2$。

习题

1、4个男生，3个女生站成一排，三个女生中有且只有两个女生相邻，多少种不同的排法？

2、8个车位，5辆不同的车，只有空车位互不相邻在一起多少种停法？只有2个空车位在一起多少种停法?

解析分割线

解析

1、4个男生，3个女生站成一排，三个女生中有且只有两个女生相邻，多少种不同的排法？

2个女生相邻，剩下的一个女生不能与这2个女生相邻，就有不相邻了。

4个男生：$A_4^4$

3个女生选2个捆：$A_3^2$

插空：$A_5^2$

2、8个车位，5辆不同的车，只有空车位互不相邻在一起多少种停法？只有2个空车位在一起多少种停法?

空车位互不相邻：

排5辆车：$A_5^5$

插空：空车位调换没有影响，$C_6^3$

只有2个空车位相邻：

排5辆车：$A_5^5$

绑2空车位：空车位一样，没有顺序，1种

6空隙插空：插入两个元素：两个空车位、一个空车位，此时这两个元素不一样，$A_6^2$

四、定序问题 & 相同元素排列问题

定序问题：部分元素顺序已经定好，只选不排。
相同元素排列问题：部分元素相同，没有顺序，只选不排。

例题1：7个人排队，其中甲在乙前面，乙在丙前面。

甲乙丙三人选位置：$C_7^3$

甲乙丙：三人的顺序已经定好，只有1种

余4人：$A_4^4$

例题2：1 1 1 2 3组成5位数，几种可能？

给三个1选三个位置：$C_5^3$

三个1：交换没有区别，1种

余2个：$A_2^2$

习题

1、某工程队有6项工程需要单独完成，其中工程乙必须在工程甲完成之后才能进行，工程丙必须在工程乙完成之后才能进行，工程丁必须在工程丙完成之后立即进行，共有多少种方案？

2、三位数中，123叫做严格递增数，530叫做严格递减数，严格单调3位数有多少个？

3、7人身高不同，排成一排，中间最高，两侧依次降低，多少种排法？

4、把good写错多少种方法?把error写错多少种方法?

解析分割线

解析

甲 –> 乙 –> 丙丁，丙丁看作一个工程。

3个工程选：$C_5^3$

3个工程：顺序已经定好，1种

余2：$A_2^2$

2、三位数中，123叫做严格递增数，530叫做严格递减数，严格单调3位数有多少个？

递减数：

从10个里选3个：$C_{10}^3$

这3个数需要递减，只有1种

递增数：

从10个里选3个：0不能选，剩9个数，$C_{9}^3$

这3个数需要递增，只有1种

故$C_{10}^3 + C_{9}^3$。

3、7人身高不同，排成一排，中间最高，两侧依次降低，多少种排法？

			最高

中间只能是最高的一个，只有1种，没得选。

选左边3人：$C_6^3$

选右边3人：$C_3^3$

顺序已经定好了，只能向两侧依次降低，只有1种。

故$C_6^3$。

4、把good写错多少种方法?把error写错多少种方法？

good：$C_4^2 A_2^2 - 1$

error： $C_5^3 A_2^2 - 1$

五、挡板法

特点：相同的元素分成n份，1份至少m个。

例题：6个相同的苹果，分给3人，每人至少有1个苹果，有几种分法？

将苹果分成3份，需要2个挡板。

1 2 | 3 4 | 5 6

6个苹果中间有5个位置可以放挡板，故$C_5^2$

习题

1、12个苹果分给3个人，每个人至少3个，多少种分法?

2、9个运动员名额分给1班2班3班，要求每个班所得名额不少于自己班级序号，多少种分法?

解析分割线

解析

1、12个苹果分给3个人，每个人至少3个，多少种分法?

三个人分别给两个苹果，问题就转换成6个苹果给3人，每人至少1个，$C_5^3$

2、9个运动员名额分给1班2班3班，要求每个班所得名额不少于自己班级序号，多少种分法?

2班给1个名额，3班给2个名额，问题转换成6个名额给3个班，至少1个，$C_5^2$

六、分组问题

特点：多个元素分成n组。

平均分组：出现m个组元素个数一样，除以$A_m^m$。

例题1：6本书，分成3组，第一组1本书，第二组2本书，第三组3本书，有几种分法？

第一组$C_6^1$

第二组$C_5^2$

第三组$C_3^3$

故$C_6^1 C_5^2 C_3^3$。

例题2：6本书，分成3组，每组2本书，有几种分法？

平均分组，三组都是一样的，没有顺序，继续按例1的方法统计，会重复。

ab	cd	ef
cd	ab	ef
ab	ef	cd
cd	ef	ab
ef	ab	cd
ef	cd	ab

每$A_3^3$种方案是1种，$C_6^2 C_4^2 C_2^2 \div A_3^3$。

习题

1、9本书分堆，放书架

（1）9本书分成1，3，5三堆，然后放到3个不同的书架上，多少种放法？

（2）9本书平均分成3堆，然后放到3个不同的书架上，多少种方法?

（3）9本书分成2，2，5三堆，然后放到3个不同的的书架上，多少种方法?

2、把9个人分配到3个单位，有多少种分法?

1）甲单位2人，乙单位3人，丙单位4人

2）1个单位2人，一个单位3人，一个单位4人

3）每个单位3人

4）两个单位各2人，一个单位5人

3、把A，B,C,D四本不同的书分给三位同学，每人至少一本，每本书必须有人分到，A、B不能分给同一个人，多少种不同的分法?

解析分割线

解析

1、9本书分堆，放书架

（1）9本书分成1，3，5三堆，然后放到3个不同的书架上，多少种放法？

分组：$C_9^1 C_8^3 C_5^5$

放到书架：$A_3^3$

故结果$C_9^1 C_8^3 C_5^5 A_3^3$。

（2）9本书平均分成3堆，然后放到3个不同的书架上，多少种方法?

分组：$C_9^3 C_6^3 C_3^3 \div A_3^3$

放到书架：$A_3^3$

故结果$C_9^3 C_6^3 C_3^3$。

（3）9本书分成2，2，5三堆，然后放到3个不同的的书架上，多少种方法?

分组：$C_9^2 C_7^2 C_5^5 \div A_2^2$

放到书架：$A_3^3$

故结果$C_9^2 C_7^2 C_5^5 \div A_2^2 \times A_3^3$。

2、把9个人分配到3个单位，有多少种分法?

1）甲单位2人，乙单位3人，丙单位4人

分组：$C_9^2 C_7^3 C_4^4$

分配到单位：已经指定单位，1种。

2）1个单位2人，一个单位3人，一个单位4人

分组：$C_9^2 C_7^3 C_4^4$

分配到单位：单位没指定，$A_3^3$

3）每个单位3人

分组：$C_9^3 C_6^3 C_3^3 \div A_3^3$

分配：$A_3^3$

4）两个单位各2人，一个单位5人

分组：$C_9^2 C_7^2 C_5^5 \div A_2^2$

分配：$A_3^3$

3、把A，B，C，D四本不同的书分给三位同学，每人至少一本，每本书必须有人分到，A、B不能分给同一个人，多少种不同的分法?

AB分给同一个的人分法只有1种，AB、C、D，在计算分组时，减去这一种分法。

$(\frac{C_4^1 C_3^1 C_2^2}{A_2^2} - 1) \times A_3^3$

参考视频

SleepBlog

基本定义

分类加法计数原理

分步乘法计数原理

常见题型

一、特殊元素优先安排

习题

解析

二、捆绑法

习题

解析

三、插空法

习题

解析

四、定序问题 & 相同元素排列问题

习题

解析

五、挡板法

习题

解析

六、分组问题

习题

解析

你的赏识是我前进的动力