# 第 6 章 数学和逻辑

## 6.1 组合数学基础

### 1、排列组合的基础知识

（1）两个基础问题
* 问题一：从甲、乙、丙 3 名同学中选出 2 名去参加某天一项活动，有多少种不同的选法？写出这些选法？
  * 解析：甲、乙；甲、丙；乙、丙。共 3 种。
* 问题二：从甲、乙、丙 3 名同学中选出 2 名去参加某天的一项活动，其中 1 名同学参加上午的活动，1 名同学参加下午的活动，有多少种不同的选法，写出这些选法？
  * 解析：选甲乙去：甲、乙；乙、甲；选甲丙去：甲、丙；丙、甲；选乙丙去：乙、丙；丙、乙。共 6 种。

（2）排列组合的定义
* 组合的定义：从 n 个不同元素中取出 $m (m \le n)$ 个元素并成一组，叫做从 n 个不同元素中取出 m 个元素的一个组合。
* 排列的定义：从 n 个不同元素中取出 $m (m \le n)$ 个元素，按照一定的顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列。
* 注意掌握它们的区别：排列与元素的顺序有关，而组合则与元素的顺序无关。

（3）请判断如下问题是组合问题还是排列问题？
* (a) 设集合 $A=\{a,b,c,d,e\}$，则集合 A 的含有 3 个元素的子集有多少个？——**组合问题**
* (b) 某铁路线上有 5 个车站，则这条铁路线上共需准备多少种车票？——**排列问题**
* (c) 10 名同学分成人数相同的数学和英语两个学习小组，共有多少种分法？——**组合问题**
* (d) 10 人聚会，见面后每两人之间要握手相互问候，共需握手多少次？——**组合问题**
* (e) 从 4 个风景点中选出 2 个游览，有多少种不同的方法？——**组合问题**
* (f) 从 4 个风景点中选出 2 个，并确定这 2 个风景点的游览顺序，有多少种不同的方法？——**排列**

（4）请尝试写出 $a, b, c$ 这 3 个元素，选取 2 个元素的排列和组合的结果分别有哪些？
* 组合结果：$ab, ac, bc$
* 排列结果：$ab, ac, ad, bc, bd, cd$ （注：此处原文档OCR存在字面识别瑕疵，规范逻辑为排列包含顺序）

---

### 2、排列
从 n 个不同元素中取出 $m (m \le n)$ 个元素的所有排列的个数，叫做从 n 个不同元素中取出 m 个元素的排列数，用符号 $A_n^m$ 表示（也可写为 $P_n^m$）。

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

* 问题 1：分别从 3 个不同的乒乓球中选择 2 个乒乓球依次放在 2 个不同的盒子里，每个盒子各 1 个，求有多少种不同的选择方法？
  * $A_3^2 = 6$
* 问题 2：分别从 6 个不同的乒乓球中选择 3 个乒乓球，依次放在 3 个不同的盒子里，每个盒子 1 个，请问有多少种放法？
  * $A_6^3 = 120$

---

### 3、组合
从 n 个不同元素中取出 $m (m \le n)$ 个元素的所有组合的个数，叫做从 n 个不同元素中取出 m 个元素的组合数，用符号 $C_n^m$ 表示。

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

例子：计算如下算式的运算结果
* (a) $C_7^4 = 35$
* (b) $C_{10}^3 = 120$
* (c) 已知 $C_n^3 = A_n^2$，求 n 的值？—— $n = 8$

例子：甲、乙、丙、丁 4 支足球队举行单循环赛；
(1) 各队要举办多少场比赛？列出所有各场比赛的双方；
* 答案：$C_4^2 = 6$。甲乙、甲丙、甲丁、乙丙、乙丁、丙丁。
(2) 有多少种冠亚军的组合？列出所有冠亚军的可能情况；
* 答案：$A_4^2 = 12$。甲乙、甲丙、甲丁、乙丙、乙丁、丙丁、乙甲、丙甲、丁甲、丙乙、丁乙、丁丙。

---

