集合排列

在$n$个元素中对$r$个元素进行有序选择,记为$A(n, r)$
则有 $A(n, r) = \frac{n!}{(n - r)!} = n * (n - 1) * (n - 2) * … * (n - r + 1)$

例1: 将26个字母排序, 使得元音字母不得相继出现, 问方案数.
我们们将21个辅音字母看作点, 5个元音字母便须在这21个辅音字母的间隙中存在才能满足不相邻.

由此图可以发现, $n$个点之间算上两边共有$n + 1$个空位, 因此元音字母的排列方案为$A(22, 5)$个
总方案便是
$A(21, 21) * A(22, 5) = \frac{21!22!}{17!}$

循环排列

例1： $6$个人排成一圈，有多少种不同的方式?
容易发现: 123456 234561 345612 456123 561234 612345 是等价的,即同属一种方案(通过旋转可得)
答案便是$\frac{6!}{6}$
更一般地便是$\frac{n!}{n}~n为集合元素数量 $
再一般些, 求$n$个元素中的循环$-r$排列, 即为
$\frac{A(n, r)}{r} = \frac{n!}{r(n - r)!}$

例2：10个人座一圆桌，其中有两人不愿彼此挨着就坐, 有多少种方案?
这是一个思维的转化: 总方案 = 两人挨着坐的方案 + 两人不挨着的方案
容易得到 两人不挨着的方案 = 总方案 - 两人挨着坐的方案.
所以我们可以先算出两人挨着坐的方案数.
将不应相邻的两人捆绑作$X$, 则有九个人{$X, 3, 4,…, 8, 9, 10$}的方案数,即为
$\frac{9!}{9} = 8!$
我们发现$X$有$1~2$ 和 $2~1$两种情况,
那么方案就要再乘上2, 即$2 * 8!$
所以,
两人不挨着的方案 = $\frac{10!}{10} - 2* 8! = 9! - 2 * 8!$

集合组合

在$n$个元素中对$r$个元素进行无序选择, 即为${n \choose{r}}$ 或者$C(n, r)$.

特别的：
${n \choose{0}} = 1 ~~ {n \choose{1}} = n ~~ {n \choose{n}} = 1$

${0 \choose{0}} = 1$ 意为0个中选0个也有一种方案.
我们可以发现$r$个数的所有排列$r!$对应一个组合, 即
$A(n, r) = r!{n \choose{r}}$
于是
${n \choose{r}} = \frac{n!}{r!(n - r)!}$

例1：如果每个词有3、4或5个元音,那么26个字母能构造多少个8-字母词？
考虑加法原理，首先分元音个数计数.
3元音词: 元音的位置有${8 \choose{3}}$种, 因为单词可以重复, 所以元音有$5^3$种, 辅音有$21^5$种,
因此根据乘法原理 方案数便是${8 \choose{3}} 5^3 21^5$
同理, 4元音词的方案数是${8 \choose{4}} 5^4 21^4$, 5元音词的方案数是${8 \choose{5}} 5^5 21^3$
那么总的方案数便是
${8 \choose{3}} 5^3 21^5 + {8 \choose{4}} 5^4 21^4 + {8 \choose{5}} 5^5 21^3$个

集合还有一些额外的性质:
${n \choose{r}} = {n \choose{n - r}}$

${n \choose{0}} + {n \choose{1}} + {n \choose{2}} + {n \choose{3}} … + {n \choose{n - 1}} + {n \choose{n}} = 2^n$

多重集排列

令$S$是一个多重集, 有$k$个不同类型的元素, 各元素都有无限重复次数, 那么$S$的r-排列为$k^r$(每个位置上的选择都有$k$种)

令$S$是一个多重集, 有$k$个不同类型的元素, 各元素的重数分别为{$n_1, n_2, n_3,…,n_k$}
设$S$的大小$n$为$n_1 + n_2 + n_3 +…+ n_k$,则$S$的排列数为
$\frac{n!}{n_1!n_2!n_3!…n_k!}$
每一类元素相同, 它们位置互换对排列没有影响, 所以要除去它们的排列数.
例1: mississippi的排列数.
计算{$m*1, i*4, s*4, p*2$}的排列数, 答案为
$\frac{11!}{1!4!4!2!}$
这个式子还能表示把集合划分成指定大小的部分之后给每个部分贴上标签.

令$S$表示一个多重集,$S$的大小为 $n_1 + n_2 + … + n_k$,将$n$个元素的集合划分成$k$组放进带标签的$k$个盒子(每个盒子放任意一部分), 方案数等于:
$\frac{n!}{n_1!n_2!n_3!…n_k!}$
(不在乎每个盒子内的小球的顺序)

令$S$表示一个多重集,$S$的大小为 $n_1 + n_2 + … + n_k$,将$n$个元素的集合划分成$k$组放进不带标签的$k$个盒子(每个盒子放任意一部分), 方案数等于:
$\frac{n!}{\textbf{k!}n_1!n_2!n_3!…n_k!}$
(在刚刚的基础上除去盒子的排列)

非攻击型车问题

在$8 * 8$的国际象棋棋盘上, 两个车能够相互攻击的条件是它们位于棋盘的同一行或者同一列.
那么对于$8$个非攻击型车有多少种可能的方法？
显然, $8$辆车不能再同一列, 即横坐标不同,那么每一列上必定有辆车, 那么这$8$辆车的坐标一定是$(1, j_1)~(1, j_2)…(1, j_8)$
因此$j$就是$8$的全排列.
那么答案就是$8!$.

