排列组合

加法原理、乘法原理

做一件事，有 n 类办法，在第 1 类办法中有 $m_1$ 种不同的方法，在第 2 类办法中有 $m_2$ 种不同的方法，…，
在第 n 类办法中有 $m_n$ 种不同的方法，那么完成这件事共有:

$N=m_1+m_2+…+m_n$

分步计数原理：完成一件事，需要分成 n 个步骤，做第 1 步有 $m_1$ 种不同的方法，做第 2 步有 $m_2$ 种不同的方法，…，
做第 n 步有 $m_n$ 种不同的方法,那么完成这件事共有

$N=m_1×m_2×\cdots ×m_n$

区别：

  • 分类计数原理是加法原理，不同的类加起来就是我要得到的总数
  • 分步计数原理是乘法原理，是同一事件分成若干步骤，每个步骤的方法数相乘才是总数

排列问题

从 n 个不同元素种取出 $m(m\leq n)$ 个元素的所有不同排列的个数，叫做从 n 个不同元素种取出 m 个元素的排列数，用符号 $\mathrm{P}_n^m$ 表示
$\mathrm{P}_n^m=n(n-1)(n-2)\cdots(n-m+1)=\frac{n!}{(n-m)!},\quad n,m\in \mathbb{N}^* ,\text{并且}m\leq n$

排列数性质

$A_n^m = n * A_{n-1}^{m-1}$
可理解为“某特定位置”先安排，再安排其余位置

$A_n^m = m * A_{n-1}^{m-1} + A_{n-1}^m$
可理解为：含特定元素的排列有 $m * A_{n-1}^{m-1}$, 不含特定元素的排列为 $A_{n-1}^m$

组合问题

从 n 个不同元素中取出 $m(m\leq n)$ ，个元素的所有不同组合的个数，叫做从 n 个不同元素种取出 m 个元素的组合数，用符号$\mathrm{C}_n^m$

组合公式
$$\mathrm{C}_n^m=\frac{\mathrm{A}_n^m}{\mathrm{A}_m^m}=\frac{n(n-1)(n-2)\cdots (n-m+1)}{m!}=\frac{n!}{m!(n-m)!},\quad n,m\in \mathbb{N}^* ,\text{并且}m\leq nz$$

组合数的性质
$\mathrm{C}_n^m = \mathrm{C}_n^{n-m}$
以理解为：将原本的每个组合都反转，把原来没选的选上，原来选了的去掉，这样就变成从 n 个元素种取出 n − m 个元素 ，显然方案数是相等的

递推公式
$C_n^m=C_{n-1}^m+\mathrm{C}_{n-1}^{m-1}$
可理解为：

  • 含特定元素的组合有 $\mathrm{C}_{n-1}^{m-1}$
  • 不含特定元素的排列为 $\mathrm{C}_{n-1}^m$

求解应用的一些基本方法

1.特殊元素优先安排

  • 在解决排列组合问题时，如果有一些元素需要满足特定条件或有特殊限制，你会先考虑这些元素的安排，然后再考虑剩余元素的安排

在处理有优先条件的问题时，你通常按照以下步骤操作

  1. 处理特殊元素：根据特殊元素的具体条件，计算它们可能的排列方式。例如，如果需要两个特定元素必须相邻，那么你可以将它们视为一个单一元素进行处理
  2. 安排剩余元素：一旦特殊元素的位置确定了，剩下的元素就没有特殊条件了，你可以像处理普通的排列组合问题一样来安排它们

这种方法非常适用于包含了特定条件或限制的问题，如

  • 密码生成（某些字符必须出现或不能出现在特定位置）
  • 座位安排（某些人必须坐在一起或不能坐在一起）
  • 竞赛安排（一些队伍必须首先比赛），等等
  • 通过将问题分解成处理特殊元素和处理一般元素两个部分，可以更容易地计算出最终的排列组合数目

2.排列、组合混合的问题先选后排

