排列组合

（一）排列和排列数

1. 排列 A（array）

A_n^m = n(n-1)(n-2)\cdots(n-m+1)

从 $n$ 个不同元素中，任取 $m (m \leq n)$ 个元素，按照一定的顺序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列。

2. 排列数公式：

A_n^m = n(n-1)(n-2)\cdots(n-m+1)

从 $n$ 个不同元素中取出 $m (m \leq n)$ 个元素的所有排列数为：

A_n^m = n(n-1)(n-2)\dots(n-m+1)

当 $n = m$ 时，为全排列

A_n^n = n(n-1)(n-2)\dots3 \cdot 2 \cdot 1 = n!

A_n^m = C_n^m \times A_m^m

排列其实相当于一步步的组合。大学寝室选 6 人去打饭，在窗口排队共有

A_6^6

种，第一位有 6 种，排第二有 5 种⋯⋯第六有 1 种，所以一共有 $6 \times 5 \times 4 \times 3 \times 2 \times 1$ 种，相当于 $C_6^6 \times C_5^5 \times C_4^4 \times C_3^3 \times C_2^2 \times C_1^1$ 种。

假如只是从 6 人中选 3 人打饭，不用排队，则是 $C_6^3$ 种，如果算上排队，则 $C_6^3 \times A_3^3$ 种，即相当于一开始就选出排队的 $A_6^3$ 种。

注意: 先组合再排列，注意排列的是 $C_n^m$ 中的 $n$ ，一定是 $n$ 分不同情况下有顺序，如果不区分，则不用乘 $A_n^m$ 。

（二）组合和组合数

1. 组合 C（combination）

从 $n$ 个不同元素中，任取 $m(m \leq n)$ 个元素并成一组，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合。

2. 组合数公式：

从 $n$ 个不同元素中取出 $m(m \leq n)$ 个元素的所有组合的个数

$C_n^m = \frac{A_n^m}{A_m^m} = \frac{m(m-1)(m-2)\cdots(m-n+1)}{m!}$
$C_n^m = C_n^{n-m}$

从寝室 6 人中选 2 人去打饭，剩下 4 人在寝室，选 2 人打饭和留 4 人在寝室是一样的，2 人打饭即剩的 4 人肯定在寝室，所以

$C_6^2 = C_6^4$

区别: 排列——与顺序有关，组合——与顺序无关。

（三）加法原理和乘法原理

1. 加法原理

完成一件事，有 $n$ 类办法，在第 1 类办法中有 $m_1$ 种不同的方法，在第 2 类办法中有 $m_2$ 种不同的方法⋯⋯在第 $n$ 类办法中有 $m_n$ 种不同的方法，那么完成这件事共有 $N = m_1 + m_2 + \cdots + m_n$ 种不同的方法。

例如: 从甲地到乙地，一天中，火车有 3 趟，汽车有 2 趟，那么一天中从甲地到乙地有几种方式？解析从甲地到乙地的方式可以是乘坐火车或者汽车。既然有 3 趟火车和 2 趟汽车，那么总的出行选择方式就是火车和汽车的选择方式之和。

选择火车的方式有 3 种。
选择汽车的方式有 2 种。

因此，总的方式数是 3 + 2 = 5 种。所以，一天中从甲地到乙地总共有 5 种不同的方式。

2. 乘法原理

完成一件事需要 $n$ 个步骤，做第 1 步有 $m_1$ 种不同的方法，做第 2 步有 $m_2$ 种不同的方法，⋯⋯做第 $n$ 步有 $m_n$ 种不同的方法，那么完成这件事共有

$N = m_1 \times m_2 \times \cdots \times m_n$

种不同的方法。

例如: 从甲地到乙地，必须先经过丙地，一天中，从甲地到丙地火车有 3 趟，从丙地到乙地汽车有 2 趟，那么一天中从甲地到乙地有几种方式？解析要从甲地到达乙地，因为必经丙地，所以需要考虑从甲地到丙地，再从丙地到乙地的组合方式。从甲地到丙地有 3 趟火车可选，从丙地到乙地有 2 趟汽车可选。每趟火车都可以搭配 2 趟汽车中的任一趟，因此，总的组合方式为： 3 趟火车 * 2 趟汽车 = 6 种方式所以，一天中从甲地到乙地总共有 6 种不同的方式。

