517编程普及组数学之排列组合
517编程普及组数学之排列组合
wsq127写在最前
排列组合是数学中重要的概念，用于描述对象的排列和组合方式。在许多领域，如概率论、组合数学、计算机科学等，排列组合都有广泛的应用。
阶乘
对于非负整数的阶乘是所有小于等于该数的正整数的积，在数学中我们用 $!$ 表示阶乘。也就是说 $n!=1\times2\times3\times…\times n$，例如 $4!=1\times2\times3\times4=24$。特别的，我们定义 $0!=1$。
阶乘也可以写成递归式：
$$
!x=\begin{cases}
1 & x=1\
!(x-1)\cdot x & x>1
\end{cases}
$$
在组合数学中，$n$ 个不同的元素中按照一定的顺序选择 $n$ 个元素的所有可能的方式的总数，也就是说 $n$ 的全排列，它是等于 $n!$ 的。例如，如果有$3$ 个不同的元素，那么排列的总数就是 $3!=6$。
排列
概念
排列是指从一组对象中按照一定的顺序选择若干个对象的方式。
假设有 $n$ 个对象，从中选取 $m$ 个对象进行排列，那么总共就有 $A_n^m$ 种排列方法。
计算
我们发现，如果说 $n$ 个数中取 $m$ 个数，并且考虑顺序的情况下，第 $1$ 个位置应该有 $n$ 种选择，第 $2$ 个位置由于有一个数在第一个位置被选了，那么就只剩下了 $n-1$ 个数，以此类推，直到第 $m$ 个位置剩下 $n-m+1$ 种选择。
而总共的方案数根据乘法原理就能得出是每一个位置可以选择的数量相乘。
总结成算是就是就是：$A_n^m=n\cdot(n-1)\cdot(n-2)\cdot\dots\cdot(n-m+1)$
然而，肯定有人跳出来挑刺了，这个算式实在是钛长了，我也这么认为，那么让我们化简一下。
我们发现 $n\cdot(n-1)\cdot(n-2)\cdot\dots\cdot(n-m+1)$ 这一坨东西和 $n!$ 差了 $(n-m)\cdot(n-m-1)\cdot\dots1$，不难发现这一坨就是 $n-m$ 的阶乘，那么我们便可以化简得到：$A_n^m=n\cdot(n-1)\cdot(n-2)\cdot\dots\cdot(n-m+1)=\frac{n!}{(n-m)!}$。
这下就身心愉悦了。
组合
概念
组合和排列的唯一区别就是排列的组合是不区分顺序的，也就是说在组合中我们把 $[1,4,5]$ 和 $[5,1,4]$ 先辈の集合视为同一种方案。
假设有 $n$ 个对象，从中选取 $m$ 个对象进行组合，那么总共就有 $C_n^m$(也记作 $(_n^m)$) 种排列方法。
计算
不难发现在每一种选择都有 $m!$ 种顺序，而组合也就可以用排列的结果去除 $!m$，所以 $C_n^m=\frac{n!}{m!(n-m)!}$最快的一集。
隔板法
$n$ 个相同的小球放到 $m$ 个不同的盒子，有一种方案？
遇到上面这种问题时，我们就可以使用隔板法来解决。
这个问题会分两种情况：
不能为空
假设是 $9$ 个小球，$4$ 个盒子。
我们先“画”出 $9$ 个小球：
O O O O O O O O O
懒得画图然后呢要分到 $4$ 个盒子里，我们可以理解为划分成四个部分，那么就需要分割三次，也就是插三个隔板。
而图中总共有 $8$ 个空隙，要插 $3$ 个隔板，发现答案是 $C_8^3$。
O|O|O|O|O|O|O|O|O
1 2 3 4 5 6 7 8
接下来返回到 $n$ 个小球，$m$ 个盒子，不难得出答案就是 $C_{n-1}^{m-1}$。
可以为空
仍然假设 $9$ 个小球，$4$ 个盒子。
和上一种不一样的是，这一种相当于一个空隙里可以放 $2$ 个甚至更多。
不过细心想一想，我们发现隔板的总数加上小球的总数是不变的，为 $n+m-1$，而这里面有 $m-1$ 个是隔板，那么答案就是 $C_{n+m-1}^{m-1}$。
直接理解的话貌似不太好理解，我们不妨将他转换为上一个情况。
如果说我们先借来 $m$ 个球，然后按照上面这种方法每个盒子都不为空，接下来在从每个盒子拿出来一个球，总共 $m$ 个，还回去，那么就相当于每个盒子可以为空，答案仍然是 $C_{n+m-1}^{m-1}$。
