组合学核心知识点与解题技巧

一只emo的忘忧兽

2025-09-18 23:40:43

发布于：江西

4阅读

0回复

0点赞

组合学核心知识点与解题技巧（初一级别 / CSP 备考适用）

一、基础原理：组合学的 “底层逻辑”

（一）加法原理：“选一类就能完成，把方法数加起来”

核心定义

做一件事，有 $k$ 类不同方法（每类方法单独用就能做完这件事，且各类方法不重复），第 1 类有 $n_1$ 种方法，第 2 类有 $n_2$ 种方法…… 第 $k$ 类有 $n_k$ 种方法，总方法数就是各类方法数的和。
公式

总方法数 = $n_1 + n_2 + \dots + n_k$
例子

从家到学校有 3 种方式：坐公交有 2 路、3 路（2 种选法），骑自行车有普通自行车、山地车（2 种选法），走路只有 1 种方式。总共有多少种去学校的方法？

解：三类方法互斥，直接相加 → $2 + 2 + 1 = 5$ 种。

（二）乘法原理：“分多步才能完成，把每步方法数乘起来”

核心定义

做一件事，需要分 $k$ 步完成（少一步都做不完），第 1 步有 $n_1$ 种方法，第 2 步有 $n_2$ 种方法…… 第 $k$ 步有 $n_k$ 种方法，总方法数就是每步方法数的乘积。
公式

总方法数 = $n_1 \times n_2 \times \dots \times n_k$
例子

搭配一套衣服：上衣有 3 件（T 恤、衬衫、卫衣），裤子有 2 条（牛仔裤、运动裤）。总共能搭出多少套不同的衣服？

解：分两步（先选上衣、再选裤子），两步方法数相乘 → $3 \times 2 = 6$ 套（如 T 恤 + 牛仔裤、T 恤 + 运动裤等）。

二、经典排列模型：“有序” 的计数方法

（一）圆排列：“围圆圈排队，固定一个人再算”

核心定义 $n$ 个不同的人（或物品）围在圆圈上排列，因为圆圈没有 “起点” 和 “终点”（比如 5 人围坐，顺时针换位置后相对顺序不变），所以先固定 1 个人的位置，再算剩下的人怎么排。
公式 $n$ 个不同元素的圆排列数 = $(n-1)!$

（“!” 是 “阶乘”，如 $3! = 3 \times 2 \times 1 = 6$ ， $4! = 4 \times 3 \times 2 \times 1 = 24$ ，表示 “从这个数开始，乘比它小 1 的数，直到乘到 1”）
例子

5 个同学围圆桌吃饭，有多少种不同的坐法？

解：固定 1 个同学的位置，剩下 4 个同学全排列 → $4! = 4 \times 3 \times 2 \times 1 = 24$ 种。

（二）重复排列：“选了还能再选，每步都有 $n$ 种选法”

核心定义

从 $n$ 个不同的物品里，选 $k$ 个物品排列（选过的物品还能再选），因为每一步选的时候所有物品都在，所以每步都有 $n$ 种选法。
公式

总排列数 = $n^k$

（ $n$ 是物品总数， $k$ 是要选的个数，“ $n^k$ ” 表示 $n$ 乘 $k$ 次，如 $2^3 = 2 \times 2 \times 2 = 8$ ）
例子

用数字 0、1、2 组成 3 位数（数字可重复，如 111、202），总共能组成多少个？

解：分 3 步（百位、十位、个位）：

百位不能是 0，有 2 种选法（1、2）；
十位可以是 0、1、2，有 3 种选法；
个位和十位一样，3 种选法；

总个数 = $2 \times 3 \times 3 = 18$ 种。

（三）不相邻排列：“先排不限制的，再插要间隔的”

核心定义

要排两类物品，其中一类（如 A）不能相邻，就先把另一类（如 B）排好，再在 B 的 “空隙” 里插 A（空隙包括 B 的两端，确保 A 不相邻）。
步骤公式（分两步）

① 先排无限制的 $m$ 个物品 B：排列数 = $m!$ （ $m$ 个不同物品的全排列）；

② 算 B 的空隙数：有 $m+1$ 个空隙（如 3 个 B 排成 “B B B”，空隙是 “_ B _ B _ B _”，共 4 个）；

③ 从 $m+1$ 个空隙里选 $n$ 个插 A，排列数 = $A_{m+1}^n$ （ $A_a^b = aÃ(a-1)Ã\dotsÃ(a-b+1)$ ，表示从 $a$ 个里选 $b$ 个排队）；

④ 总排列数 = $m! Ã A_{m+1}^n$
例子

有 3 个男生和 2 个女生排队，要求女生不能相邻，有多少种排法？

解：① 先排男生： $3! = 3 \times 2 \times 1 = 6$ 种；

② 男生的空隙数： $3+1 = 4$ 个（“_ 男 _ 男 _ 男 _”）；

③ 从 4 个空隙选 2 个插女生： $A_4^2 = 4 \times 3 = 12$ 种；

④ 总排法 = $6 \times 12 = 72$ 种。

（四）错位排列：“每个人都不拿自己的东西”

