先唠叨一句

小奥的组合数学是真的香，我当时csp2020-j初赛的组合数学题就用小奥+亿点枚举居然就都做对了：）

排列组合

两种原理

加法原理

假设你现在要从A城到B城市

有三种方法：

加法原理

坐飞机有三条航线（蓝）

开车有三条高速（绿）

坐高铁有两班（棕）

那请问一共有几种选择？

$3 + 3 + 2 = 8$

诶嘿，这就是加法原理。

乘法原理

现在我们不去B城，去C城

但是要经过B城乘法原理

请问一共有几种出行方式？

当我们走a到b的第一条路，b到c有8种可以选

当我们走a到b的第二条路，b到c有8种可以选

以此类推

当我们走a到b的第8条路，b到c有8种可以选

因此，A到B有8条路，B到C有8条路

那一共就有

$8\times8 = 64$

这就是乘法原理，非常简单。

基础排列组合

排列数

您和您的伙伴一共8人，要去C城，正在机场排队安检，请问您们有几种排队顺序？

可以想一下，现在有八个位置

现在您们8个人要抢第1个位置，也就是说第1个位置有八种选择

~~经过一番打斗后,~~ 剩下的7个人去抢第二个位置，第2个位置有7种选择

以此类推

根据乘法原理

一共有

$8\times7\times6\times5\times4\times3\times2\times1 = 8! = 40320 种$

可以发现， $$n$$ 个元素排列时，一共有 $n!$ 种排法。

现在您们8人在候机，发现只有4个椅子，您们有几种坐法？（顺序不同也算一种方法）

首先，您们8人抢第一个椅子，第一个椅子有8种选择

然后抢第二个，第二个椅子有7种选择

然后抢第三个，第三个椅子有6种选择

然后抢第四个，第四个椅子有5种选择

然后？然后剩下的人站着！（

于是坐法就有

$8\times 7\times 6\times\ 5 = 1680种$

替换成字母就是：n个元素排一个长度为m的序列，有多少种排法？

$S = n\times(n-1)\times(n-2)\times...\times(n-m+1)$

简化可得：

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

现在我们来看一些概念

现在n个元素排一个长度为m的序列，这个排列数我们用 $A_n^m$ （或 $P_n^m$ ）表示

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

前面您8人安检时的排列，即 $n=m$ 时，这样的排列叫做全排列

$A_n^n = n!$

组合数

您到了C城，面前有10架共享单车，您和您的伙伴一共8个人，每人选一架共享单车，有几种选法？(共享单车都是一样的，没有什么顺序之分，别抬杠（（ )