解题策略

1. 内部组合，外部排列

例1：某次专业技能大赛有来自A科室的4名职工和来自B科室的2名职工参加，结果有3人获奖且每人的成绩均不相同。如果获奖者中最多只有1人来自B科室，那么获奖者的名单和名次顺序有多少种不同的可能性？

A. 48
B. 72
C. 96
D. 120

解析: 分类。

情况 1: 获奖 B 科 1 人，A 科 2 人，B 选 1，有 2 种，A 选 2，有 $C_4^2 = 6$ 种，获奖 3 人排序有 $A_3^3 = 6$ 种，总情况 2 $\times 6 \times 6 = 72$ 种（错误点: 情况 1，A 选 2 时不能直接先排 $A^2$ ，易错）。
情况 2: 获奖三人都是 A：A 选 3，有 $A_3^3 = 24$ 种。两种情况相加 $72 + 24 = 96$ 种。C。

分步组合时，已经排列，不需再排列。一次性组合出来可以再 A 排列，如果本身是分步操作组合选取，则不需要再排列。

易错点: 两个一样的东西组合，不分顺序的情况下，一定有一次重复，总情况数一定要减掉重复的。

2. 错位排列

主体完全错位，欧拉错装信封问题：

$D_1 = 0, \ D_2 = 1, \ D_3 = 2, \ D_4 = 9, \ D_5 = 44, \ D_6 = 265$

【递推公式】:

$D_n = (n-1) \left( D_{n-2} + D_{n-1} \right) = （项数-1）\times（前两项的和）$

3. 圆周排列

$n$ 个元素，共有 $(n-1)!$ 种

关键词: 环形/围成一圈/圆桌: $n$ 个元素，共有 $(n-1)!$ 种

主体环形而坐，圆周排列， $n$ 个元素/人的环形排列数：

$\frac{A_n^n}{n} = A_n^{n-1} = （N-1）!$

例: 3 人直线排列有 $A_3^3 = 6$ 种，环形排列有

$\frac{A_3^3}{3} = A_2^2 = 2$ 种。

Here is the extracted content in Markdown and LaTeX format:

4. 平均分组

全部平均分组

有 $n$ 个组，元素个数相同，只需要分组不用排列。
排列总情况数 ÷ $A_n^n$

分成 $n$ 组，先排列，再 ÷ $A_n^n$ ，即： $\frac{\text{排列总情况数}}{A_n^n}$ 分成 3 组，÷ $A_3^3$ ，分成 4 组，÷ $A_4^4$ ，分成 5 组，÷ $A_5^5$ ，分成 $m$ 组，÷ $A_m^m$ 。

5. 比赛问题

循环赛:

$N$ 支队伍进行循环赛

单循环: 比赛场次 = $C(n, 2)$

一般意义上的循环赛，

任意两支队伍打一场比赛: 比赛场次 = $C_n^2$

双循环:

任意两支队伍打两场比赛 = 单循环 $\times 2$ ，分主客场：

比赛场次 = $A_n^2$ 【基本不考】

淘汰赛:

每场比赛淘汰一支队伍，每轮比赛淘汰一半的队伍。

按轮淘汰:

$n$ 个人，每次分 2 组比赛，每次淘汰一半人，决出胜负需比赛 $n-1$ 次。

① 16 人，分成两组每组 8 人，比赛 8 场淘汰一半剩 8 人。
② 8 人，再分成两组各 4 人比赛第 4 场，淘汰一半剩 4 人。
③ 4 人，分成两组各 2 人比赛第 2 场，淘汰一半剩 2 人。
④ 2 人，最后 1 场决出胜负。

一共比赛 $8+4+2+1=15$ 场。比赛场次 = $N-1$ 。

按场淘汰
$N$ 个人比赛，决出冠亚军，比赛场次 = $N - 1$
$N$ 个人比赛，决出 1, 2, 3, 4 名，比赛场次 = $N$

即决出冠亚军后，还有两个人要比赛决出第三名和第四名，在原来基础上多一场比赛， $N - 1 + 1 = N$ 。

例: 100 人比赛，每场淘汰一个，最后剩 1 个冠军，则一共进行 99 场比赛，淘汰了 99 人。

6. 递推方法

本质是递推过程，即斐波那契数列。

像 $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89$ 。

本质是一个递推和数列，从第三项开始为前两项之和。