例子：一位教练的足球队共有 17 名初级学员，他们中以前没有一人参加过比赛。按照足球比赛规则，比赛时一个足球队的上场队员是 11 人；
(1) 这位教练从这 17 名学员中可以形成多少种学员上场方案？
* 答案：$C_{17}^{11} = 12376$
(2) 如果在选出 11 名上场队员时，还要确定其中的守门员，那么教练员有多少种方式做这件事情？
* 答案：$C_{17}^{11} \times C_{11}^1 = 136136$ 或 $C_{17}^1 \times C_{16}^{10} = 136136$

例子：
(1) 平面内有 10 个点，以其中每 2 个点为端点的线段共有多少条？
* 答案：$C_{10}^2 = 45$
(2) 平面内有 10 个点，以其中每 2 个点为端点的有向线段共有多少条？
* 答案：$A_{10}^2 = 90$

例子：
(1) 凸五边形有多少条对角线？
* 答案：$C_5^2 - 5 = 10 - 5 = 5$
(2) 凸 n（$n>3$）边形有多少条对角线？
* 答案：$C_n^2 - n = \frac{n^2-3n}{2}$ （n 点取 2 个点是所有的线 – n 条边，剩余的是对角线）

---

### 4、排列组合解题技巧

#### （1）知识点小结
* **A、分类计数原理**：做一件事情，完成它可以有 n 类办法，在第一类办法中有 $m_1$ 种不同的方法，在第二类办法中有 $m_2$ 种不同的方法，……，在第 n 类办法中有 $m_n$ 种不同的方法，那么完成这件事共有 $N = m_1 + m_2 + \dots + m_n$ 种不同的方法。
* **B、分步计数原理**：做一件事情，完成它需要分成 n 个步骤，做第一步有 $m_1$ 种不同的方法，做第二步有 $m_2$ 种不同的方法，……，做第 n 步有 $m_n$ 种不同的方法，那么完成这件事有 $N = m_1 \times m_2 \times \dots \times m_n$ 种不同的方法。
* **C、可重排列**：在 m 个不同的元素中，每次取出 n 个元素，元素可以重复出现，按照一定的顺序那么第一、第二……第 n 位是的选取元素的方法都是 m 种；所以从 m 个不同的元素中，每次取出 n 个元素的可重复的排列数为 $m^n$。
* **D、解排列组合问题**
  ① 要弄清一件事是“分类”还是“分步”完成；
  ② 对于元素之间的关系，还要考虑是“有序的”还是“无序的”，也就是会正确使用分类计数原理和分步计数原理、排列定义和组合定义；

#### （2）解题技巧
* **技巧 1：相邻问题——整体捆绑法。**
  * 例：7 名学生站成一排，甲、乙必须站在一起，有多少不同排法？
  * 解：先将甲乙二人看作一个元素与其他五人进行排列，并考虑甲乙二人的内部顺序，共有 $A_6^6 \times A_2^2 = 1440$ 种。
* **技巧 2：不相邻问题——选空插入法。**
  * 例：7 名学生站成一排，甲乙互不相邻，有多少不同排法？
  * 解：甲、乙二人不相邻的排法一般应用“插空”法，计算应为：$A_5^5 \times A_6^2 = 3600$ 种。
* **技巧 3：复杂问题——总体排除法或排异法。**
  * 例：正六边形的中心和顶点共 7 个点，以其中 3 个点为顶点的三角形共有几个。
  * 解：从 7 个点中取 3 个点的取法有 $C_7^3$ 种，但其中正六边形的对角线所含的中心和顶点三点共线不能组成三角形，有 3 条，所以满足条件的三角形共有 $C_7^3 - 3 = 32$ 个。
* **技巧 4：特殊元素——优先考虑法。**
  * 例：乒乓球队的 10 名队员中有 3 名主力队员，派 5 名队员参加比赛，3 名主力队员要安排在第一、三、五位置，其余 7 名队员选 2 名安排在第二、四位置，那么不同的出场安排共有多少种。
  * 解：由于第一、三、五位置特殊，只能安排主力队员，有 $A_3^3$ 种排法，而其余 7 名队员选出 2 名安排在第二、四位置，有 $A_7^2$ 种排法，所以不同的出场安排共有 $A_3^3 \times A_7^2 = 252$ 种。
