排列组合

排列与组合

排列组合其实是分开的两个词，排列：A，组合：C。
排列组合即 AC。

先来看最基本的排列：\(1\sim n\) 的全排列，这个有多少种呢？\(n!\) 种。

然后看到最基本的组合：从 \(n\) 个数中选择一个数，方案数当然是 \(n\) 种了。

\(A_{n}^{m}\) 表示在 \(n\) 个不同元素中选择 \(m\) 个进行排列的方案数，计算方法：

\[A_{n}^{m}=\frac{n!}{(n-m)!} \]

可以这么理解：\(n!\) 就是所有数全部拎出来排，但是我们只需要 \(m\) 个，剩下的 \(n-m\) 个数的排列是多余的。

\(C_{n}^{k}\) 表示在 \(n\) 个元素中选出 \(m\) 个的方案数，计算方法：

\[c_{n}^{m}=\frac{A_{n}^{m}}{m!} \]

可以这么理解：\(A_{n}^{m}\) 已经选好了这 \(m\) 个数，但是我们不需要这 \(m\) 个数的 \(m!\) 种排列，所以去掉。

加法原理

不同的类型的方案数应该相加。

如：一条路，往前走有 \(A\) 种走法，往后走有 \(B\) 种走法，那么一共有 \(A+B\) 种走法。

乘法原理

不同步骤的方案数应该相乘。

如：一条路，走第一步有 \(A\) 种选择，走完第一步之后又有 \(B\) 种选择，则一共有 \(A\times B\) 种选择。

容斥原理

\[A\cup B\cup C=A+B+C-A\cap B-A\cap C-B\cap C+A\cap B\cap C \]

别样的排列与组合

圆排列

若从 \(n\) 个数中选择 \(m\) 个数排成一个圆，排列方案？

首先我们不考虑圆，则方案数为 \(A_{n}^{m}\)。

在圆排列中，排列 \([1,2,3]\)，\([2,3,1]\) 和 \([3,1,2]\) 都是同一个排列。

一个长度为 \(m\) 的排列以任意一个数作为首位在线性排列种是不同的，但在圆排列中却是相同的。

所以圆排列数：\(\frac{A_{n}^{m}}{m}\)

重复元素的排列

求一个序列 \([1,2,2,3,4,4,4,5]\) 的不同全排列数量。

考虑普通的全排列，即为 \(8!=40320\) 种。

但是序列中有重复的元素，如 2，前后两个 2 交换位置时应该是同一种方案，所以答案算多了。

\[\frac{40320}{2!}=20160 \]

然后是 4，在一个排列中，4 有 \(3!=6\) 种方案交换位置。

\[\frac{20160}{3!}=3360 \]

所以，长度为 \(n\) 的序列 \(a\) 含有重复元素的不同全排列数量为:

\[\frac{n!}{\prod_{i\in a}cnt_i!} \]

不相邻组合

注意！是组合！
一个序列的选出 \(m\) 个数，但是要求：若 \(a_x\) 被选出，则 \(a_{x-1}\) 和 \(a_{x+1}\) 不能被选出。

这样考虑：
选出了 \(m\) 个数，所以还有 \(n-m\) 个数没有被选出。若要选出的数不相邻，则要求选出的数在未选出的 \(n-m\) 个数之间插空。

\(n-m\) 个数有 \(n-m+1\) 个空！

方案数即为 \(C_{n-m+1}^{m}\)

球放盒子

保证你读完之后认不到“球”和“盒”这两个字。

\(n\) 球，\(m\) 盒。

球相同，盒子不同，盒子不能为空

问题等价于“将若干元素分成 \(m\)，每组必须有值。”

考虑使用插板法（插 \(x\) 个板子分成 \(x+1\) 组）

问题又等价于：\(n\) 个球中间共有 \(n-1\) 个空隙，在这 \(n-1\) 个空隙插入 \(m-1\) 个板子（选择 \(m-1\) 个空隙插板子），方案数 \(C_{n-1}^{m-1}\)

球相同，盒子不同，盒子可以为空

由于球是相同的，可以给每个盒子先放一个球（一共放 \(n+m\) 个球），然后就转化成了上一个问题。

方案数 \(C_{n+m-1}^{m-1}\)

球相同，盒子相同，盒子不能为空

定义状态：\(P_{n,m}\) 表示 \(n\) 球 \(m\) 盒的方案数。
考虑转换问题：总共有 \(n\) 个球，要求分成若干份，数量最多的那份有 \(m\) 个球，球数量递减（非严格）。求方案数。
比如：
球球球球
球球
球
这时候我们将上面的竖着看：
球|球|球|球
球|球|空|空
球|空|空|空
分成两种情况：

1. 最大值有两个及以上
   此时我们可以直接删掉最大值份中的所有球，对满足“数量最多的那份有 \(m\) 个球”这个条件没有影响。\(P_{i,j}+=P_{i-j,j}\)。
2. 最大值只有一个
   此时第二个值一定满足 \(\le MAX-1\)，所以将最大值减一不影响单调性。\(P_{i,j}+=P_{i-1,j-1}\)。

球相同，盒子相同，盒子可以为空

\(P_{n+m,m}\)。

球不同，盒子相同，盒子不能为空。

用 \(S_{n,m}\) 表示当前问题答案。
若要加入一个球，有两种选择：

1. 新开一个盒子，有：S[i][j]+=S[i-1][j-1]。
2. 选一个盒子放，有：S[i][j]+=S[i-1][j]*j。、

卡特兰数

用于解决的问题：多边形划分成三角形，从 \((0,0)\) 走到 \((n,n)\) 且不穿过对角线……
推法：
由于画图需要耗费太多的时间了，所以：link
最终公式：\(H_n=\frac{1}{n+1}C_{2n}^n\)