第九章 排列组合

排列组合常用公式速查表

符号约定：

• $n,m\in\mathbb N$，且 $0\le m\le n$。
• 阶乘：$n!$，约定 $0!=1$。
• 线性排列 $A_n^m=\dfrac{n!}{(n-m)!}$，组合 $C_n^m=\dfrac{n!}{m!(n-m)!}$。

1. 相异元素（不重复）

2. 允许重复取用

3. 含重复元素的全排列

4. 错位排列（全不在原位）

5. 常用恒等式与技巧

• 对称性：$\displaystyle C_n^m=C_n^{\,n-m}$
• Pascal 恒等式：$\displaystyle C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$
• 乘法原理：分步选择且互不干扰，用“乘”。
• 加法原理：情形互斥，用“加”。
• 先选后排：很多有序问题可拆成“组合 × 排列”。

6. 快速选型（决策小抄）

1. 是否有顺序？

   • 有 → 看是否可重复：可 → $n^m$；不可 → $A_n^m$。
   • 无 → 看是否可重复：可 → $C_{n+m-1}^m$；不可 → $C_n^m$。

2. 圆上排？

   • 给定 $m$ 个相异元素：$(m-1)!$。
   • 从 $n$ 中选 $m$ 再圆排：$\dfrac{n!}{(n-m)!\,m}$。
   • 若镜像同一（手环/项链）：再除以 $2$（$m>2$）。

3. 有相同元素？ → $\dfrac{n!}{\prod n_i!}$。

4. 要求“无人在原位”？ → 用 $D_n$。

一、加乘原则

1. 分类相加

完成一件事情，需要划分几个类别，各类别中的方法可以独立完成这件事情。当分类没有重复、没有遗漏时，完成这件事情的方法总数等于每一类方法数之和。

示例：小明计划明早从南京去一趟杭州，可以选择高铁、大巴、飞机三种方式。由于时间问题，小明必须在9:00~10:00内出发，而这个时间段内高铁、大巴、飞机分别有4、3、2趟航班。高铁、大巴、飞机，三种出行方式不管选择哪种，都可以独立完成"从南京去杭州"这件事情，所以是分类相加，小明的出行共有 $4 + 3 + 2 = 9$ 种方案。

2. 分步相乘

完成一件事情，需要分为几个步骤，各步骤不重叠、不遗漏、正好完成这件事时，完成这件事情的方法总数等于各步骤的完成方法数之积。

示例：小明明早去杭州之后，下午还要去一趟苏州，现在已知去杭州有9种出行方案，从杭州去苏州有6种出行方案。而南京 $\rightarrow$ 杭州、杭州 $\rightarrow$ 苏州都是"南京 $\rightarrow$ 杭州 $\rightarrow$ 苏州"这件事的两个不重叠、不遗漏的步骤，分步相乘，所以南京 $\rightarrow$ 杭州 $\rightarrow$ 苏州共有 $9 \times 6 = 54$ 种出行方案。

① 确定好各组挑选名额
② 从"库"中按名额挑选给各组

3. $A_m^n$ 是什么

$A_m^n$：从"库"中 $m$ 个对象里依次挑选1个对象 $n$ 次的总方案数。由于每次挑选都是不重叠的步骤，所以分步相乘：

$A_m^n = m \times (m - 1) \times (m - 2) \times \cdots \times (m - n + 1)$

例1 3个人排成一列，有多少种排法？

此问题中，一列3个位置，3个人，可以把3个位置看作3个单位，分别名额为1，需要依次从3个对象的库里挑1个对象挑3次，所以一共有 $A_3^3 = 3 \times 2 \times 1 = 6$ 种方式。

例2【模版题】 6个人中挑3个人排成一列，有多少种排法？

此问题中，一列3个位置，6个人，可以把3个位置看作3个单位，分别名额为1，需要依次从6个对象的库里挑1个对象挑3次，所以共有 $A_6^3 = 6 \times 5 \times 4 = 120$ 种方式。

4. 捆绑排序

例3【模版题】 甲乙丙丁戊5个人排成一列，其中甲乙是发小，两个人必须排在相邻位置，有多少种排法？

由于甲乙必须排在一起，我们选择把甲乙看作一个整体，此时问题变为(甲乙)丙丁戊4个人排成一列，则有 $A_4^4 = 4 \times 3 \times 2 \times 1 = 24$ 种方式。但要注意到，甲乙虽然看作一个整体，但是整体内部依然存在"顺序"，在(甲乙)的组内，甲和乙谁在前谁在后是还没有解决的事情，所以还需要再多加一步，甲乙2人排成1列问题 $A_2^2 = 2 \times 1 = 2$ 种情况。最后分步相乘，一共有 $A_4^4 \times A_2^2 = 24 \times 2 = 48$ 种情况。

5. 消除多余顺序

例4 还是上面排队问题条件，如果今天老师突然允许甲乙两个人并排排队，他俩直接并排手拉手了，那么这5人在前后位置上的排法（不考虑甲乙的左右顺序）有多少种？

此时甲乙还是看作1个整体，实际为4个对象排到4个位置中，共有 $A_4^4 = 4 \times 3 \times 2 \times 1 = 24$ 种方式。

对比上面两种情况可以发现

总结：

• 如果一件事情，额外多加了一个要求，出现了新的"顺序"，那么就需要对总方法数多乘一个"顺序" $A_n^n$。
• 如果一件事情，多考虑了一个要求，多算了一个"顺序"，那么实际结果就需要把多出来的这个"顺序" $A_n^n$ 除掉。

6. $C_m^n$ 是什么

$C_m^n$：从"库"中 $m$ 个对象里挑选 $n$ 个对象给某组。

$C_m^n = \frac{A_m^n}{A_n^n} = \frac{m \times (m - 1) \times (m - 2) \times \cdots \times (m - n + 1)}{n \times (n - 1) \times \cdots \times 2 \times 1}$

例5【模版题】 小明、小红、小王、小李四位同学应聘某知名企业，企业只计划招录2位同学，有多少种招录可能？

此问题中，"库"中有4位同学需要挑选2位给企业，所以有 $C_4^2 = \frac{4 \times 3}{2 \times 1} = 6$ 种可能。

7. 稍微复杂一点的题目

例6【模版题】 小明、小红、小王、小李4位毕业生去甲、乙、丙3个单位报道，每个单位至少1位毕业生，有多少种报道方式？

解析 在这个问题中，我们可以把甲、乙、丙3个单位看作3个组，小明、小红、小王、小李4位毕业生是一个库，从毕业生库中挑选毕业生给各个组。