* **技巧 5：多元问题——分类讨论法。**
  * 例：某班新年联欢会原定的 5 个节目已排成节目单，开演前又增加了两个新节目；如果将这两个节目插入原节目单中，那么不同插法的种数为多少。
  * 解：增加的两个新节目，可分为相邻与不相邻两种情况：(1) 不相邻：$A_6^2$ 种；(2) 相邻：$A_2^2 \times A_6^1$ 种。故总数 $30 + 12 = 42$ 种。或用总体排除：$A_7^7 / A_5^5 = 42$ 种。
* **技巧 6：混合问题——先选后排法。**
  * 例：从黄瓜、白菜、油菜、扁豆 4 种蔬菜品种中选出 3 种，分别种在不同土质的三块土地上，其中黄瓜必须种植，不同的种植方法共有多少种。
  * 解：先选后排，分步实施。不同的选法有 $C_3^2$ 种，不同的排法有 $A_3^3$ 种，故不同的种植方法共有 $C_3^2 \times A_3^3 = 18$ 种。
* **技巧 7：相同元素分配——档板分隔法。**
  * 例：把 10 本相同的书发给编号为 1，2，3 的三个学生阅览室，每个阅览室分得的书的本数不小于其编号数，试求不同分法的种数。
  * 解：先分别给 1、2、3 号阅览室分配 0、1、2 本书，然后把剩下的 7 本书分配给这 3 个阅览室，要求每个阅览室至少再分到 1 本。在 7 本书中有 6 个空，任意选取 2 个空，即可把这 7 本书分成左、中、右 3 个部分，所以不同的分法共有 $C_6^2 = 15$。
* **技巧 8：转化法。**
  * 例：高二年级 8 个班，组织一个 12 个人的年级学生分会，每班要求至少 1 人，名额分配方案有几种？
  * 解：可以转化为：插板问题，结果为 $C_{11}^7 = 330$。

---

### 5、关于排列组合问题的小结
一、分清排列（先取再排）和组合（只取不排），按指定的一种顺序排列的问题，实质是组合问题。
二、基本的解题方法：
1. 特优法：优先处理特殊元素（位置）法；
2. 捆绑法：某些元素要求必须相邻时，可以先将这些元素看作一个元素，与其他元素排列后，再考虑相邻元素的内部排列；
3. 插空法：某些元素不相邻排列时，可以先排其他元素，再将这些不相邻元素插入空档；
4. 对于含“至多”、“至少”的问题，宜用排除法或分类解决；涉及“多面手”的问题，一般分类解决；
5. 不同元素的均匀分组：将 $mn$ 个不同元素均匀分成 n 组，有 $\frac{C_m^m C_{m-1}^m \dots C_m^m}{A_n^n}$ 种分法；
6. 挡板法：相同元素分配问题，将 n 个相同元素分给 m 个不同单位，每个单位至少一个元素，有 $C_{n-1}^{m-1}$ 种分法。

---

## 6.2 常用的原理小结

### 1、容斥原理
容斥原理是在计数时，必须确保没有重复，没有遗漏，使重叠部分不被重复计算。
基本思想是：
1、先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来；
2、然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复。

如果被计数的事物有 A、B、C 三类，那么：
$A \cup B \cup C = A + B + C - A \cap B - B \cap C - C \cap A + A \cap B \cap C$

* 例如：一次期末考试，某班有 15 人数学得满分，有 12 人语文得满分，并且有 4 人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？
  * 答案：$15 + 12 - 4 = 23$ 人。

【NOIP2018 普及组】13. 10000 以内，与 10000 互质的正整数有（ ）个。
A. 2000 
B. 4000 
C. 6000 
D. 8000
答案：B
解析：互质的意思，与 10000 没有公约数，即不能被 10000 的质因子整除。
$10000 = 2^4 \times 5^4$
10000 以内被 2 整除的数有 5000 个；被 5 整除的数有 2000 个；被 10 整除的数有 1000 个。
被 2 或 5 整除的数有：$5000 + 2000 - 1000 = 6000$ 个。
互质的数有：$10000 - 6000 = 4000$ 个。