$f(n) = f(n-1) + f(n-2) + ...$

$f(n) = f(n-1) * f(n-2) * ...$

等递推公式

7. 多人传球

$M$ 个人传 $N$ 次球，有多少种传球方式： $X = \frac{(M-1)^N}{M}$

与 $X$ 最接近的整数：最终传给“非自己”的某人。
与 $X$ 第二接近的整数：最终传给自己。

解题方法

（一）特殊优先

题目: 某一个或几个元素在指定位置或不在指定位置。
原则: 谁特殊，优先谁！

位置优先 或 元素优先。

（二）捆绑法

主体相邻，捆绑法。
内部排列 + 外部打包排列

先捆绑，整体排列完再内部排。

（三）插空法

主体不相邻，不能连着/连续不能挨着。
技巧: 先排其他，再插“不相邻”。

(1) $N$ 个物体 $N+1$ 个空（包括两端），物体之间 $N-1$ 个空。 不相邻对象去插另一对象的空（不是反过来）， $N$ 个物体 $N+1$ 个空（包括两端），物体之间 $N-1$ 个空。

(2) 先单独将被插空对象排列，再插空。

(3) 两种主体都不能连续，多数量主体插少数量主体的空（包括两端）。

（四）插板法

相同元素分配问题，每组至少分到多少个

(1) 相同元素分配（说明不需排列，无顺序）；

(2) 每组至少分一个；

(3) 所分组不同。

$M$ 个元素分成 $N$ 组，每组至少 1 个： $C(M-1, N-1)$ 种方法

(1) $M$ 个元素分成 $N$ 组，每组至少 1 个： $C_{M-1}^{N-1}$ 种方法。

(2) $M$ 个元素分成 $X$ 个：转化成每组至少 1 个。

先每组分 $X-1$ 个，剩 $M-(X-1)N$ 个，再按每组至少 1 个分，共 $C_{N-1}^{[M-(X-1)N]-1}$ 种。

例 1. 3 个人分 5 个苹果，每人至少一个，有多少种分法？

解析: 等价于“ $x + y + z = 5$ 有多少组正整数解？”用隔板法，答案为 $C(4, 2)$ 。

（五）逆向计数法

正难则反，逆向计数。
正面情况多，反面情况少。

例 1. 某班有 50 名学生，其中 20 名男生，30 名女生。从中选出 3 名学生，至少有 1 名男生，有多少种选法？

解析: 正面情况多，反面情况少。解法一：我们需要从 50 名学生中选出 3 名学生，且至少有 1 名男生。我们可以通过以下步骤来解决这个问题：

计算总的选法数：从 50 名学生中选出 3 名学生的总选法数是： $\binom{50}{3} = \frac{50 \times 49 \times 48}{3 \times 2 \times 1} = 19600$
计算没有男生的选法数：没有男生的情况意味着选出的 3 名学生全是女生。班上有 30 名女生，从中选出 3 名女生的选法数是： $\binom{30}{3} = \frac{30 \times 29 \times 28}{3 \times 2 \times 1} = 4060$
计算至少有 1 名男生的选法数：至少有 1 名男生的选法数等于总选法数减去没有男生的选法数： $\binom{50}{3} - \binom{30}{3} = 19600 - 4060 = 15540$

因此，至少有 1 名男生的选法数是： $\boxed{15540}$

解法二：要解这个问题，我们可以通过计算总的选择方法，然后减去全是女生的选择方法。

计算总的选择方法：从 50 名学生中选择 3 名，不考虑性别。使用组合数的计算方法，这可以表示为 C(50, 3)。 $C(50, 3) = \frac{50!}{3!(50-3)!} = \frac{50 \times 49 \times 48}{3 \times 2 \times 1} = 19600$
计算全是女生的选法：从 30 名女生中选择 3 名。这可以表示为 C(30, 3)。 $C(30, 3) = \frac{30!}{3!(30-3)!} = \frac{30 \times 29 \times 28}{3 \times 2 \times 1} = 4060$
计算至少有 1 名男生的选法：总的选择方法减去全是女生的选法，即 19600 - 4060 = 15540。因此，从这 50 名学生中选出 3 名学生，且其中至少有 1 名男生的选择方法共有 15540 种。

例题讲解