首先要先确定好各个组的挑选名额，4个名额分给3个单位只能是 $2 + 1 + 1$，第一步确定好名额，从3个单位里找1个单位领取2个名额，$C_3^1$ 种情况，可能甲是那个2也可能乙是那个2也可能丙是那个2。然后不管谁是2，开始按照名额分配对象，先给名额为2的组分配 $C_4^2$ 种情况，再给剩下一个单位分配1个 $C_2^1$，最后一个对象自动归最后一组。所以共有 $C_3^1 \times C_4^2 \times C_2^1 = 3 \times 6 \times 2 = 36$ 种报道方式。

上面这个过程中，分配人员分为四步：

1. 确定各组名额
2. 给2人组挑人
3. 给其中一个1人组挑人
4. 给最后一个1人组挑人

注意点：

1. 确定好名额后，挑人顺序不影响结果，任意顺序皆可。比如刚刚的问题里，如果分配好名额后先给1人组挑人，$C_3^1 \times C_4^1 \times C_3^1 = 3 \times 4 \times 3 = 36$，结果不变。
2. 最后一组不需要纳入计算过程，最后一组没有其他选择，只有拿剩下的一种可能。

不妨考虑每个单位至少有一人，四人分到三单位的唯一可能的“人数分布”是 $(2,1,1)$：

1. 先选哪一个单位分到 2 人：有 $\displaystyle3$ 种。
2. 从 4 位同学里选 2 人去这个“双人”单位：$\displaystyle\binom{4}{2}=6$ 种。
3. 剩下 2 人分别去另外两个单位，一一对应，共有 $2!\;=\;2$ 种方式。

因此总数

故共有 36 种报道方式。

8. 再复杂一点

例7【模版题】 小明、小红、小王、小李、小胡5位毕业生去甲、乙、丙3个单位报道，每个单位至少1位毕业生，有多少种报道方式？

解析 在这个问题中，首先我们还是先确定各个组的挑选名额，5个名额分给3个组可以是 $3 + 1 + 1$，也可以是 $2 + 2 + 1$，要先确定好名额我们才好继续接下来的挑人动作，所以此处进行一次分类。

分类一： 如果是 $3 + 1 + 1$，第一步确定好名额为3的组，$C_3^1$ 种情况，然后开始按照名额分配对象，$C_5^3 \times C_2^1$ 种情况，所以 $3 + 1 + 1$ 的分类下，共有 $C_3^1 \times C_5^3 \times C_2^1 = 3 \times 10 \times 2 = 60$ 种情况。

分类二： 如果是 $2 + 2 + 1$，第一步确定好名额为1的组，$C_3^1$ 种情况，然后开始按照名额分配对象，$C_5^2 \times C_3^2$ 种情况，所以 $2 + 2 + 1$ 的分类下，共有 $C_3^1 \times C_5^2 \times C_3^2 = 3 \times 10 \times 3 = 90$ 种情况。

根据分类相加原则，一共有 $60 + 90 = 150$ 种报道方式。

按照三人分布在三个单位的情况，先把总人数 $5$ 分成三份（每份 $\ge1$）共有两种模式：

1. 模式一：$(3,1,1)$

   • 选哪个单位接收 3 人：3 种。
   • 从 5 人中选 3 人去这个单位：$\binom{5}{3}=10$ 种。
   • 剩下 2 人分配到剩余两个单位（每人一人），有 $2!$=2 种。 → 本模式：$3\times10\times2=60$ 种。

2. 模式二：$(2,2,1)$

   • 选哪个单位接收 1 人：3 种。
   • 从 5 人中选 1 人去这个单位：$\binom{5}{1}=5$ 种。
   • 剩下 4 人中，选 2 人去其中一个“2 人”单位：$\binom{4}{2}=6$ 种，余下 2 人去最后一个单位。 → 本模式：$3\times5\times6=90$ 种。

合计 $60+90=150$ 种报道方式。

使用容斥原理，对“每人可去甲/乙/丙3个单位”，但要保证三个单位都至少有人，计算如下：

1. 总分配数（不作限制）：

   $$3^5 = 243.$$

2. **剔除“至少有 1 个单位无人”**的情况。设

   • $A$ = “甲无人”，
   • $B$ = “乙无人”，
   • $C$ = “丙无人”。

   则

   $$|A|=|B|=|C|=2^5=32,$$

   因为当某单位无人，剩下两单位任意分配。

3. **加回“至少有 2 个单位无人”**的过度剔除部分：

   $$|A\cap B| = |A\cap C| = |B\cap C| = 1^5 = 1,$$

   因为当两单位都无人，所有人都只能分到最后一个单位。

4. **“3 个单位都无人”**不可能（留给人的单位数为 0），故交三集的计数为 0。

5. 应用容斥：

   $$\begin{aligned} N &=3^5 -\bigl(|A|+|B|+|C|\bigr) +\bigl(|A\cap B|+|A\cap C|+|B\cap C|\bigr) -0\\ &=243 - 3\times32 + 3\times1\\ &=243 - 96 + 3\\ &=150. \end{aligned}$$

因此，一共有 150 种报道方式。

9. 正面排列组合问题

例8【模版题】 厨师要从6种主料中选取2种，8种辅料中选取3种烹制一道菜肴，问最多可以烹制多少种不同的菜肴？

• A. 288
• B. 360
• C. 420
• D. 840

解析 烹制一道菜肴需要分为两步：① 选取主料 ② 选取辅料，分别有 $C_6^2$ 和 $C_8^3$ 种可能，分步相乘，一共最多可以烹制 $C_6^2 \times C_8^3 = 15 \times 56 = 840$ 种菜肴，选择D。

例【较难】 某企业最近招聘了5名新员工，女员工比男员工多一名，现随机分配到三个部门学习，每个部门至少分配一名员工，而且最多不能超过两名员工，同一个部门分配到的员工性别不能相同。请问共有（）种分配结果。

• A.18
• B.20
• C.25
• D.36

解析 根据题目要求，3 个部门名额分配只能是 $2 + 2 + 1$ ，而且同部门员工性别不同，所以名额为 2 的部门必须是 1 男 1 女。现有 3 女 2 男，分配步骤可以如下：