---

### 2、鸽巢原理/抽屉原理
抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有 $n+1$ 个元素放到 n 个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。
抽屉原理的另一个表达：如果有 n 个集合和 $kn+1$ 个元素，将元素放入集合中之后，至少有 1 个集合中有 $k+1$ 个元素。

* 例子：属相是有 12 个，那么任意 37 个人中，一个属相至少不少于多少个人？
  * 答案：4 人。($37 / 12 = 3$ 余 1，向上取整得 $3+1=4$)。

【NOIP2019 普及组】12. 一副纸牌除掉大小王有 52 张牌，四种花色，每种花色 13 张。假设从这 52 张牌中随机抽取 13 张纸牌,则至少（ ）张牌的花色一致。
A. 4 
B. 2 
C. 3 
D. 5
答案：A
解析：抽屉原理，最坏情况，13 张牌对应四种花色的牌数为 3、3、3、4。这时再抽一张，不管放在哪，都能满足要求（即有 4 张花色一致）。

---

## 6.3 逻辑

1. 今天是星期日，那么 100 天以后是星期几？
   * 解析：$100 \div 7 = 14$ 余 2，因此相当于 2 天之后，答案是星期二。
2. 今天是星期日，那么 $10^{100}$ 天以后是星期几？
   * 解析：根据余数循环规律， $10^{100}$ 的指数 100 除以 6 余 4，对应余数为 4 的星期四。
3. 2017 年 10 月 1 日是星期日，1999 年 10 月 1 日是（ ）。
   * A. 星期三 
   * B. 星期日 
   * C. 星期五 
   * D. 星期二
   * 答案：C（总天数计算后模 7 推进推算）。
4. 一个人站在坐标（0, 0）处，面朝 x 轴正方向。第一轮，他向前走 1 单位距离，然后右转；第二轮，他向前走 2 单位距离，然后右转；第三轮，他向前走 3 单位距离，然后右转……他一直这么走下去。请问第 2017 轮后，他的坐标是：（1009, 1008）。

---

## 6.4 前缀、中缀、表达式

* **前缀表达式**（波兰式）：运算符位于操作数之前，如 `- \times + 3 4 5 6`。求值时从右至左扫描。
* **中缀表达式**：常见的运算表达式，如 `(3+4) \times 5 - 6`。
* **后缀表达式**（逆波兰表达式）：运算符位于操作数之后，如 `3 4 + 5 \times 6 -`。求值时从左至右扫描。

【NOIP2010 提高组】前缀表达式“`+3*2+5 12`”的值是（ ）
A. 23 
B. 25 
C. 37 
D. 65
答案：C

【NOIP2017 普及组】表达式 `a * (b + c) * d` 的后缀形式是（ ）。
A. `a b c d * + *` 
B. `a b c + * d *` 
C. `a * b c + * d` 
D. `b + c * a * d`
答案：B

---

## 6.5 数学和逻辑课堂练习

* 【NOIP2019 普及组】7. 把 8 个同样的球放在 5 个同样的袋子里,允许有的袋子空着不放,问共有多少种不同的分法？
  * 答案：C（18 种，枚举法求解）。
* 【NOIP2019 提高组】10. 一次期末考试，某班有 15 人数学得满分，有 12 人语文得满分，并且有 4 人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？
  * 答案：A（23 人）。
* 【NOIP2018 普及组】6. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照 CapsLock、A、S、D、F 的顺序循环按键，屏幕上输出的第 81 个字符是字母（ ）。
  * 答案：A（周期为 8，81 % 8 = 1）。
* 【NOIP2018 普及组】12. 设含有 10 个元素的集合的全部子集数为 S，其中由 7 个元素组成的子集数为 T，则 T / S 的值为（ ）。
  * 答案：B（15 / 128）。
