排列组合

（一）排列和排列数

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)$ 个元素的所有组合的个数

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

2. $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

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. 平均分组

全部平均分组

1. 有 $n$ 个组，元素个数相同，只需要分组不用排列。

2. 排列总情况数 ÷ $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$ 支队伍进行循环赛

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

一般意义上的循环赛，

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

2. 双循环:

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

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

淘汰赛:

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

1. 按轮淘汰:

$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$。

2. 按场淘汰

3. $N$ 个人比赛，决出冠亚军，比赛场次 = $N - 1$

4. $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}$

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

解题方法

（一）特殊优先

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

位置优先 或 元素优先。

（二）捆绑法

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

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

（三）插空法

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

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

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

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

（四）插板法

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

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

(2) 每组至少分一个；

(3) 所分组不同。

2. $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. 正难则反，逆向计数。
2. 正面情况多，反面情况少。

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

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

1. 计算总的选法数： 从 50 名学生中选出 3 名学生的总选法数是： $\binom{50}{3} = \frac{50 \times 49 \times 48}{3 \times 2 \times 1} = 19600$

2. 计算没有男生的选法数： 没有男生的情况意味着选出的 3 名学生全是女生。班上有 30 名女生，从中选出 3 名女生的选法数是： $\binom{30}{3} = \frac{30 \times 29 \times 28}{3 \times 2 \times 1} = 4060$

3. 计算至少有 1 名男生的选法数： 至少有 1 名男生的选法数等于总选法数减去没有男生的选法数： $\binom{50}{3} - \binom{30}{3} = 19600 - 4060 = 15540$

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

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

1. 计算总的选择方法：从 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$
2. 计算全是女生的选法：从 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$
3. 计算至少有 1 名男生的选法：总的选择方法减去全是女生的选法，即 19600 - 4060 = 15540。 因此，从这 50 名学生中选出 3 名学生，且其中至少有 1 名男生的选择方法共有 15540 种。

例题讲解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• A.4
• B.5
• C.6
• D.7

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

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

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

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

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

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

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

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