CSP-J 初赛排列组合专题讲义

一、为什么排列组合是重点？

排列组合是CSP-J初赛的必考、高频考点，几乎每年都会出现，平均一份试卷有2道左右的排列组合题。这部分内容也是初赛前面30分中难度最大的一个板块。掌握好排列组合，对冲击初赛高分至关重要。

二、两大计数原理（基石）

在开始排列组合之前，必须先理解两个最基本的计数原理。

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

做一件事，完成它有n 类办法。在第一类办法中有 m₁ 种方法，第二类中有 m₂ 种方法……第 n 类中有 mₙ 种方法，那么完成这件事共有：

N = m₁ + m₂ + … + mₙ种不同的方法。

核心判断标准：各类方案之间是并列关系（“或”的关系），选其中一类就能完成任务。

举例：从甲地到乙地，可以坐飞机（有3个航班）或坐火车（有4个班次），则共有 3 + 4 = 7 种方式。

2. 乘法原理（分步计数原理）

做一件事，需要分成n 个步骤。做第一步有 m₁ 种方法，做第二步有 m₂ 种方法……做第 n 步有 mₙ 种方法，那么完成这件事共有：

N = m₁ × m₂ × … × mₙ种不同的方法。

核心判断标准：各个步骤都要完成（“且”的关系），缺一不可。

举例：从甲地到乙地需要先坐飞机（3个航班）再坐火车（4个班次），则共有 3 × 4 = 12 种方式。

三、排列（Permutation）—— 讲究顺序

1. 定义

从n个不同元素中，任取m个（m ≤ n）不同的元素，按照一定的顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列。

关键词：顺序！排列关注的是“谁在前、谁在后”。

2. 公式

排列数记作 A(n, m) 或 P(n, m)：

A(n, m) = n × (n-1) × (n-2) × … × (n-m+1) = n! / (n-m)!

特殊地，当 m = n 时，就是 n 个元素的全排列：

A(n, n) = n!

3. 理解方式

以“6个人排队”为例：

• 第1个位置有6种选择

• 第2个位置剩5种选择

• 第3个位置剩4种选择

• ……

• 第6个位置剩1种选择

所以共有 6 × 5 × 4 × 3 × 2 × 1 = 720 种。

记忆口诀：排列就是“排队”。

四、组合（Combination）—— 不讲究顺序

1. 定义

从n个不同元素中，任取m个（m ≤ n）不同的元素并成一组，叫做从 n 个不同元素中取出 m 个元素的一个组合。

关键词：不讲究顺序！组合只关心“选了谁”，不关心“谁先谁后”。

2. 公式

组合数记作 C(n, m)：

C(n, m) = n! / [m! × (n-m)!]

3. 理解方式

以“10个苹果中取3个”为例：

• 如果考虑顺序，有 10 × 9 × 8 = 720 种

• 但组合不讲究顺序，3个苹果的内部顺序有 3! = 6 种

• 所以组合数为 720 / 6 = 120 种

记忆口诀：组合就是“选人”。

4. 组合的重要性质

性质一（对称性）：C(n, m) = C(n, n-m)

性质二（递推/帕斯卡恒等式）：C(n, m) = C(n-1, m) + C(n-1, m-1)

这个性质可以用来构造杨辉三角，在编程中避免直接计算阶乘。

性质三（总和）：C(n, 0) + C(n, 1) + … + C(n, n) = 2ⁿ

这体现了组合数学与二进制的深刻联系。

五、排列 vs 组合 —— 一张表搞定

从A、B、C三人中选两人：AB和BA是两种不同的排列，但却是同一种组合。

六、五大核心解题方法

方法1：特殊优先法

适用场景：题目中有特殊限制条件的元素。

核心思路：优先安排有特殊要求的元素，再处理其他无限制的元素。

例题：用0、1、2、3组成四位数，首位不能为0。

• 首位特殊，先安排首位：有3种选择（1、2、3）

• 其余三位从剩下3个数中排列：有 A(3,3) = 6 种

• 总数 = 3 × 6 = 18 种

方法2：捆绑法

适用场景：某些元素必须相邻（必须排在一起）。

操作步骤：

1. 将必须相邻的元素“捆绑”成一个整体

2. 将这个整体与其他元素一起排列

3. 最后对捆绑内部进行排列