核心定义 $n$ 个不同的物品（如 $n$ 封信），分给 $n$ 个对应对象（如 $n$ 个邮箱），但每个物品都不能分给自己对应的对象，这种排列叫错位排列，用 $D(n)$ 表示 $n$ 个元素的错位排列数。
公式（递推公式）

当 $n=1$ 时：只有 1 个物品，无法错位， $D(1) = 0$ ；
当 $n=2$ 时：2 个物品交换位置，只有 1 种错位， $D(2) = 1$ ；
当 $n>=3$ 时： $D(n) = (n-1) \times [D(n-1) + D(n-2)]$ （第 $n$ 个物品先和前面 $n-1$ 个中的一个交换，再分两种情况算剩下的错位数）

例子

3 个同学（甲、乙、丙）各有 1 支笔（甲的笔、乙的笔、丙的笔），把笔分给 3 人，每人都不能拿自己的笔，有多少种分法？

解：用递推公式算 → $D(3) = (3-1) \times [D(2)+D(1)] = 2 \times (1+0) = 2$ 种（实际为 “甲拿乙的、乙拿丙的、丙拿甲的” 和 “甲拿丙的、乙拿甲的、丙拿乙的”）。

三、其他高频题型：CSP 常考场景

（一）涂色问题：“抓自由变量，从约束多的位置入手”

核心思路

涂色问题常涉及 “相邻区域不同色”“网格染色”，关键是确定 “自由选择的位置” 和 “被约束的位置”，优先从约束最多的位置（如角落、边缘）开始分析。

若有 “每行 / 每列” 全局约束（如 “网格染色，每两行交点同色数为偶数”），可尝试 “首行首列确定全局”：先自由选首行和首列的颜色，剩余位置颜色由首行首列唯一确定（需验证约束）；
若仅 “相邻不同色”（如环形、线性涂色），线性从一端开始，环形先固定一个位置避免重复。

例子

用红、绿两种颜色给 2×2 网格染色（无相邻约束），共多少种？

解：每个小格有 2 种选择，4 个小格分步计算 → $2 \times 2 \times 2 \times 2 = 16$ 种。

（二）握手 / 比赛场次问题：“无序组合，选 2 个就对应一次”

核心思路 $n$ 个人互相握手、 $n$ 队单循环赛，本质是 “从 $n$ 个中选 2 个”（无序，交换两人 / 两队顺序不影响结果），直接用组合数公式。
公式

总次数 = $C(n,2) = \frac{n(n-1)}{2}$ （ $C(n,k)$ 表示从 $n$ 个里选 $k$ 个的组合数， $C(n,k) = \frac{n!}{k!(n-k)!}$ ）
例子

10 人互相握手，总次数 = $C(10,2) = \frac{10 \times 9}{2} = 45$ 次；

8 队单循环赛，总场次 = $C(8,2) = \frac{8 \times 7}{2} = 28$ 场。

（三）数字排列问题：“分类讨论，规避约束”

核心思路

常涉及 “无重复数字”“首位≠0”“奇偶性” 等约束，需结合加法原理分类（如按个位奇偶性分），再用乘法原理分步计算。
例子

用 0-5 组成无重复数字的三位偶数，共多少种？

解：按个位分 3 类（个位 = 0/2/4）：

个位为 0：首位从 1-5 选（5 种），十位从剩下 4 数选（4 种）→ $5 \times 4 = 20$ 种；
个位为 2：首位从 1,3,4,5 选（4 种），十位从剩下 4 数选（4 种）→ $4 \times 4 = 16$ 种；
个位为 4：同个位为 2，16 种；

总结果 = $20+16+16 = 52$ 种。

（四）分组分配问题：“平均分组要除序，分配任务不除序”

核心思路

若组别无区分（平均分组，如 “6 人分成 3 组，每组 2 人”）：需除以 “组数的阶乘”（消除重复分组顺序）；
若组别有区分（分配任务，如 “6 人分给 3 个不同班级，每班 2 人”）：无需除序，直接分步选。

公式与例子

平均分组（6 人分 3 组，每组 2 人）：

先分步选： $C(6,2) \times C(4,2) \times C(2,2) = 15 \times 6 \times 1 = 90$ 种；

除以组数阶乘（3 组）： $\frac{90}{A(3,3)} = \frac{90}{6} = 15$ 种（ $A(3,3)=3! = 6$ ）。
分配任务（6 人分给 3 个不同班级，每班 2 人）：

直接分步选： $C(6,2) \times C(4,2) \times C(2,2) = 90$ 种。

（五）成对问题：“先定成对，再选不成对”

核心思路

如 “手套选 k 只，恰好配 m 副”，先确定 m 副的选法，再从剩余种类中选 “不成对” 的，避免重复。
例子

5 副不同颜色的手套（共 10 只），取 6 只恰好配 2 副，有多少种选法？

解：① 选 2 副手套： $C(5,2) = 10$ 种；

② 从剩下 3 副中选 2 只不成对的（每副选 1 只）： $C(3,2) \times 2 \times 2 = 3 \times 2 \times 2 = 12$ 种（选 2 副，每副 2 种选择）；

总结果 = $10 \times 12 = 120$ 种。