CSP初赛no2. 组合数学

• 重在计算原理过程，不建议死记硬背公式

1. 计数基本原理

核心公式

• 加法原理（分类计数）：完成一件事有 $n$ 类独立方法，任选一类即可完成，总方法数为各类方法数相加。
  $$N = m_1 + m_2 + \dots + m_n$$
• 乘法原理（分步计数）：完成一件事分 $n$ 个步骤，依次完成所有步骤才算完成，总方法数为各步方法数相乘。
  $$N = m_1 \times m_2 \times \dots \times m_n$$
• 解题原则：先分类，类内再分步；分类不重不漏，分步相互独立。

例题

例1 从甲地到乙地有3条公路、2条铁路，从乙地到丙地有4条公路。从甲地经乙地到丙地，共有多少种不同的走法？

解析：从甲到乙再到丙是分步完成，用乘法原理。
甲到乙共 $3+2=5$ 种走法，乙到丙有4种走法，总走法：$5 \times 4 = 20$ 种。

例2 某班有男生25人、女生20人，从中选1人担任班长，共有多少种不同选法？

解析：选男生或选女生是两类独立方案，用加法原理。
总选法：$25 + 20 = 45$ 种。

例3 从A地到C地可直达（共2条路线），也可经B地中转。已知A到B有3条路线，B到C有4条路线。从A到C共有多少种走法？

解析：分“直达”和“中转”两类，类内分步。
中转类：$3 \times 4 = 12$ 种；直达类：2种；
总计：$12 + 2 = 14$ 种。

2. 排列

核心公式

从 $n$ 个不同元素中取 $m$ 个按顺序排列，排列数记为 $A_n^m$（或 $P_n^m$）。
$$A_n^m = \frac{n!}{(n-m)!}$$
例如6个不同数中选4个做排列，第一个有6种选择，第二个为5种，第三个4种，第四个3种，即$6 * 5 * 4 * 3$，这就是排列公式的意义，求n的前m位阶乘。

• 全排列：$\(m=n\)$ 时，$A_n^n = n!$
• 圆排列：$n$ 个元素围成圆圈（旋转相同算一种），方案数 $(n-1)!$；若允许翻转，再除以2，即 $\dfrac{(n-1)!}{2}$
• 解题原则：先枚举限制多的位。

例题

例1 用数字0,2,4,6,8组成无重复数字的三位数，一共能组成多少个？

解析：百位不能为0，优先处理百位。
百位：4种选择（2,4,6,8）；
十位：剩余4个数字任选，4种；
个位：剩余3个数字任选，3种；
总数：$4 \times 4 \times 3 = 48$ 个。

例2 6名同学排成一排，其中甲不能站在排头，共有多少种排法？

解析：方法一（特殊优先）：先排排头，除甲外5人选1，剩余5人全排列。
$5 \times A_5^5 = 5 \times 120 = 600$ 种。
方法二（正难则反）：总排列 - 甲在排头的排列。
$A_6^6 - A_5^5 = 720 - 120 = 600$ 种。

例3 4名同学围圆桌就坐，座位无编号，共有多少种不同坐法？

解析：圆排列公式，$(4-1)! = \(3!\) = 6$ 种。
理解：固定1人位置作参考，剩余3人全排列，$\(3!\) = 6$。

3. 组合

核心公式

从 $n$ 个不同元素中取 $m$ 个组成一组（不考虑顺序），组合数记为 $C_n^m$。
$$C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m! \cdot (n-m)!}$$
例如7个不同数中选3个做组合，第一个有7种选择，第二个为6种，第三个5种，即$7 * 6 * 5$，但这是排列，区别在于比如1 2 3，在这个过程中会枚举到$1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1$，这都是同一个组合，被算了6次，或者说3！次，所以要再除以6，即组合公式是在排列公式的基础上再除以m！。
核心性质

1. 对称性：$C_n^m = C_n^{n-m}$
2. 全集和：$C_n^0 + C_n^1 + \dots + C_n^n = 2^n$
3. 帕斯卡恒等式：$C_n^m = C_{n-1}^m + C_{n-1}^{m-1}$

例题

例1 从10名学生中选4人参加数学竞赛，不区分分工，共有多少种选法？

解析：无序选取，用组合。
$C_{10}^4 = \frac{10!}{4! \cdot 6!} = \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} = 210$ 种。

例2 平面上有8个点，任意三点不共线，一共可以确定多少条直线？多少个三角形？