* 【NOIP2017 提高组】9. 将 7 个名额分给 4 个不同的班级，允许有的班级没有名额，有( )种不同的分配方案。
  * 答案：D（120 种，隔板法 $C_{10}^3 = 120$）。
* 【NOIP2017 普及组】9. 甲、乙、丙三位同学选修课程，从 4 门课程中，甲选修 2 门，乙、丙各选修 3 门，则不同的选修方案共有（ ）种。
  * 答案：C（96 种）。

第 6 章数学和逻辑

6.1 组合数学基础

1、排列组合的基础知识

（1）两个基础问题 * 问题一：从甲、乙、丙 3 名同学中选出 2 名去参加某天一项活动，有多少种不同的选法？写出这些选法？ * 解析：甲、乙；甲、丙；乙、丙。共 3 种。 * 问题二：从甲、乙、丙 3 名同学中选出 2 名去参加某天的一项活动，其中 1 名同学参加上午的活动，1 名同学参加下午的活动，有多少种不同的选法，写出这些选法？ * 解析：选甲乙去：甲、乙；乙、甲；选甲丙去：甲、丙；丙、甲；选乙丙去：乙、丙；丙、乙。共 6 种。

（2）排列组合的定义 * 组合的定义：从 n 个不同元素中取出 $m (m \le n)$ 个元素并成一组，叫做从 n 个不同元素中取出 m 个元素的一个组合。 * 排列的定义：从 n 个不同元素中取出 $m (m \le n)$ 个元素，按照一定的顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列。 * 注意掌握它们的区别：排列与元素的顺序有关，而组合则与元素的顺序无关。

（3）请判断如下问题是组合问题还是排列问题？ * (a) 设集合 $A={a,b,c,d,e}$，则集合 A 的含有 3 个元素的子集有多少个？——组合问题 * (b) 某铁路线上有 5 个车站，则这条铁路线上共需准备多少种车票？——排列问题 * (c) 10 名同学分成人数相同的数学和英语两个学习小组，共有多少种分法？——组合问题 * (d) 10 人聚会，见面后每两人之间要握手相互问候，共需握手多少次？——组合问题 * (e) 从 4 个风景点中选出 2 个游览，有多少种不同的方法？——组合问题 * (f) 从 4 个风景点中选出 2 个，并确定这 2 个风景点的游览顺序，有多少种不同的方法？——排列

（4）请尝试写出 $a, b, c$ 这 3 个元素，选取 2 个元素的排列和组合的结果分别有哪些？ * 组合结果：$ab, ac, bc$ * 排列结果：$ab, ac, ad, bc, bd, cd$ （注：此处原文档OCR存在字面识别瑕疵，规范逻辑为排列包含顺序）

2、排列

从 n 个不同元素中取出 $m (m \le n)$ 个元素的所有排列的个数，叫做从 n 个不同元素中取出 m 个元素的排列数，用符号 $A_n^m$ 表示（也可写为 $P_n^m$）。

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

问题 1：分别从 3 个不同的乒乓球中选择 2 个乒乓球依次放在 2 个不同的盒子里，每个盒子各 1 个，求有多少种不同的选择方法？
$A_3^2 = 6$
问题 2：分别从 6 个不同的乒乓球中选择 3 个乒乓球，依次放在 3 个不同的盒子里，每个盒子 1 个，请问有多少种放法？
$A_6^3 = 120$

3、组合

从 n 个不同元素中取出 $m (m \le n)$ 个元素的所有组合的个数，叫做从 n 个不同元素中取出 m 个元素的组合数，用符号 $C_n^m$ 表示。

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

例子：计算如下算式的运算结果 * (a) $C_7^4 = 35$ * (b) $C_{10}^3 = 120$ * (c) 已知 $C_n^3 = A_n^2$，求 n 的值？—— $n = 8$

例子：甲、乙、丙、丁 4 支足球队举行单循环赛； (1) 各队要举办多少场比赛？列出所有各场比赛的双方； * 答案：$C_4^2 = 6$。甲乙、甲丙、甲丁、乙丙、乙丁、丙丁。 (2) 有多少种冠亚军的组合？列出所有冠亚军的可能情况； * 答案：$A_4^2 = 12$。甲乙、甲丙、甲丁、乙丙、乙丁、丙丁、乙甲、丙甲、丁甲、丙乙、丁乙、丁丙。