例1：四对情侣排成一队买演唱会门票，已知每对情侣必须排在一起，问共有多少种不同的排队顺序?

A.24 种
B.96 种
C.384 种
D.40320 种

解析: 捆绑法。

每对情侣捆绑在一起，相当于 4 对情侣排成一排，有 $A_4^4 = 24$ 种排法。
每对情侣内部有 $A_2^2 = 2$ 种排法，所以总共有 $24 \times 2 \times 2 \times 2 \times 2 = 384$ 种排法。
C。

例2：某市举办经济建设成就展，计划在六月上旬组织5个单位参观，其中1个单位由于人数较多，需要连续参观2天，其他4个单位只需参观1天，若每天最多只能安排一个单位参观，则参观的时间安排共有（）种。

A.650
B.700
C.15120
D.16800

捆绑法。连续参观2天看作一个整体，6月上旬一共10天，将整体的2天和其他8天看作9个时段，安排5个单位参观，有A9 5=15120种。C。 捆绑的两天不用排列。

例3：将7个大小相同的桔子分给4个小朋友，要求每个小朋友至少得到1个桔子，一共有几种分配方法？

A.14
B.18
C.20
D.22

解析: 插板法，7 个桔子分 4 人，每人至少一个，相当于在中间 6 个空插 3 个板，则共有 $C_6^3 = 20$ 种。C。

例4：某企业选拔170多名优秀人才平均分配为7组参加培训。在选拔出的人才中，党员人数比非党员多3倍。接受培训的党员中的10%在培训结束后被随机派往甲单位等12个基层单位进一步锻炼。已知每个基层单位至少分配1人，问甲单位分配人数多于1的概率在以下哪个范围内？

A.不到14%
B.14％-17％之间
C.17%-20%之间
D.超过20%

解析：（1）170多人且是7的倍数，则总人数应为175，党员和非党员比例4:1，分别为140和35，所以14个党员分配给12个单位C14 12。（2）甲分配多于1只有两种情况，第一种情况：甲 3 人，其他单位全是 1 人，只有 1 种情况。

第二种情况：甲 2 人，其他单位一个 2，其他全是 1，相当于 12 个人分到 11 个单位每个单位至少 1 人，插空 $C_{11}^{10} = 11$ 种情况，共 11 + 1 = 12 种情况。

概率为 $12 \div C_{14}^{12} = 12 / 78$ ，B。

方法 2：反面即甲分配 1 个，剩下 13 分配给 11 个人，插板 $C_{12}^{10} = 66$ ，概率为 $(78 - 66) \div 78 = 12 / 78$ 。正面分两种，反面只有一种情况。B。

例5：某论坛邀请了六位嘉宾，安排其中三人进行单独演讲，另三人参加圆桌对话节目。如每位嘉宾都可以参加演讲或圆桌对话，演讲顺序分先后且圆桌对话必须安排在任意两场演讲之间，问一共有多少种不同的安排方式？

A. 120
B. 240
C. 480
D. 1440

解析：插空法。圆桌对话须在任意两场演讲之间，则：（1）圆桌对话相邻; （2）圆桌不能在演讲两端。六人中选三人按先后演讲，有 $A_6^3 = 120$ 种，三场演讲之间两个空，圆桌对话有 $C_2^1 = 2$ 种，共 $120 \times 2 = 240$ 。B。

例6：把12棵同样的松树和6棵同样的柏树种植在道路两侧，每侧种植9棵，要求每侧的柏树数量相等且不相邻，且道路起点和终点处两侧种植的都必须是松树。问有多少种不同的种植方法？

A.36
B.50
C.100
D.400

解析:

每侧 3 棵柏树，9 - 3 = 6 棵松树。
“不相邻”插空，柏树不相邻，两端是松树，则柏树只能插在松树中间，6 棵松树中间有 5 个空，故柏树有 $C_5^3 = 10$ 种。
“两侧”则有 $C_5^3 C_5^3 = 100$ 种。C。【树都一样，而且两边各 9 固定，不需再排列】。

例7：四位厨师聚餐时各做一道拿手菜。现在要求每人去品尝一道菜，但不能尝自己的那道。问共有几种不同尝法？

A.6 种
B.9 种
C.12 种
D.15 种

解析: 错位排列： $D_4 = 9$ 。B。

例8： 5个瓶子都贴了标签，其中恰好贴错了三个，则错的可能情况有几种？