解析：两点确定一条直线，三点确定一个三角形，均为组合问题。
直线数：$C_8^2 = 28$ 条；
三角形数：$C_8^3 = 56$ 个。

例3 计算 $C_7^2 + C_7^3$，并用组合恒等式验证结果。

解析：直接计算：$C_7^2=21$，$C_7^3=35$，和为56。
由帕斯卡恒等式：$C_n^m + C_n^{m-1} = C_{\(n+1\)}^m$，
故 $C_7^2 + C_7^3 = C_8^3 = 56$，结果一致。

4. 鸽巢原理（抽屉原理）

核心结论

• 基本形式：$\(n+1\)$ 个物体放入 $n$ 个盒子，至少有一个盒子有≥2个物体。
• 加强形式：$m$ 个物体放入 $n$ 个盒子，必有一个盒子至少有 $\left\lceil \dfrac{m}{n} \right\rceil$ 个物体（向上取整）。
• 解题方法：最不利原则，考虑最坏情况，再加1即为保证成立的最小值。

例题

例1 袋子里有红、黄、蓝三种颜色的球各10个，至少取出多少个球，才能保证一定有4个球颜色相同？

解析：最坏情况：每种颜色各取3个，共 $3 \times 3 = 9$ 个，仍不满足。
再取1个，必然有一色达到4个。
答案：$9 + 1 = 10$ 个。

例2 某校有370名2012年出生的学生，其中至少有几名学生生日在同一天？

解析：2012年是闰年，共366天。
$370 \div 366 = 1 \dots 4$，向上取整为2。
至少有2名学生生日相同。

例3 一副去掉大小王的扑克牌共52张，四种花色各13张，至少抽多少张，才能保证有3张牌花色相同？

解析：最坏情况：每种花色各抽2张，共 $4 \times 2 = 8$ 张。
再抽1张必满足条件，答案：$8 + 1 = 9$ 张。

5. 隔板法（插板法）

核心公式

适用场景：相同元素分到不同组。

1. 基础型（每组至少1个）：$n$ 个相同元素分 $m$ 组，每组至少1个
   $$C_{n-1}^{m-1}$$
2. 允许空组：先给每组补1个元素，转化为基础型
   $$C_{n+m-1}^{m-1}$$
3. 不相邻选位：$n$ 个位置选 $k$ 个两两不相邻
   $$C_{n-k+1}^k$$

例题

例1 把7个相同的苹果分给3个小朋友，每人至少分1个，共有多少种分法？

解析：相同元素、每组至少1个，基础隔板法。
$C_{7-1}^{3-1} = C_6^2 = 15$ 种。

例2 方程 $x + y + z = 8$ 有多少组非负整数解？

解析：非负整数解即允许x,y,z为0，对应允许空组。
公式：$C_{8+3-1}^{3-1} = C_{10}^2 = 45$ 组。

例3 一排有10个座位，选3个座位入座，要求任意两人不相邻，共有多少种选法？

解析：不相邻选位模型。
$C_{10-3+1}^3 = C_8^3 = 56$ 种。

6. 容斥原理

核心公式

• 两集合：
  $$|A \cup B| = |A| + |B| - |A \cap B|$$
• 三集合：
  $$|A \cup B \cup C| = |A|+|B|+|C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|$$
• 正难则反：符合条件数 = 总数 - 不符合条件数

例题

例1 在1~100的自然数中，能被3或5整除的数共有多少个？

解析：设A为能被3整除的集合，B为能被5整除的集合。
$|A| = \lfloor 100/3 \rfloor = 33$，$|B| = \lfloor 100/5 \rfloor = 20$，
$|A\cap B|$ 即能被15整除：$\lfloor 100/15 \rfloor = 6$。
由容斥：$33 + 20 - 6 = 47$ 个。

例2 某班40名同学，会打篮球的有22人，会踢足球的有25人，两项都不会的有5人。(22 + 25 - 两项都会 = 35)的有多少人？

解析：至少会一项的人数：$40 - 5 = 35$ 人。
由容斥公式：$22 + 25 - \(22 + 25 - 两项都会 = 35\) = 35$，
解得(22 + 25 - 两项都会 = 35)：$47 - 35 = 12$ 人。

例3 用数字0~9组成无重复数字的三位数，其中数字3和5至少出现一个的三位数有多少个？