例子：一位教练的足球队共有 17 名初级学员，他们中以前没有一人参加过比赛。按照足球比赛规则，比赛时一个足球队的上场队员是 11 人； (1) 这位教练从这 17 名学员中可以形成多少种学员上场方案？ * 答案：$C_{17}^{11} = 12376$ (2) 如果在选出 11 名上场队员时，还要确定其中的守门员，那么教练员有多少种方式做这件事情？ * 答案：$C_{17}^{11} \times C_{11}^1 = 136136$ 或 $C_{17}^1 \times C_{16}^{10} = 136136$

例子： (1) 平面内有 10 个点，以其中每 2 个点为端点的线段共有多少条？ * 答案：$C_{10}^2 = 45$ (2) 平面内有 10 个点，以其中每 2 个点为端点的有向线段共有多少条？ * 答案：$A_{10}^2 = 90$

例子： (1) 凸五边形有多少条对角线？ * 答案：$C_5^2 - 5 = 10 - 5 = 5$ (2) 凸 n（$n>3$）边形有多少条对角线？ * 答案：$C_n^2 - n = \frac{n^2-3n}{2}$ （n 点取 2 个点是所有的线 – n 条边，剩余的是对角线）

4、排列组合解题技巧

（1）知识点小结

A、分类计数原理：做一件事情，完成它可以有 n 类办法，在第一类办法中有 $m_1$ 种不同的方法，在第二类办法中有 $m_2$ 种不同的方法，……，在第 n 类办法中有 $m_n$ 种不同的方法，那么完成这件事共有 $N = m_1 + m_2 + \dots + m_n$ 种不同的方法。
B、分步计数原理：做一件事情，完成它需要分成 n 个步骤，做第一步有 $m_1$ 种不同的方法，做第二步有 $m_2$ 种不同的方法，……，做第 n 步有 $m_n$ 种不同的方法，那么完成这件事有 $N = m_1 \times m_2 \times \dots \times m_n$ 种不同的方法。
C、可重排列：在 m 个不同的元素中，每次取出 n 个元素，元素可以重复出现，按照一定的顺序那么第一、第二……第 n 位是的选取元素的方法都是 m 种；所以从 m 个不同的元素中，每次取出 n 个元素的可重复的排列数为 $m^n$。
D、解排列组合问题 ① 要弄清一件事是“分类”还是“分步”完成； ② 对于元素之间的关系，还要考虑是“有序的”还是“无序的”，也就是会正确使用分类计数原理和分步计数原理、排列定义和组合定义；

（2）解题技巧

