排列组合初赛详解

排列组合初赛详解

首先，我们有两个必备的公式：

第一个

排列公式：
$$A_n^m=\frac{n!}{(n-m)!}$$

或者

$$P_n^m=\frac{n!}{(n-m)!}$$

第二个

组合公式：
$$C_n^m=\frac{A_n^m}{A_m^m}=\frac{n!}{m!(n-m)!}$$

运用

1.插板法

例题：现有 $ n $ 完全相同的元素，要求将其分为 $ k $ 组，保证每组至少有一个元素，一共有多少种分法？

分析：可以将问题转化为 $n$ 个元素，用 $ k - 1 $ 块板子将他们分为 $k$ 个部分，即为将 $k-1$ 个板插入 $n-1$ 个空
即为：
$$A_{n-1}^{k-1}$$

变式：现有 $ n $ 完全相同的元素，要求将其分为 $ k $ 组，一共有多少种分法？

分析：这一次一组可以有0个元素，所以我们可以给每一个组别都先放一个，所以这下就变成了：

$ n + k $ 完全相同的元素，要求将其分为 $ k $ 组，每组至少有一个元素，一共有多少种分法？

即为：
$$A_{n+k-1}^{k-1}$$

2.捆绑法

例题：
五个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（ ）种不同排列方法？

分析：先把双胞胎看成一个整体，最后再乘2,表示他俩内部可以排个先后。

总结：
遇到形如：有 $n$ 个人，其中 $m$ 个人要在一起的问题，可以将$m$个人看作一个整体，则 $ans=(n-m+1)!\times m!$

错排问题

把错位排列问题具体化，考虑这样一个问题：

n 封不同的信，编号分别是 1,2,3,4,5，现在要把这五封信放在编号 1,2,3,4,5 的信封中，要求信封的编号与信的编号不一样。问有多少种不同的放置方法？

假设考虑到第 $n$ 个信封，考虑两种情况进行递推：
1.前 $n-1$ 封都装错
2.前 $n-1$ 封信中有一封装对，其余都装错
第一种情况，既然前面都装错了，所以只需将第 $n$ 封信与前 $n-1$ 封信依次交换，便可得到所有情况。
即：
$$D_{n_1}=(n-1)(D_{n-1})$$
第二种情况，因为有一封信是正确的所以，只需将正确的和第 $n$ 封信交换即可，则答案为：
$$D_{n_2}=(n-1)(D_{n-2})$$
则可以得出递推式：
$D_n=(n-1)(D_{n-1}+D_{n-2})$
还有另一个：
$n{D}_{n-1}+(-1{)}^n$