$①$ 确定部门名额分配， $C_{3}^{1}$ 。依次挑人，第一个2部门先挑1男1女， $C_{2}^{1}\times C_{3}^{1}$ ，第二个2部门再挑1男1女， $C_{1}^{1}\times C_{2}^{1}$ ，最后一个部门预最后的人。共有 $C_{3}^{1}\times C_{2}^{1}\times C_{3}^{1}\times C_{1}^{1}\times C_{2}^{1} = 3\times 2\times 3\times 2 = 36$ 种分配结果。 $(2)$ 确定部门名额分配， $C_{3}^{1}$ 。由于每个部门各1个女的，两个2部门各1个男的，可以看作步骤一：3个女员工分配给3个部门 $A_{3}^{3}$ ；步骤二：2个男员工分配给2个部门 $A_{2}^{2}$ 。共有 $C_{2}^{1}\times A_{2}^{3}\times A_{2}^{2}$ $= 3\times 6\times 2 = 36$ 种分配结果。

首先确定性别人数：共 5 人，女比男多一，故女 3 人（记作 $F_1,F_2,F_3$），男 2 人（记作 $M_1,M_2$）。

每个部门人数限制为 1 至 2 人，且两人同组时须一男一女。要把 5 人分给 3 个部门，只有容量配置 $(2,2,1)$ 能凑满：

1. 选出哪一个部门只分到 1 人：3 种。

2. 这个“单人”部门必须是一位女员工（因为两个双人组各需 1 男 1 女，用尽全部 2 男、2 女 中的 2 女，剩下一女作为单人）：

   • 从 3 名女中选 1 人：$\binom{3}{1}=3$ 种。

3. 剩下的两部门各分到一男一女：

   • 先把 2 名男分配到这 2 个部门：$2!=2$ 种；
   • 再把剩下的 2 名女分配到这 2 个部门：$2!=2$ 种；
   • 合计 $2\times2=4$ 种。

将以上相乘，总数

答：共有 36 种分配结果。

例 某交警大队的 16 名民警中，男性为 10 人，现要选 4 人进行夜间巡逻工作，要求男性民警不得少于 2 名，问有多少种选人方法？

• A.1605
• B.1520
• C.1071
• D.930

解析首先确定可以挑几个男性民警，不少于2名，则可能是2名、3名、4名。分类讨论

2名男性 $+2$ 名女性： $C_{10}^{2}\times C_{6}^{2}$

3名男性 $+1$ 名女性： $C_{10}^{3}\times C_{6}^{1}$

4名男性： $C_{10}^{4}$

分类相加，所以一共有 $C_{10}^{2}\times C_{6}^{2} + C_{10}^{3}\times C_{6}^{1} + C_{10}^{4} = 45\times 15 + 120\times 6 + 210 = 1605$ 种选人方法，选择 $A$

10. 组合公式

$C_m^n = C_m^{m-n}$

公式含义： 从m个不同元素中选择n个元素的组合数，等于从m个元素中选择(m-n)个元素的组合数。

例题： 从8个人中选择3个人参加活动，有多少种选法？