技巧 1：相邻问题——整体捆绑法。
例：7 名学生站成一排，甲、乙必须站在一起，有多少不同排法？
解：先将甲乙二人看作一个元素与其他五人进行排列，并考虑甲乙二人的内部顺序，共有 $A_6^6 \times A_2^2 = 1440$ 种。
技巧 2：不相邻问题——选空插入法。
例：7 名学生站成一排，甲乙互不相邻，有多少不同排法？
解：甲、乙二人不相邻的排法一般应用“插空”法，计算应为：$A_5^5 \times A_6^2 = 3600$ 种。
技巧 3：复杂问题——总体排除法或排异法。
例：正六边形的中心和顶点共 7 个点，以其中 3 个点为顶点的三角形共有几个。
解：从 7 个点中取 3 个点的取法有 $C_7^3$ 种，但其中正六边形的对角线所含的中心和顶点三点共线不能组成三角形，有 3 条，所以满足条件的三角形共有 $C_7^3 - 3 = 32$ 个。
技巧 4：特殊元素——优先考虑法。
例：乒乓球队的 10 名队员中有 3 名主力队员，派 5 名队员参加比赛，3 名主力队员要安排在第一、三、五位置，其余 7 名队员选 2 名安排在第二、四位置，那么不同的出场安排共有多少种。
解：由于第一、三、五位置特殊，只能安排主力队员，有 $A_3^3$ 种排法，而其余 7 名队员选出 2 名安排在第二、四位置，有 $A_7^2$ 种排法，所以不同的出场安排共有 $A_3^3 \times A_7^2 = 252$ 种。
技巧 5：多元问题——分类讨论法。
例：某班新年联欢会原定的 5 个节目已排成节目单，开演前又增加了两个新节目；如果将这两个节目插入原节目单中，那么不同插法的种数为多少。
解：增加的两个新节目，可分为相邻与不相邻两种情况：(1) 不相邻：$A_6^2$ 种；(2) 相邻：$A_2^2 \times A_6^1$ 种。故总数 $30 + 12 = 42$ 种。或用总体排除：$A_7^7 / A_5^5 = 42$ 种。
技巧 6：混合问题——先选后排法。
例：从黄瓜、白菜、油菜、扁豆 4 种蔬菜品种中选出 3 种，分别种在不同土质的三块土地上，其中黄瓜必须种植，不同的种植方法共有多少种。
解：先选后排，分步实施。不同的选法有 $C_3^2$ 种，不同的排法有 $A_3^3$ 种，故不同的种植方法共有 $C_3^2 \times A_3^3 = 18$ 种。
技巧 7：相同元素分配——档板分隔法。
例：把 10 本相同的书发给编号为 1，2，3 的三个学生阅览室，每个阅览室分得的书的本数不小于其编号数，试求不同分法的种数。
解：先分别给 1、2、3 号阅览室分配 0、1、2 本书，然后把剩下的 7 本书分配给这 3 个阅览室，要求每个阅览室至少再分到 1 本。在 7 本书中有 6 个空，任意选取 2 个空，即可把这 7 本书分成左、中、右 3 个部分，所以不同的分法共有 $C_6^2 = 15$。
技巧 8：转化法。
例：高二年级 8 个班，组织一个 12 个人的年级学生分会，每班要求至少 1 人，名额分配方案有几种？
解：可以转化为：插板问题，结果为 $C_{11}^7 = 330$。

5、关于排列组合问题的小结

一、分清排列（先取再排）和组合（只取不排），按指定的一种顺序排列的问题，实质是组合问题。二、基本的解题方法： 1. 特优法：优先处理特殊元素（位置）法； 2. 捆绑法：某些元素要求必须相邻时，可以先将这些元素看作一个元素，与其他元素排列后，再考虑相邻元素的内部排列； 3. 插空法：某些元素不相邻排列时，可以先排其他元素，再将这些不相邻元素插入空档； 4. 对于含“至多”、“至少”的问题，宜用排除法或分类解决；涉及“多面手”的问题，一般分类解决； 5. 不同元素的均匀分组：将 $mn$ 个不同元素均匀分成 n 组，有 $\frac{C_m^m C_{m-1}^m \dots C_m^m}{A_n^n}$ 种分法； 6. 挡板法：相同元素分配问题，将 n 个相同元素分给 m 个不同单位，每个单位至少一个元素，有 $C_{n-1}^{m-1}$ 种分法。

6.2 常用的原理小结

1、容斥原理

容斥原理是在计数时，必须确保没有重复，没有遗漏，使重叠部分不被重复计算。基本思想是： 1、先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来； 2、然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复。

如果被计数的事物有 A、B、C 三类，那么： $A \cup B \cup C = A + B + C - A \cap B - B \cap C - C \cap A + A \cap B \cap C$

例如：一次期末考试，某班有 15 人数学得满分，有 12 人语文得满分，并且有 4 人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？
答案：$15 + 12 - 4 = 23$ 人。

【NOIP2018 普及组】13. 10000 以内，与 10000 互质的正整数有（）个。 A. 2000 B. 4000 C. 6000 D. 8000 答案：B 解析：互质的意思，与 10000 没有公约数，即不能被 10000 的质因子整除。 $10000 = 2^4 \times 5^4$ 10000 以内被 2 整除的数有 5000 个；被 5 整除的数有 2000 个；被 10 整除的数有 1000 个。被 2 或 5 整除的数有：$5000 + 2000 - 1000 = 6000$ 个。互质的数有：$10000 - 6000 = 4000$ 个。