这是解决一类更复杂的排列组合问题的一个策略。这种问题通常涉及两个步骤

  1. 先选（组合）：首先从一组元素中选择一定数量的元素，这个过程是组合，因为在这一步骤中我们不关心选出的元素的顺序。
  2. 后排（排列）：在选择了元素之后，接下来的问题是如何安排这些元素的顺序。这一步骤涉及到排列，因为我们现在关心的是元素的顺序

通过这种方法，我们可以先计算所有可能的组合数（选择元素），然后针对每一种组合计算排列数（安排元素顺序）。这种先选后排的策略常用于解决那些同时包含组合和排列规则的问题

例子：

1
2
3

如果有一个问题是从10本不同的书中选择4本来排列在书架上，   
我们可以先计算从10本书中选择4本的组合数（组合），   
然后计算这4本书的排列数（排列）。最终的答案就是这两个数的乘积

3.相邻问题的捆绑法

这种方法是用来解决某些元素必须相邻的排列问题。步骤如下：

  1. 捆绑：将需要相邻的元素视为一个单一的元素。
  2. 排列：计算所有元素（包括捆绑后的元素）的排列数量。
  3. 乘以内部排列：将上述结果乘以被捆绑元素内部的排列数量。

例子1
假设我们有A, B, C三个字母，需要A和B必须相邻。
我们可以将AB视为一个单一的元素X，并计算X, C两个元素的排列数，即2!（X可以是AB或BA）。
然后，因为A和B可以内部互换，我们需要将结果乘以2!。所以，总的排列数是2! * 2! = 4。

4.不相邻问题的插空法

这种方法用于解决某些元素不能相邻的排列问题。步骤如下：

  1. 排列不受限制的元素：首先排列那些没有相邻限制的元素。
  2. 插空：在已排列的元素之间（包括头尾）找出可插入受限制元素的空隙。
  3. 排列受限制的元素：计算有多少种方法可以在这些空隙中插入受限制的元素。

例子2
假设我们有A, B, C, D四个字母，但A不能与B相邻。
首先排列C和D（因为它们不受限制），有2!种排列。然后在CD的头、尾和中间找空隙插入A，有3个空隙。
最后，在剩下的空隙中插入B，如果我们已经将A放入了一个空隙，那么还剩下2个空隙可以选择。
所以，最终的排列数是2! * 3 * 2 = 12。

5.分排问题的直排处理

在分排问题中，我们要将一组对象分成几个不同的小组，并在每个小组内进行排列。直排处理的步骤包括：

  1. 分组：根据条件将总数分成几个部分。
  2. 排列：对每个小组进行排列计算。

例子1
有10个运动员，需要分成3个接力队伍，每队3人，剩下的1人作为替补。
每个队伍的排列方法数为3!。所以，总排列方法数为(3!)^3 * 1，因为替补不需要排列。

6.至多至少问题的间接法

这种方法用于解决至多或至少问题，即至多有多少个或至少有多少个对象满足某条件的问题。解决这类问题的方法是：

  1. 计算全部：首先计算没有任何条件限制的总数。
  2. 减去不满足条件的数量：然后从总数中减去不满足至多或至少条件的数量。

例子2
假设有5个球，至少要选择3个球。那么我们先计算选择任意数量球的总方法数，即2^5（因为每个球有被选中或不被选中两种可能）。
然后，我们减去选择0个、1个和2个球的方法数，即2^5 - (C_5^0 + C_5^1 + C_5^2)。

7.数量不大问题的穷举法

当问题中的数量不是很大时，我们可以使用穷举法，即尝试所有可能的情况来找到解决方案。

例子3
如果有4本不同的书，要看有多少种不同的排列方式，因为数量不大，我们可以简单地列出所有的排列来计算，总数为4!。

8.分组问题

在分组问题中，我们要将一组对象分成几个小组，但每个小组内不需要进一步排列。

例子4
假设有 6 人要分成3组，每组 2 人。我们可以用组合公式计算。首先选 2 人分成一组，
有 $C_6^2$ 种方法；然后在剩下的4人中选2人，有 $C_4^2$ 种方法；最后剩下 2 人自然组成最后一组。
总的分组方法数为 $C_6^2 * C_4^2 / 2$!，除以 2! 是因为分组是没有顺序的。

参考