例题：5个小朋友站成一排，其中两个双胞胎必须相邻，有几种排法？

• 将双胞胎捆绑成一个整体 [双胞胎]

• 现在有 4 个元素排列：A(4,4) = 24 种

• 双胞胎内部可以互换：2! = 2 种

• 总数 = 24 × 2 =48 种

方法3：插空法

适用场景：某些元素不能相邻（必须被分开）。

操作步骤：

1. 先排列没有“不能相邻”限制的元素

2. 在它们之间的“空隙”（包括两端）中插入受限制的元素

例题：5个人排队，A和B不能相邻。

• 先排C、D、E：3! = 6 种

• 形成 4 个空位（_ C _ D _ E _）

• 从4个空位中选2个插入A和B：A(4,2) = 12 种

• 总数 = 6 × 12 = 72 种

方法4：挡板法（隔板法）

适用场景：将n 个相同元素分成k 份（每份至少1个）。

核心思路：n 个元素排成一排，之间有 n-1 个空隙，插入 k-1 个挡板即可分成 k 份。

公式：C(n-1, k-1)

例题：10个三好学生名额分配到7个班级，每班至少1个。

• 10个名额之间有9个空隙

• 需要插入 7-1 = 6 个挡板

• 方案数 = C(9,6) = 84 种

注意：如果允许有空盒（某份可以为0），则需要额外处理，通常先“借”元素再分配。

方法5：间接法（正难则反）

适用场景：正面直接计算情况太多、太复杂。

核心思路：计算对立面（不满足条件的情况），用总数减去。

例题：略（详见后续综合例题）

七、特殊排列专题

1. 圆排列

将 n 个不同元素排成一个圆圈（不是直线）。

公式：(n-1)!

理解：圆形排列没有“起点”，旋转后相同的算一种，所以比直线排列少 n 倍。

2. 有重复元素的排列

有 k 种元素，第 i 种有 nᵢ 个（n₁ + n₂ + … + n_k = n），全排列数为：

n! / (n₁! × n₂! × … × n_k!)

例题：由数字1、1、2、4、8、8组成的不同的六位数有多少个？

• 总数 = 6! / (2! × 2!) = 720 / 4 = 180 种

八、历年真题解析

真题1（CSP-J 2020）：捆绑法

题目：五个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（ ）种不同排列方法？

• A. 24

• B. 36

• C. 72

• D. 48

解析：捆绑法。

• 双胞胎捆绑成1个整体 → 4个元素排列：4! = 24

• 双胞胎内部排序：2! = 2

• 总数 = 24 × 2 =48，选D

真题2（CSP-J 2020）：挡板法

题目：10个三好学生名额分配到7个班级，每个班级至少有一个名额，一共有（ ）种不同的分配方案。

解析：挡板法。

• 10个名额 → 9个空隙

• 分成7份 → 插6块板

• 方案数 = C(9,6) = C(9,3) =84 种

真题3（CSP-J 2021）：组合

题目：（略，考察组合基本计算）

解析：先在6人中选2人，再在剩下4人中选2人，最后除以重复（3组人的排列）：

• C(6,2) × C(4,2) / A(3,3) = 15 × 6 / 6 =15 种

真题4（手套问题）

题目：有五副不同颜色的手套（共10只），一次性从中取6只手套，请问恰好能配成两副手套的不同取法有（ ）种。

• A. 120

• B. 180

• C. 150

• D. 30

解析：

• 先选2副完整的：C(5,2) = 10 种

• 再从剩下3副（6只）中选2只，但不能是同一副：C(6,2) - 3 = 15 - 3 = 12 种

• 总数 = 10 × 12 =120，选A

九、常见题型总结

十、备考建议

1. 理解本质：排列讲究顺序，组合不讲究顺序——这是所有题目的根本。

2. 熟记公式：A(n,m) 和 C(n,m) 的公式必须烂熟于心。

3. 掌握五大方法：特殊优先法、捆绑法、插空法、挡板法、间接法。

4. 咬文嚼字：仔细读题，区分“排列”还是“组合”，“相邻”还是“不相邻”，“至少”还是“恰好”。

5. 多做真题：2024年初赛就考了一道原题，说明真题复现率不低。

6. 菜就多练：排列组合没有捷径，多练才能形成条件反射。

附录：核心公式速查表