排列组合

之前做 CSP-J 初赛试题总是不会做排列组合的题，现在就来补坑。

阶乘

n!（读作“n 的阶乘”）表示从1到n的所有整数的乘积，即：

$$n!=n\times (n-1)\times (n-2)\times \cdots \times 2\times 1$$

并且规定：

$$0!=1$$

排列公式

$$P(n,k)=\frac{n!}{(n-k)!}$$

排列****强调顺序，表示从n个不同元素中取出k个元素并考虑顺序的排列方式总数，即两个排列如果顺序不同就视为不同的情况。

例如：

$$P(5,3)=\frac{5!}{(5-3)!}=\frac{5!}{2!}=\frac{5\times 4\times 3\times 2\times 1}{2\times 1}=\frac{120}{2}=60$$

组合公式

$$C(n,k)=\frac{n!}{k!(n-k)!}$$

组合数表示从n个不同元素中取出k个元素且不考虑顺序的组合方式总数，选出的结果中不关心排列的顺序，只关注“哪些元素被选中”。

例如：

$$C(5,3)=\frac{5!}{3!(5-3)!}=\frac{5!}{3!\times 2!}=\frac{5\times 4\times 3\times 2\times 1}{(3\times 2\times 1)(2\times 1)}=\frac{120}{12}=10$$

重复元素排列公式

$$P=\frac{n!}{a_1!\times a_2!\times \cdots \times a_k!}$$

当元素中有重复时（如字母AABBC），全排列数需除以重复元素内部的排列数。

例如：排列AABBC，总方式为：

$$P=\frac{5!}{2!\times 2!\times 1!}=\frac{120}{4}=30$$

排列AABBC：5个位置中，2个A、2个B、1个C。

相邻问题（捆绑法）

当某几个元素必须相邻时，我们可以将它们看作是一个“大块”（一个整体），然后计算这些“大块”与其他元素的排列数。

$$P_{\text{相邻}}=(n-k+1)!\times k!$$

例题

5 个人 A、B、C、D、E 排队，其中 A 和 B 必须相邻，问有多少种不同的排法？

解法

1. 把 A 和 B 视为一个整体（AB），那么就相当于 4 个单元（AB、C、D、E）。
2. 对这 4 个单元进行全排列：
   $$4!=24$$
3. AB 内部也可以交换位置（AB 或 BA），即：
   $$2!=2$$
4. 总排列数：
   $$4!\times 2!=24\times 2=48$$

所以总共有 48 种 排列方式。

不相邻问题（插空法）

在排列组合问题中，如果题目要求某些元素必须 不相邻，我们可以使用插空法（Slot Method） 来解决。

当某些元素必须不相邻时，我们可以先安排其他元素，然后再把这些特殊元素插入剩余的空隙中，确保它们不会相邻。

$$\text{不相邻排列数}=m!\times C(m+1,n)\times n!$$

例题

5 个人 A、B、C、D、E 排队，其中 X 和 Y 必须不相邻，问有多少种不同的排法？

解法

1. 先安排 5 个人 A、B、C、D、E，总排列数：
   $$5!=120$$
2. 形成 6 个空位（前后+中间）：
   $$-A-B-C-D-E-$$
3. 从这 6 个空位中选 2 个放 X 和 Y：
   $$C(6,2)=\frac{6!}{2!(6-2)!}=\frac{6!}{2!4!}=\frac{6\times 5}{2}=15$$
4. X 和 Y 在选定的 2 个位置上自由排列：
   $$2!=2$$
5. 最终排列数：
   $$5!\times C(6,2)\times 2!=120\times 15\times 2=3600$$

至少/至多问题（补集法）

如果我们要求某种情况至少/至多出现多少次，可以先求 总情况数，再减去 不符合要求的情况，即：

$$符合要求的情况数=总情况数-不符合的情况数$$

补集法通常用于：

1. 至少发生 X 次的情况
2. 至多发生 X 次的情况

公式总结

对于时间 A：

• 至少发生 X 次：

$$P(至少X)=总情况数-P(少于X)$$

• 至多发生 X 次：

$$P(至多X)=P(0次)+P(1次)+\cdots +P(X次)$$

例题

从 10 个人中选 5 个人，要求至少有 2 名女生，问有多少种选法？

解法

1. 求总的选法（不考虑性别）：
   $$C(10,5)=\frac{10!}{5!(10-5)!}=252$$
2. 求不符合要求的情况（女生少于 2 人）：
   • 0 名女生（即全是男生）：
     $$C(6,5)=\frac{6!}{5!(6-5)!}=6$$
   • 1 名女生（其余全是男生）：
     $$C(4,1)\times C(6,4)=4\times 15=60$$
3. 符合要求的选法：
   $$252-(6+60)=186$$

所以至少选 2 名女生的选法有 186 种。