解法一： 直接计算选3个人的组合数 $C_8^3 = \frac{8!}{3!(8-3)!} = \frac{8!}{3!5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$

解法二： 利用组合公式，转换为选5个人不参加的组合数 $C_8^3 = C_8^{8-3} = C_8^5 = \frac{8!}{5!(8-5)!} = \frac{8!}{5!3!} = 56$

应用技巧： 当n > m/2时，可以转换为计算C_m^{m-n}，能够简化计算过程。例如计算C_{100}^{98}时，可以转换为C_{100}^2 = 4950，避免了复杂的大数计算。

11. 趣味思路：空白人

例【模版题】 甲乙丙丁戊5人负责周一至周三安保，要求每天至少一人不超过两人，每人只参加一天，问共有多少种安排？

• A. 60种
• B. 90种
• C. 120种
• D. 180种

解析一（常规解析）： 5人分3天，每天1-2人，则名额为1+2+2，先定名额确定哪一天是1，$C_3^1$ 种情况，然后分人，$C_5^1 \times C_4^2$，所以一共有 $C_3^1 \times C_5^1 \times C_4^2 = 3 \times 5 \times 6 = 90$ 种安排，选择B。

解析二（空白人思路）： 假设存在一位"借来"的员工，每天分组2人，分完组"借来"的员工即可离开，所以一共有 $C_6^2 \times C_4^2 = 15 \times 6 = 90$ 种安排，选择B。

推导：

• 由于每天至少 1 人且不超过 2 人，3 天共要分配 5 人，唯一可能的日人数分布是 $(1,2,2)$。

• 先从“周一/周二/周三”中选一个做 1 人日：3 种；

• 再从 5 人里选 1 人去这个“1 人日”：$\binom{5}{1}=5$ 种；

• 剩下 4 人，分配到另外两个“2 人日”——先从中选 2 人去其中某天：$\binom{4}{2}=6$ 种，剩下 2 人自动到最后一天。

• 总计：

  $$3 \times 5 \times 6 = 90.$$

例10 扶贫攻坚期间，某单位将5户不同贫困程度的贫困户分给3位帮扶干部，要求每名干部最多分到2户，其中老王主动要求结对帮扶最困难的一户，则剩余4户共有多少种不同的分配方案？

• A. 18种
• B. 24种
• C. 30种
• D. 36种

解析 假设存在一位空白人，则问题转变为6人平均分3位干部，每人2位。老王除了确定的最困难的1户，还需要再挑选一位 $C_5^1$，剩下两位干部还有 $C_4^2$ 种挑人方式，所以一共有 $C_5^1 \times C_4^2 = 5 \times 6 = 30$ 种方案，所以选择C。

设最困难的那户已经给了老王，剩下 4 户需要分给 A（老王）、B、C 三位，每人最多 2 户，且 A 此时还可再分 0 或 1 户。

记 $k_A,k_B,k_C$ 分别为剩余分配给 A、B、C 的户数，则

• 情况1： $k_A=0$，则 $k_B+k_C=4$，仅有 $(k_B,k_C)=(2,2)$。 分配数：$\binom{4}{0}\binom{4}{2}=6$。

• 情况2： $k_A=1$，则 $k_B+k_C=3$，且 $k_B,k_C\le2$，可选 $(1,2)$ 或 $(2,1)$。

  • $(k_B,k_C)=(1,2)$：$\binom{4}{1}\binom{3}{1}=4\times3=12$。
  • $(k_B,k_C)=(2,1)$：$\binom{4}{1}\binom{3}{2}=4\times3=12$。

合计方案数

答：共有 30 种不同的分配方案。

二、反面排列组合问题

例11【模版题】 某高校开设A类选修课四门、B类选修课三门。小刘从中共选取四门课程，若要求两类课程各至少选一门，则选法有：

• A. 18种
• B. 22种
• C. 26种
• D. 34种

此问题中，需要先确定两类课程分别选取几门，可能3门A + 1门B，可能2门A + 2门B，也可能1门A + 3门B，正面分类情况较多，于是我们可以考虑反面排列组合。

满足题意情况数 = 不管某条件情况数 - 不满足此条件情况数

在上面的问题中，如果不管条件"两类课程各至少选一门"，只是选取四门课程，问题就很简单，$C_7^4$ 即可。但 $C_7^4$ 中必然存在不满足条件"两类课程各至少选一门"的情况数，需要减掉。不满足"两类课程各至少选一门"条件是没有选A类或者没有选B类。

分类一： 没有选A类，需要在B类3门课中选取4门课，不存在这样的情况，0种。
分类二： 没有选B类，需要在A类4门课中选取4门课，有 $C_4^4 = 1$ 种情况。

所以满足题意情况数 $= C_7^4 - 1 = C_7^3 - 1 = 35 - 1 = 34$ 种情况，所以选择D。

从 A 类 4 门、B 类 3 门中任选 4 门，且至少各选 1 门。

• 总方式：$\displaystyle\binom{7}{4}=35$
• 全选 A 类（B 类 0 门）：$\displaystyle\binom{4}{4}=1$
• 全选 B 类（A 类 0 门）：$\displaystyle\binom{3}{4}=0$

因此有效选法

或者分情况计算：

1. 选 1 门 A、3 门 B：$\binom{4}{1}\binom{3}{3}=4$
2. 选 2 门 A、2 门 B：$\binom{4}{2}\binom{3}{2}=6\times3=18$
3. 选 3 门 A、1 门 B：$\binom{4}{3}\binom{3}{1}=4\times3=12$

汇总：$4+18+12=34$。

答：共有 34 种选法。

例 单位3个科室分别有7名、9名和6名职工。现抽调2名来自不同科室的职工参加调研活动，问有多少种不同的挑选方式？

• A.146
• B.159
• C.179
• D.286

解析 正面思路，2名来自不同科室的职工可能是 $7 + 9$ $7 + 6$ $9 + 6$ 三种情况，分类相加。共有 $C_{7}^{1}\times C_{9}^{1}$ $+C_{7}^{1}\times C_{6}^{1} + C_{9}^{1}\times C_{6}^{1} = 63 + 42 + 54 = 159$ 种不同的挑选方式。所以选择 $B$ 0

解析 反面思路，如果不管条件“2名职工来自不同科室”，则有 $C_{22}^{2}$ 种方式，如果不满足条件“2名职工来自不同科室”，来自相同科室，则有 $C_{7}^{2} + C_{9}^{2} + C_{6}^{2}$ 种方式，所以满足题意的方式共有 $C_{22}^{2} - C_{7}^{2} - C_{9}^{2} - C_{6}^{2}$ $= 231 - 21 - 36 - 15 = 159$ 种不同的挑选方式。所以选择 $B$ 0

正面排列组合与反面相比，并没有完全的优劣关系，结合题目考虑哪种方向更适合短时间解出即可，排列组合更重要的是越快出完整步骤的思路最好。

三、反面容斥排列组合问题

例【较难】 某公司推出4款杯子，分别为陶瓷杯、玻璃杯、木质杯和不锈钢杯，现将4个杯子放进展柜排成一排展示，要求玻璃杯不能放在两端，木质杯和不锈钢杯不能相邻，那么可能会出现多少种排列方式？

• A. 8
• B. 12
• C. 16
• D. 20

解析 一排4个位置由左至右标记为1、2、3、4。玻璃杯不能在两端1或者4，中间2和3挑选1个给玻璃杯有 $C_2^1$ 种情况。玻璃杯去2，木质杯和不锈钢杯就去1、3或者1、4的位置上2种情况，再考虑木质杯和不锈钢杯的左右顺序，$A_2^2$ 种情况，最后陶瓷杯去最后空着的位置即可。所以一共有 $C_2^1 \times 2 \times A_2^2 = 8$ 种情况，所以选择A。

1. 反面原理

满足题意情况数 = 不管某条件情况数 - 不满足此条件情况数

解析 条件1"玻璃杯不能放在两端"比较容易确定情况，可以考虑进条件1、不考虑条件2再减反面。玻璃杯不在两端的情况下，共有 $C_2^1 A_3^3$ 种情况，此时不满足条件2"木质杯和不锈钢杯不能相邻"的情况是木质杯和不锈钢杯相邻，共有 $C_2^1 A_2^2$ 种情况（捆绑后，当玻璃杯确定了中间的一个位置后，$1 + 1 + 2$ 的位置关系，捆绑整体的位置也自然确定了，只需要考虑其内部顺序即可，最后一个杯子自动入最后一个位置），所以共有 $C_2^1 A_3^3 - C_2^1 A_2^2 = 12 - 4 = 8$ 种，选择A。

2. 容斥原理

满足题意情况数 = 不管条件1条件2情况数 - 不满足条件1情况数 - 不满足条件2情况数 + 不满足条件1且不满足条件2情况数

容斥原理：$A \cap B = A + B - A \cup B$

解析 题干存在两个条件"玻璃杯不能放在两端"、"木质杯和不锈钢杯不能相邻"，各自条件的反面比较直接，考虑反面容斥做法。满足题意情况数 $= A_4^4 - C_2^1 A_3^3 - A_3^3 A_2^2 + C_2^1 A_2^2 A_2^2 = 24 - 12 - 12 + 8 = 8$ 种，所以选择A。

我们先把“玻璃杯”固定在中间的两个位置，再排布其余三款杯子并排除“木质杯”与“不锈钢杯”相邻的情况：

1. 玻璃杯放第 2 位 剩余位置为第 1、3、4 位，需排入陶瓷（C）、木质（W）、不锈钢（S）。

   • 总排列数：3! = 6 种
   • “W”与“S”同时占第 3、4 位的情况有 2 种，需要剔除
   • 有效排列：6 − 2 = 4 种

2. 玻璃杯放第 3 位 剩余位置为第 1、2、4 位，同样排入 C、W、S。

   • 总排列数：3! = 6 种
   • “W”与“S”同时占第 1、2 位的情况有 2 种，需要剔除
   • 有效排列：6 − 2 = 4 种

将两种情况相加，共有 4 + 4 = 8 种合法的展示排列方式。

例13 某企业从10名高级管理人员中选出3人参加国际会议。在10名高级管理人员中，有一线生产经验的有6人，有研发经验的有5人，另有2人既无一线生产经验也无研发经验。如果要求选出的人中，具备一线生产经验的人和具备研发经验的人都必须有，问有多少种不同的选择方式？

• A. 96
• B. 100
• C. 106
• D. 112

解析 $6 + 5 - (10 - 2) = 3$，所以有3人既有生产经验也有研发经验，有3人只有生产经验，有2人只有研发经验，2人什么也没有。

满足题意情况数 = 总情况 - 没有生产经验 - 没有研发经验 + 既没有生产经验也没有研发经验

$\Sigma = C_{10}^3 - C_4^3 - C_5^3 + C_2^3 = 120 - 4 - 10 + 0 = 106$

所以选择C。

例【较难】 某三甲医院派甲乙丙丁四名医生到ABCD四个社区义诊，每个医生只负责一个社区。已知甲不去A社区，且如果丙去C社区，那么丁去D社区，则不同的派法共有：

• A.15种
• B.18种
• C.21种
• D.24种

解析 总情况 $= A_4^4 = 24$ 。条件一反面为甲去A社区，情况数为 $A_3^3 = 6$ 。条件二反面为丙去C，丁不去D，情况数为 $C_2^1\times A_2^2 = 4$ 。条件一反面且条件二反面为甲去A丙去C丁不去D，只有甲A乙D丙C丁B这1种情况，所以派法一共有 $24 - 6 - 4 + 1 = 15$ 种，选择A选项。

我们把所有可能的 1∶1 派法 $4!=24$ 按照“丙”是否去 C 分两种情况讨论：

1. 情况一：丙→C

由条件“若丙去 C 则丁→D”，故丁→D。剩余甲、乙 分配给 A、B，但甲≠A，只能甲→B、乙→A，共 1 种。

2. 情况二：丙≠C

此时“若丙→C”前件为假，丁 无额外限制。只需满足甲≠A 且 丙≠C。 所有无约束的排列有 $4!=24$ 种， 减去甲→A 的 6 种， 减去丙→C 的 6 种， 再加回重复减去的（甲→A 且 丙→C）2 种， 得到 $24-6-6+2=14$ 种。

两种情况合计：

因此，共有 15 种不同的派法。

注意点

排列组合容斥思想中，直接去除条件反面时，不用考虑另一个条件成立与否。

四、环形排列问题

环形排列公式：

n个不同对象的环形排列数 = $(n-1)! = A_{n-1} ^ {n-1}$

原理解释：

• 环形排列相当于固定一个对象的位置，然后对其余$(n-1)$个对象进行线性排列
• 因为圆桌没有固定的起点，所以n个对象的环形排列等于$(n-1)$个对象的线性排列

例【模版题】 5名公司职员坐在圆桌上吃饭，问共有多少种不同的坐法？

• A.24
• B.48
• C.60
• D.120

解析 圆桌位置关系属于环形问题，5个人，所以坐法 $= A_4^4 = 24$ 种，所以选择A。

例【模版题】 有8个小朋友需要一起吃午饭，一共有两张桌子，一张圆桌可以坐5个人，一张方桌可以坐3个人，请问坐在圆桌上的小朋友共有多少种坐法？

• A.1200
• B.1344
• C.3344
• D.6720

解析首先选取坐圆桌的5个人 $C_8^5$ ，再环形排列 $A_4^4$ ，所以一共有 $C_8^5\times A_4^4 = C_8^3\times A_4^4 = 56\times 24 = 1344$ 种，所以选择 $B_{\circ}$

例【较难】 有5对夫妇参加一场婚宴，他们被安排在一张10个座位的圆桌就餐，问5对夫妇恰好都被安排在一起相邻而坐的情况有多少种

• A.384种
• B.768种
• C.3840种
• D.7680种

解析5对夫妇相邻而坐，捆绑为3个整体环形排列 $A_4^4$ 种坐法，每个整体内部还有 $A_2^2$ 种排序，所以一共有 $A_4^4\times 2^5 = 24\times 32 = 768$ 种情况，所以选择 $B_{\circ}$

将每对夫妻视为一个“二人组合”单元，则问题简化为在圆桌上排列 5 个组合单元，并且每个单元内部夫妻两人又可交换座次。

1. 组合单元在圆桌上的排列 在圆桌上排列 $n$ 个可区分对象，等价于线性排列后除以旋转对称，总数为 $(n-1)!$。 这里 $n=5$，故共有 $(5-1)! = 4! = 24$ 种。

2. 每对夫妻内部的座次 每个组合单元（夫妻）内部可交换坐左或坐右，共有 $2$ 种可能。 5 对夫妻独立决定，共有 $2^5 = 32$ 种。

3. 总数

   $$24 \times 32 = 768.$$

所以，恰好 5 对夫妇都相邻而坐的座次共有 768 种。

五、插空法

1. 不相邻问题

例【模版题】 6人放学排成1列，其中小明、小王吵架了不愿意排在一起，有多少种排法？

解析 按照“隔板法”思路，分三步计算：

1. 先排除小明和小王 将剩下的 4 个人先排成一列，有

   $$4! = 24$$

   种方式。

2. 确定小明、小王的位置间隔 在这 4 个人之间（包括两端）共有 5 个“空位”：

   $$\_ \;A\;\_ \;B\;\_ \;C\;\_ \;D\;\_$$

   要让小明和小王不相邻，就需要分别放在这 5 个空位中选出的 2 个不同位置，共有

   $$\binom{5}{2} = 10$$

   种选法。

3. 在选定的两空位上安排小明/小王的先后顺序 小明和小王互换位置还算不同，共有

   $$2! = 2$$

   种。

总计

因此，共有 480 种排法。

我们令全排列总数为 $6!$。记事件 $A_j$ 为“小明与小王占据第 $j$ 和第 $j+1$ 号相邻座位”（无论先后），则 $j=1,2,3,4,5$。

1. 计算 $|A_j|$ 固定他们在位置 $j$、$j+1$，二人内部可互换：2 种；其余 4 人自由排列：$4!$ 种。

   $$|A_j| = 2 \times 4! = 48.$$

2. 两两交集 $|A_i\cap A_j|$ 若 $i\neq j$，则“同一对二人”不可能同时占两组不同的相邻位置，因此

   $$|A_i\cap A_j| = 0,\quad i\neq j.$$

3. 容斥求并集 $\biggl|\bigcup_{j=1}^5 A_j\biggr|$

   $$\Bigl|\bigcup A_j\Bigr| = \sum_{j=1}^5|A_j| \;-\!\!\sum_{i<j}|A_i\cap A_j| +\cdots = 5\times48 - 0 + \cdots = 240.$$

   这即是“小明与小王相邻” 的排列数。

4. 求“不相邻”情形

   $$\underbrace{6!}_{720} \;-\;240 \;=\;480.$$

例 在一张节目单中原有6个节目，若保持这些节目的相对顺序不变，再添加进去3个小品，这3个小品为了避免审美疲劳不能相邻，则所有不同的添加方法共有多少种？

解析原来6个节目有7个空位，3个小品选择3个空位插入，共有 $A_7^3 = 7\times 6\times 5 = 210$ 种情况。

2. 插班法公式

1. 将 a 个可区分物品插入 b 个可区分物品中且互不相邻

首先，我们假设：

• 这两类物品均可区分（即每个物品都是独一无二的），
• 原本的 b 个物品先排成一行（它们的内在顺序也要计入总数），
• 然后将 a 个物品插入其中，且要求插入的这 a 个物品两两之间不相邻。

推导步骤

1. 先排列 b 个物品 将原有的 b 个物品在一条线上任意排列，共有

   $$A_b^b$$

   种可能。

2. 确定插入“缝隙” 排好 b 个物品后，就形成了 $b+1$ 个“缝隙”（包括最左端和最右端各一个）。 这 $b+1$ 个位置中，我们要选出 a 个来插入新物品，以保证它们互不相邻， 可选的方法数为

   $$C_{b+1}^a$$

3. 安排 a 个物品的内部顺序 选定了插入位置后，还要决定这 a 个物品在所选缝隙中的排列顺序，共有

   $$A_a^a$$

   种。

公式汇总

将上述三步的自由度相乘，即可得到总的排列数：

• 若你只关心在固定的 b 个物品序列中插入 a 个可区分物品（即不再计入 b!），则结果简化为

  $$C_{b+1}^a \times A_a^a$$

• 注意当 $a>b+1$ 时，无论如何插入都必然会有相邻，故结果为 0。

举例

• 令 $a=2$、$b=3$。

  • 先排 3 个物品：$3!=6$ 种；
  • 缝隙数 $=3+1=4$，选 2 个：$C_{4}^{2}=6$ 种；
  • 插入物品内部排列：$2!=2$ 种。
  • 总数 $=6\times6\times2=72$ 种。

这样，我们就得到了“将 a 个可区分物品插入 b 个可区分物品中且互不相邻”的排列总数公式：

例【模版题】 某学习平台的学习内容由观看视频、阅读文章、收藏分享、论坛交流、考试答题五个部分组成。某学员要先后学完这五个部分，若观看视频和阅读文章不能连续进行，该学员学习顺序的选择有：

• A.24种
• B.72种
• C.96种
• D.120种

解析

1. 容斥法

   • 全部排列：$5!\!=120$
   • 将“观看视频（V）”与“阅读文章（A）”看作一个整体，则类似“VA”一起排列，其内部可交换顺序有 $2!\!=2$，整体加上另外 3 个模块，共 $4!\!=24$ 种排列，乘以内部顺序得 $24\times2=48$。
   • 不相邻的排列数＝总排列 − 相邻排列＝$120-48=72$。

2. 插空法

   • 先排列除 V、A 外的 3 个模块（收藏分享、论坛交流、考试答题）：$3!\!=6$ 种。
   • 排好后在 4 个“缝隙”（首、末及中间两处）中选 2 个位置放 V 和 A，保证不相邻：$\binom{4}{2}=6$ 种位置选择；
   • V、A 在所选位置上可交换顺序：$2!\!=2$。
   • 总数＝$6\times6\times2=72$。

3. 公式法

   $$\text{不相邻排列数} =5! - 2\times4! =120 - 48 =72$$

3. 插空不相邻的另一种思维

例 6人放学排成1列，其中小明小王吵了架不愿意排在一起，有多少种排法？

下面分别用容斥法和插板法来计算“小明”和“小王”不相邻的排法数。

一、容斥法

1. 总排列数 6 个人随意排：

   $$6! = 720$$

2. “小明”“小王”相邻的排列数

   • 将他们看作一个整体，则共有 $5$ 个“对象”排列：

     $$5! = 120$$

   • 整体内部可以互换顺序：

     $$2! = 2$$

   • 故相邻情况共有：

     $$5! \times 2! = 120 \times 2 = 240$$

3. 不相邻数

   $$6! \;-\;(5!\times2!) \;=\;720-240 \;=\;480$$

二、插板法（插空法）

1. 先排除小明、小王之外的 4 人：

   $$4! = 24$$

2. 确定“缝隙”数 排列好的 4 人之间及两端共有 $4+1=5$ 个缝隙。

3. 在这 5 个缝隙中选 2 个放小明、小王，保证他们不相邻：

   $$\binom{5}{2} = 10$$

4. 小明、小王在所选缝隙内的顺序：

   $$2! = 2$$

5. 合并

   $$4! \times \binom{5}{2} \times 2! = 24 \times 10 \times 2 = 480$$

结论：两种方法都得出 480 种不相邻排列。

4. 快速解决相隔至少n个元素的排列组合问题

例【模版题】 如果是10个人排成1列，其中小明小王吵了架不愿意排在一起，且小明小王中间起码要隔3个对象，有多少种排法？

方法一·捆绑法

我们把小明、小王及中间的 $k$ 人（$3\le k\le8$）捆成一个“大组”，再考虑这个大组与剩下的人如何排列。

1. 选中间的 $k$ 人并排列

   • 从其他 8 人中选 $k$ 人：$\displaystyle \binom{8}{k}$
   • 这 $k$ 人内部排列：$k!$

2. 组内小明/小王两端互换

   • 小明、小王可各居一端：2 种

3. 整体单位排列

   • 大组视作 1 个单位，剩余 $8-k$ 人各作 1 单位，共 $1+(8-k)=9-k$ 个单位，排列方法：$(9-k)!$

4. 对 $k=3$ 到 $8$ 求和

方法二·确定位置法

1. 选定“小明”和“小王”的位置 记位置编号为 1…10，要求两者之间至少隔 3 个人，即位置编号之差 ≥ 4。

   • 不考虑顺序的不同编号对共有

     $$\sum_{d=4}^{9}(10 - d)\;=\;6 + 5 + 4 + 3 + 2 + 1\;=\;21$$

     种（表示两人位置相差 d），

   • 考虑“小明”“小王”可互换（有序）则乘 2，得到

     $$21 \times 2 = 42$$

   种有序位置分配。

2. 排列其余 8 个人 剩下的 8 人在剩余 8 个位置上任意排列，共 $8! = 40320$ 种。

总数

所以，满足条件的排列共有 1,693,440 种。

两种方法思路不同，结果一致：1 693 440 种。

5. m个对象中a个对象至少需要隔n个对象

m个不同对象中a个对象至少需要隔n个对象，则这a个对象的顺序有 $A_{m-(a-1) \times n}^a$ 种排法。

注： $(a-1) \times n$ 就是一共需要用来"隔"的元素至少个数

推导 问题的抽象

• 有 $m$ 个互不相同的对象。
• 其中有 $a$（$a\le m$）个“特殊”对象必须两两之间至少隔 $n$ 个其它对象（即在这两个特殊对象之间至少有 $n$ 个非‑特殊对象）。
• 其余 $m-a$ 个对象同样互不相同。

我们要计数在全部 $m$ 个对象的排列中，满足上述“间距”条件的排列数。
（如果只关心这 $a$ 个特殊对象的相对顺序，则只取其中的因子即可，见下文最后的简化式。）

1. 先选位置，再排对象

设把全部 $m$ 个位置编号为 $1,2,\dots ,m$。
记特殊对象占据的位置为

并且必须满足

（因为两对象之间要有至少 $n$ 个“其它”对象，即两位置之间的距离要至少为 $n+1$）。

1.1 位置的等价变换

定义

则

所以 $\{j_{k}\}$ 只是一组 普通的递增整数集合，从 1 到

中任选 $a$ 个即可。

因此，满足间距要求的 位置集合 的数目为

1.2 把对象放到这些位置上

• 这 $a$ 个特殊对象互不相同，可在已选好的 $a$ 个位置上随意排列，方式数为 $a!$。
• 剩下的 $m-a$ 个普通对象也互不相同，它们在其余 $m-a$ 个空位上的排列方式为 $(m-a)!$。

把三部分乘在一起得到 全部排列 的总数：

2. 只关注这 $a$ 个对象的相对顺序

如果题目只问“这 $a$ 个对象的顺序有多少种排法”，即不计入其余 $m-a$ 个对象的排列，则只保留与这 $a$ 个对象相关的因素：

• $\binom{\,m-n(a-1)\,}{a}$ 计的是在满足间距要求的 位置 的选取方式。
• $a!$ 计的是把这 $a$ 个 不同 对象安排到已选位置的顺序。

3. 公式的有效范围

• 必须满足 $m-n(a-1)\ge a$，即

  $$m\ge a + n(a-1)$$

  否则根本放不下这么多对象（间距条件无法实现），答案为 0。

• 当 $n=0$（即没有间距限制）时，式 (2) 简化为 $a!\binom{m}{a}$，正好是先从 $m$ 个位置中任选 $a$ 个，再在这 $a$ 个位置上排 $a$ 个对象的普通计数。

4. 小结

• 全部 $m$ 个对象的合法排列数

  $$\boxed{\displaystyle \binom{\,m-n(a-1)\,}{a}\; a!\; (m-a)!} \qquad\bigl(m\ge a+n(a-1)\bigr)$$

• 仅看这 $a$ 个特殊对象的相对顺序

  $$\boxed{\displaystyle a!\,\binom{\,m-n(a-1)\,}{a}} \qquad\bigl(m\ge a+n(a-1)\bigr)$$

例【较难】 甲到飞机场坐飞机，飞机场的十二个登机口排成一条直线，相邻两个登机口之间相距50米。甲在登机口等待时被告知登机口更改了，那么甲走到新登机口的距离不超过200米的概率是：

解析 原登机口与新登机口距离不超过200米，即两个登机口间隔不超过3个其他登机口。转化为反面，讨论两个登机口间隔至少4个其他登机口情况数，有 $A_{12-4}^2 = A_8^2$ 种情况，而两个登机口总可能数有 $A_{12}^2$ 种情况，所以反面概率 $= \frac{A_8^2}{A_{12}^2} = \frac{8 \times 7}{12 \times 11} = \frac{14}{33}$，所以题干条件正面概率 $= 1 - \frac{14}{33} = \frac{19}{33}$，所以选择D。

• 登机口数量：12个，排成一条直线，编号可设为1到12。
• 相邻登机口距离：50米，因此任意两个登机口（编号为$m$和$n$，$m\neq n$）之间的距离为$50\times|m - n|$米。

1. 确定总情况数
   甲初始在任意一个登机口，更改后可到其余11个登机口，总共有$12\times11 = 132$种等可能的情况。

2. 确定满足条件的情况数
   要求距离不超过200米，即$50\times|m - n|\leq200$，化简得$|m - n|\leq4$（即两个登机口的编号差不超过4）。
   对每个初始登机口$m$，满足条件的新登机口$n$的数量如下：

   • 当$m = 1$或$m = 12$时，满足条件的$n$有4个（如$m=1$时，$n=2,3,4,5$）。
   • 当$m = 2$或$m = 11$时，满足条件的$n$有5个（如$m=2$时，$n=1,3,4,5,6$）。
   • 当$m = 3$、$m = 10$时，满足条件的$n$有6个。
   • 当$m = 4$、$m = 9$时，满足条件的$n$有7个。
   • 当$m = 5$至$m = 8$时，满足条件的$n$有8个。

   总计满足条件的情况数为：$2\times4 + 2\times5 + 2\times6 + 2\times7 + 4\times8 = 8 + 10 + 12 + 14 + 32 = 76$。

3. 计算概率
   概率 = 满足条件的情况数÷总情况数 = $\frac{76}{132} = \frac{19}{33}$。

例【较难】 办公室 8 名员工围着一张圆桌就座准备用餐, 此时又有 3 名加完班的员工在已就座的员工中间加座并参加用餐。已知加座后, 3 名加完班的员工彼此都不相邻, 且 8 名已就座的员工最多与 1 名加完班的员工相邻。问有多少种不同的加座方式?

• A.336
• B.96
• C.48
• D.30

解析 8名已就座的员工最多与1名加完班的员工相邻，即3名加完班的员工排列后中间起码隔着2位已就座的员工。此问题同时还是环形排列问题，所以比较复杂，需要先"定位"。假设3个加完班的员工为甲乙丙，任意找1位定位，$C_8^1$ 确定甲的位置，然后成为线形排列问题，8个已就座员工一条线，需要插入2个空，前后间隔都起码为2。相当于10个人排列，乙丙前中后都需要起码2个人，所以乙丙共有 $A_{10-3 \times 2}^2 = A_4^2$ 种分组方式，所以一共有 $C_8^1 \times A_4^2 = 8 \times 12 = 96$ 种不同的加座方式。

1. 选座位置（“缝隙”） 已有 8 名员工围坐成环，他们之间共有 8 个“缝隙”可供插入新座位。记环上缝隙编号为 1…8。要求不在同一原员工两侧都插座，即不能选取两个相邻缝隙（环上相邻）。

   • 将环“断开”成一条长链（线性）后，线性上选 3 个互不相邻位置的方法有

     $$\binom{8-3+1}{3} \;=\;\binom{6}{3}=20.$$

   • 再从中剔除“同时选中两端”（原 1 号缝隙和 8 号缝隙）的情况：若两端都选，则还要在线段中剩下的 4 个位置里选 1 个，数目为 $\binom{4}{1}=4$。

   • 因此环上可选缝隙数为

     $$20 - 4 \;=\;16.$$

2. 安排 3 名不同加班员工 3 名加班员工是不同个体，挑定了 3 个缝隙后，还要在这 3 个位置上进行全排列，共 $3!=6$ 种。

综上，总的加座方式数目为

6. 在 $n$ 个位置中选 $k$ 个且不相邻” 的组合数

推导

下面给出“在 $n$ 个位置中选 $k$ 个且不相邻”的经典组合数公式及其推导。

1. 公式

2. 组合型推导

2.1 等价模型：插“空隙”

• 先在 $n$ 个位置中选出 $k$ 个“用于放球”的位置，记这些选中的位置相对有序。

• 为保证任意两选中位置不相邻，我们可以在每两个选中位置之间至少插入一个“空位”。

  1. 先放 $k$ 个“球”，这 $k$ 个球之间需要 $(k-1)$ 个空位。

  2. 除去这 $(k-1)$ 个空位后，剩余可自由分配的“空位”有

     $$n - k - (k - 1) \;=\; n - 2k + 1.$$

• 这些剩余空位可以被看作“可插入任意两个球之间，或两端”的“自由空格”。一共要将这 $n - 2k + 1$ 个空格，分配到“$k+1$” 个缝隙（球的左边、球与球之间、球的右边）。

• 按“stars and bars”（球棍法）可知，将 $n - 2k + 1$ 个同质空格分成 $k+1$ 份的方案数为

  $$\binom{(n - 2k + 1) + (k+1) - 1}{(k+1) - 1} \;=\; \binom{n - k + 1}{k}.$$

  其中

  • “总物品数”为 $(n-2k+1)$，
  • “分隔棒数”为 $(k+1)-1=k$。

3. 另一种直观理解

将所选的 $k$ 个位置想象成一串“1”，剩下的 $n-k$ 个空位置想象成“0”。要求“1”两两之间至少隔一个“0”，即模式中不出现“11”。

1. 先把每个“1”和它之后的那个强制的“0”绑定成“块”——记为“10”，一共 $k$ 块，占据 $2k$ 个位置。

2. 剩下的散“0”有 $n - 2k$ 个，可以插入到这 $k$ 块以及两端，共 $k+1$ 个插槽中，且可为空。

3. 将 $n - 2k$ 个“0”自由分配到这 $k+1$ 个插槽，依旧是“球棍法”：

   $$\binom{(n - 2k) + (k+1) - 1}{(k+1)-1} \;=\; \binom{n - k + 1}{k}.$$

4. 小结

无论哪种等价建模，都得出

即为在 $n$ 个位置中选取 $k$ 个且任意两选中位置都不相邻的组合数公式。

例【模版题】 某车库有 10 个并排的车位, 有 3 辆不同的车要停进这 10 个车位之中, 而且彼此不能相邻, 则有多少种不同的停放方法?

• A.336
• B.246
• C.156
• D.66

解析

停车位非相邻选法分两步：

1. 选车位 先不考虑车的不同，将 3 个“占位”插入 10 个车位，要求任何两个都不相邻。等价于在 10−3+1=8 个“间隔”里选 3 个，数目为：

   $$\binom{8}{3} \;=\;56.$$

2. 安排车辆 3 辆车互不相同，选好 3 个车位后，还要对这 3 个车位进行排列，共有 $3!=6$ 种。

因此总方式数为

例【模版题】 小区内空着一排相邻的 8 个车位, 现有 4 辆车随机停进车位, 恰好没有连续空位的停车方式共有多少种?

• A.48
• B.120
• C.360
• D.1440

解析 4个空位不相邻，4辆车存在5个空，所以情况数 $= C_5^4$（空位插入车辆的5个空）$\times A_4^4$（4辆车的排序）$= 5 \times 24 = 120$，所以选择B选项。

6. 同素分堆问题

使用的公式

把 $n$ 个同质名额分给 $k$ 个路口：

• 每个至少 1 个（正整数解）：

  $$x_1+\cdots+x_k=n,\;x_i\ge 1 \quad\Longrightarrow\quad \binom{n-1}{k-1}.$$

• 允许为 0（非负整数解）：

  $$y_1+\cdots+y_k=m,\;y_i\ge 0 \quad\Longrightarrow\quad \binom{m+k-1}{k-1}.$$

公式的直观推导（“插板法 / 星与杠”）

以“☆”代表名额、以“|”代表隔板。

• 非负情形 $y_1+\cdots+y_k=m$：把 $m$ 颗“☆”排成一行，需要放入 $k-1$ 块“|”把它们切成 $k$ 段（段长就是各 $y_i$）。

• 允许某段为空 ⇒ “|”可以相邻或放在两端。

• 可选位置总数：$m$ 颗“☆”与 $k-1$ 块“|”一共 $m+k-1$ 个位置，从中挑 $k-1$ 个摆“|”：

  $$\#=\binom{m+k-1}{k-1}.$$

• 正整数情形 $x_i\ge1$：先给每段预放 1 颗“☆”，剩下 $n-k$ 颗自由分配，化到上式：

  $$\#=\binom{(n-k)+k-1}{k-1}=\binom{n-1}{k-1}.$$

另一种推导（隔板位置法）

把 $n$ 颗“☆”排成一串，共有 $n-1$ 个缝隙可插隔板。

• 若 $x_i\ge1$，就不能把隔板插在串的两端，也不能插出空段；于是只需在这 $n-1$ 个缝里选 $k-1$ 个放隔板：

  $$\#=\binom{n-1}{k-1}.$$

• 若允许为 0，则把“虚拟的缝”扩展到两端与相邻插板，等价于上面的 $\binom{m+k-1}{k-1}$。

例【模版题】 某城市一条道路上有4个十字路口,每个十字路口至少有一名交通协管员,现将8个协管员名额分配到这4个路口,则每个路口协管员名额的分配方案有:

• A.35种
• B.70种
• C.96种
• D.114种

解析 8个名额就像8个相同的小球，7个空位，分成4组，需要插3块隔板，所以会有 $C_7^3 = 35$ 种方案，所以选择A。

我们要把 8 个相同的协管员名额分给 4 个不同的路口，且每个路口至少 1 人。设各路口人数为 $x_1,x_2,x_3,x_4$，则