解析：正难则反，用总数减去不含3和5的。
总无重复三位数：$9 \times 9 \times 8 = 648$ 个；
不含3和5：百位7种（1,2,4,6,7,8,9），十位8种，个位7种，共 $7 \times 8 \times 7 = 392$ 个；
至少出现一个：$648 - 392 = 256$ 个。

7. 捆绑法与插空法

核心方法

• 捆绑法（相邻问题）：将必须相邻的元素捆成一个整体，先整体排列，再内部排列。
  总方案数 = 整体排列数 × 内部排列数
• 插空法（不相邻问题）：先排无限制的元素，再将不相邻元素插入形成的空隙中。

例题

例1 7名同学站成一排，甲乙两人必须相邻，共有多少种排法？

解析：捆绑法，将甲乙捆为一个整体，共6个元素全排列，再乘甲乙内部顺序。
$A_6^6 \times A_2^2 = 720 \times 2 = 1440$ 种。

例2 7名同学站成一排，甲乙两人不相邻，共有多少种排法？

解析：插空法，先排其余5人，形成6个空隙，插入甲乙。
$A_5^5 \times A_6^2 = 120 \times 30 = 3600$ 种。

例3 用1~7七个数字组成无重复数字的七位数，其中偶数（2,4,6）互不相邻，共有多少个？

解析：插空法，先排4个奇数，形成5个空隙，插入3个偶数。
奇数全排列：$A_4^4 = 24$ 种；
偶数插入空隙：$A_5^3 = 60$ 种；
总计：$24 \times 60 = 1440$ 个。

8. 定序问题

核心公式

$n$ 个元素全排列，其中 $m$ 个元素的相对顺序固定，总方案数：
$$\frac{n!}{\(m!\)}$$
理解：$m$ 个元素的 $\(m!\)$ 种顺序中只有1种符合要求，因此除以 $\(m!\)$ 去重。

例题

例1 6人排成一排，要求甲必须站在乙的左边（不一定相邻），共有多少种排法？

解析：甲乙两人顺序固定（甲在左）。
总排列：$6! = 720$ 种，其中甲在左、乙在左各占一半。
答案：$\dfrac{6!}{2!} = \dfrac{720}{2} = 360$ 种。

例2 5本不同的书排成一排，其中3本数学书必须按厚度从厚到薄排列，共有多少种排法？

解析：3本数学书顺序固定。
总排列：$5! = 120$ 种；
数学书内部顺序仅1种有效，除以 $\(3!\)$；
答案：$\dfrac{5!}{\(3!\)} = \dfrac{120}{6} = 20$ 种。

9. 错排问题

核心结论

$n$ 个编号元素重新排列，每个元素都不在原位，方案数为错排数 $D_n$。

• 递推公式：$D_n = (n-1)(D_{n-1} + D_{n-2})$
• 常用值：$D_1=0,\ D_2=1,\ D_3=2,\ D_4=9,\ D_5=44$

例题

例1 4名同学各写一张贺卡，集中后每人随机拿一张，要求每人都拿到别人写的贺卡，共有多少种情况？

解析：典型错排问题，$\(n=4\)$。
$D_4 = 9$ 种。

例2 5个编号的球放入5个编号的盒子，每盒一球，恰好有2个球的编号与盒子编号相同，共有多少种放法？

解析：分两步：

1. 选出2个对号的球：$C_5^2 = 10$ 种；
2. 剩余3个球全部错排：$D_3 = 2$ 种；
   总计：$10 \times 2 = 20$ 种。

10. 多重集排列

核心公式

$n$ 个元素中有 $k$ 类，每类元素数量为 $n_1,n_2,\dots,n_k$（$n_1+n_2+\dots+n_k=n$），同类元素完全相同，全排列数为：
$$\frac{n!}{n_1! \cdot n_2! \cdot \dots \cdot n_k!}$$

例题

例1 单词"book"的字母全排列，共有多少种不同的排法？

解析：字母构成为 b×1, o×2, k×1，共4个字母。
排列数：$\dfrac{4!}{1! \cdot 2! \cdot 1!} = \dfrac{24}{2} = 12$ 种。

例2 有3个相同的红球、2个相同的白球、1个黑球，排成一排，共有多少种不同排法？

解析：共6个球，三类数量分别为3,2,1。
排列数：$\dfrac{6!}{\(3!\) \cdot 2! \cdot 1!} = \dfrac{720}{12} = 60$ 种。