在上面的例子中,我们假设每辆车都是等价的. 那么若这$8$辆车各不相同, 方案数是多少呢?
也很简单, 就看成每辆车的颜色各不相同,
乘上颜色的排列即可, 即乘上$8!$,
那么答案就是$8!8! = (8!)^2$

那么假设有$2$个红车, $3$个绿车, $3$个蓝车, 方案数又是多少呢?
这就要用到刚才的多重集排列了.
位置和染色分开来做, 染色的排列为$\frac{8!}{2!3!3!}$,位置的排列还是$8!$
那么方案数就等于
$\frac{8!8!}{2!3!3!}$

更一般的,有$n$辆车共$k$种颜色, 第一种颜色的车有$n_1$个, 第二种颜色的车有$n_2$个…第$k$种颜色的车有$n_k$个.
把这些车放在$n * n$的棋盘上, 非攻击型车的方案数等于
$n!\frac{n!}{n_1n_2…n_k} = \frac{(n!)^2}{n_1n_2…n_k}$

多重集组合

令$S$为具有$k$种类型元素的多重集, 每种元素具有无限个的重复数.
求每种元素至少选1个的S的r-组合的个数.

这里的个数即为$x_1 + x_2 + … + x_k = r$ 的正整数解的个数.($x_i > 0$)
可以运用隔板法.

上图中每一个点代表选出的$r$个元素中的其中一个元素.
容易发现, 可用$k - 1$个木板把集合中所有元素分为$k$类,每一类便对应着$x_i$.
$r$个元素之间有$r - 1$个空.
因此可以得到方案数为${r - 1 \choose{k - 1}} = {r - 1 \choose{r - k}}$个.

那么每种元素至少选0个(即可以不选)的S的r-组合的个数.
这里的个数即为$x_1 + x_2 + … + x_k = r$ 的非负整数解的个数.($x_i >= 0$)
可设$y_i = x_i + 1$, 那么就有方程:
$y_1 + y_2 +…+ y_k = r + k$
此时的$y_i$就是一个正整数, 那么本题就转化为了上面的那道问题.‘
因此答案为:
${r + k - 1 \choose{k - 1}} = {r + k - 1 \choose{r}}$

接下来看几道例题. 要点: 将题目转化成方程的形式.
例1: 一家面包房生产$9$种炸面包圈, 如果一盒内装有$12$个炸面包圈, 那么你能买到多少种不同的盒装面包圈?
先将题目转化成方程的形式, 即为
$x_1 + x_2 +…+x_9 = 12$.(x_i >= 0)
因此很容易就能得出答案${12 + 9 - 1 \choose{12}} = {20 \choose{12}}$.

例2: $S$集合里a, b, c, d 各有10个, 求有几个10-组合满足a, b, c, d都至少出现一次?
先将题目转化成方程的形式, 即为
$x_1 + x_2 + x_3 + x_4 = 10$($0 <x_i <= 10$)
易得答案为 ${9 \choose{3}}$

例3: 方程$x_1 + x_2 + x_3 + x_4 = 20$的整数解有多少?
其中: $x_1 >= 3, x_2 >= 1, x_3 >= 0, x_4 >= 5$

这题已经把题目转化成了方程的形式,但是每个$x_i$的取值范围不同.
这是便可以设$y_1 = x_1 - 3, y_2 = x2 - 1, y_3 = x_3, y_4 = x_4 - 5$, 方程便变化为
$y_1 + y_2 + y_3 + y_4 = 11$($y_i >= 0$)
转化成了经典的隔板法问题.
答案便是${11 + 4 - 1 \choose{11}} = {14 \choose{11}}$

Pascal 公式

${n \choose{k}} = {n - 1 \choose{k}} + {n - 1 \choose{k - 1}}$
给一种十分直观的证明:

已知${n \choose{k}}$表示在$n$个元素中选$k$个元素(不在乎顺序).

那么可以以第$n$个元素是否被选上分类讨论:
1. 第$n$个元素没有被选上.
那么就在前$n - 1$个元素中选$k$个.
2. 第$n$个元素被选上.
那么就在前$n - 1$个元素中选$k - 1$个.

于是总的方案数就是这两种方案数加起来, 得到了Pascal公式.

这个公式可以用来预处理$n \choose{m}$, 代码如下:

void init() 
{
    for(int i = 0; i < N; i++)
        for(int j = 0; j <= i; j++)
            if(!j) c[i][j] = 1;
            else c[i][j] = ((long long)c[i - 1][j] + c[i - 1][j - 1]) % mod;
}

具体题目见885. 求组合数 I.

由这个公式还能推出二项式定理, 但本人现在还用不着, 就不写了.

小球与盒子

可辩别的小球和可辩别的盒子

$n$个不同的小球分配到$k$个不同的盒子, 使得第$i$个盒子中放入$n_i$个物品的方案数.
即为多重集排列, 为
$\frac{n!}{n_1!n_2!…n_k!}$

不可辩别的小球和可辩别的盒子

即为多重集组合.
$n$个相同的小球分配到$k$个不同的盒子,
每个盒子至少分一个小球的方案数.
$n - 1 \choose{k - 1}$

盒子可以为空的方案数.
$n + k - 1 \choose{k - 1}$

剩下的就不会了aaaa

错排数

$D(n) = (n - 1)(D_{n - 2} + D_{n - 3})$
易得$D(1) = 0, D(2) = 1$ 剩下的递推即可.