2、鸽巢原理/抽屉原理

抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有 $n+1$ 个元素放到 n 个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。抽屉原理的另一个表达：如果有 n 个集合和 $kn+1$ 个元素，将元素放入集合中之后，至少有 1 个集合中有 $k+1$ 个元素。

例子：属相是有 12 个，那么任意 37 个人中，一个属相至少不少于多少个人？
答案：4 人。($37 / 12 = 3$ 余 1，向上取整得 $3+1=4$)。

【NOIP2019 普及组】12. 一副纸牌除掉大小王有 52 张牌，四种花色，每种花色 13 张。假设从这 52 张牌中随机抽取 13 张纸牌,则至少（）张牌的花色一致。 A. 4 B. 2 C. 3 D. 5 答案：A 解析：抽屉原理，最坏情况，13 张牌对应四种花色的牌数为 3、3、3、4。这时再抽一张，不管放在哪，都能满足要求（即有 4 张花色一致）。

6.3 逻辑

今天是星期日，那么 100 天以后是星期几？
解析：$100 \div 7 = 14$ 余 2，因此相当于 2 天之后，答案是星期二。
今天是星期日，那么 $10^{100}$ 天以后是星期几？
解析：根据余数循环规律， $10^{100}$ 的指数 100 除以 6 余 4，对应余数为 4 的星期四。
2017 年 10 月 1 日是星期日，1999 年 10 月 1 日是（）。
A. 星期三
B. 星期日
C. 星期五
D. 星期二
答案：C（总天数计算后模 7 推进推算）。
一个人站在坐标（0, 0）处，面朝 x 轴正方向。第一轮，他向前走 1 单位距离，然后右转；第二轮，他向前走 2 单位距离，然后右转；第三轮，他向前走 3 单位距离，然后右转……他一直这么走下去。请问第 2017 轮后，他的坐标是：（1009, 1008）。

6.4 前缀、中缀、表达式

前缀表达式（波兰式）：运算符位于操作数之前，如 - \times + 3 4 5 6。求值时从右至左扫描。
中缀表达式：常见的运算表达式，如 (3+4) \times 5 - 6。
后缀表达式（逆波兰表达式）：运算符位于操作数之后，如 3 4 + 5 \times 6 -。求值时从左至右扫描。

【NOIP2010 提高组】前缀表达式“+3*2+5 12”的值是（） A. 23 B. 25 C. 37 D. 65 答案：C

【NOIP2017 普及组】表达式 a * (b + c) * d 的后缀形式是（）。 A. a b c d * + * B. a b c + * d * C. a * b c + * d D. b + c * a * d 答案：B

6.5 数学和逻辑课堂练习

【NOIP2019 普及组】7. 把 8 个同样的球放在 5 个同样的袋子里,允许有的袋子空着不放,问共有多少种不同的分法？
答案：C（18 种，枚举法求解）。
【NOIP2019 提高组】10. 一次期末考试，某班有 15 人数学得满分，有 12 人语文得满分，并且有 4 人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？
答案：A（23 人）。
【NOIP2018 普及组】6. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照 CapsLock、A、S、D、F 的顺序循环按键，屏幕上输出的第 81 个字符是字母（）。
答案：A（周期为 8，81 % 8 = 1）。
【NOIP2018 普及组】12. 设含有 10 个元素的集合的全部子集数为 S，其中由 7 个元素组成的子集数为 T，则 T / S 的值为（）。
答案：B（15 / 128）。
【NOIP2017 提高组】9. 将 7 个名额分给 4 个不同的班级，允许有的班级没有名额，有( )种不同的分配方案。
答案：D（120 种，隔板法 $C_{10}^3 = 120$）。
【NOIP2017 普及组】9. 甲、乙、丙三位同学选修课程，从 4 门课程中，甲选修 2 门，乙、丙各选修 3 门，则不同的选修方案共有（）种。
答案：C（96 种）。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com