A.6
B.10
C.12
D.20

解析: 先贴错的3个找出来，再3个错位排列， $D_3 \times C_5^3 = 20$ 。D。

例9：某部门从8名员工中选派4人参加培训，其中2人参加计算机培训，1人参加英语培训，1人参加财务培训，问不同的选法有多少种？

A.256
B.840
C.1680
D.5040

解析: 整体分步讨论，8 选 2 参加计算机， $C_8^2 = 28$ 剩余 6 选 1 参加英语， $C_6^1 = 6$ ，剩余 5 选 1 参加财务， $C_5^1 = 5$ ，总情况为 $C_8^2 C_6^1 C_5^1 = 840$ ，或 $C_8^4 C_4^2 A_2^1 = 840$ 或 $C_8^4 C_4^2 C_2^1 C_1^1 = 840$ B

例10：有5对夫妇参加一场婚宴，他们被安排在一张10个座位的圆桌就餐，但是婚礼操办者并不知道他们彼此之间的关系，只是随机安排座位。问5对夫妇恰好都被安排在一起相邻而坐的概率是多少?

A. 在1‰到5‰之间
B. 在5‰到1％之间
C. 超过1％
D. 不超过1‰

解析: 圆周排列，5 对夫妻先打包环形排列有 $A_4^4$ 种，每对夫妻之间有 2 种，则

$A_4^4 \times 2^5 / A_9^9 = 4 / (210 \times 9) \approx 2 / 1000$ A

例11：某单位组织的羽毛球男单比赛共有48名选手报名参加，比赛采用淘汰赛制，在比赛中负一场的选手即被淘汰，直至决出最后的冠军，如每名选手每天最多参加一场比赛，则比赛至少需要举行几天?

解析：按轮淘汰。要使比赛天数最少，则每天比赛选手尽可能多，加之每名选手每天最多参加一场比赛，第一天总共比赛48÷2=24场，还剩24名；第二天24÷2=12场，剩12 名；第三天12÷2=6场，剩6名；第四天6÷2=3场，剩3名；第五天选2人比赛，淘汰1人；第六天，剩下的2人决出冠军。至少6天。C

例12： 16支球队分两组，每组打单循环赛，共需打多少场比赛？

A．16
B．56
C．64
D.120

解析: 单循环赛，则每组比赛有 $C_8^2 = 28$ 场，两组共需打 $28 \times 2 = 56$ 场。B。

例13：四人进行篮球接球练习，要求每人接球后再传给别人。开始由甲发球，并作为第一次传球，若第五次传球后，球又回到甲手中，则共有传球方式（）种。

A.60 种
B.65 种
C.70 种
D.75 种

根据传球公式， $M$ 个人传 $N$ 次球，4 个人传 5 次球，则

$X = \frac{(M-1)^N}{M} = \frac{(4-1)^5}{4} = 60.75$

与 $X$ 第二接近的整数是最终传回自己手中的方法数，最接近整数是 61，第二接近整数是 60。A。

例14：某县通过发展旅游业来实现乡村振兴，引进了甲、乙、丙、丁、戊和己6名专家。其中甲、乙、丙是环境保护专家，丁、戊、己是旅游行业专家，甲、丁、戊熟悉社交媒体宣传。现要将6 名专家平均分成2个小组，每个小组都要有环境保护专家、旅游行业专家和熟悉社交媒体宣传的人，问有多少种不同的分组方式?

A.12
B.24
C.4
D.8

解析: 随机选三个分到一组，剩余为另一组，方法数为 $C_6^3$ ，涉及均匀分组问题，故为： $\frac{C_6^3}{A_2^2} = 10$ 种，剔除 2 种不符合的情况（甲乙丙、丁戊己）（甲丁戊、乙丙丁），还剩 $10 - 2 = 8$ 种。D。

例15：某班同学要订 A、B、C、D 四种学习报，每人至少订一种，最多订四种，那么每个同学有多少种不同的订报方式？

A.7 种
B.12 种
C.15 种
D.21 种

解析: 方法 1: $C_4^1 + C_4^2 + C_4^3 + C_4^4 = 15$ ，C。
方法 2: 每份报纸分两种情况：订和不订，所有可能 = 不订 = 2 × 2 × 2 × 2 - 1 = 15。

溶液问题概率问题