组合里最基本的两个数是n和r，其中n为可选物品的种类(如果不能重复数量和个数是等价的)，r为实际选出的物品的数量(更准确的说是做出选择的次数，因为如果允许重复，选r次可能选出小于r个物品)，可以用下图表示
| $S_1$ | $S_2$ | $S_3$ | $S_r$ | ||
| $O_1$ | x | $x_1$ | |||
| $O_2$ | x | $x_2$ | |||
| $O_3$ | x | $x_3$ | |||
| $O_4$ | $x_4$ | ||||
| $O_n$ | x | $x_n$ |
任何选择，最基本的要求是最后有r次选择，而且一次选择不能选两个，所以上面表中x的数量必须为r个。
允许重复的意思是：一行可以有多个x。
ordered的意思是：物品在第几次被选中被认为是有区别的。
所以，unordered的意思是：把每行的x的个数加起来，记为$x_i$，如果通过$x_i$不能区分认为选择是一样的。
例子：集合里有m个元素，子集的个数。这时候$O_1=1,O_1=0$，$r=m$，也就是从$0,1$里选m次组成一个二进制数，组合不是看最终选出了几个东西，这里显然最多选出2个：0和1，要计算的数量是不同二进制数的数量。
特列：2个元素集合的子集的个数
xx | __ | _x | x_
__ | xx | x_ | _x
一共$2^2$个，如果是unordered的，最后两个会被认为是一样的，${3\choose 2}=3$个
组合问题一定要搞清楚最后选出来的是什么东西，比如4个球放到10个盒子里，有几种放法，这个问题最终选出来的是4个盒子；如果允许重复，就是说4个盒子里面可以有两个盒子是相同的(反过来说就是某个盒子里可以有不止一个球，盒子的总数就小于4个了)；如果4个球可以区分，也就是1号球在盒子1里，2号球在盒子2里，与1号球在盒子2里，2号球在盒子1里是不同的结果，这时候叫ordered，也就是说假设球是排序的，我们按球的顺序给它们找盒子，第一次找到1号盒子，与第一次找到2号盒子是不一样的，如果球不能区分，你是排不了序的。
上面的讨论显然默认被选的物品是可以区分的，如果被选物品是不能区分的，比如上面的问题，盒子不能区分，得到的结果就是4个球被划分成子集的方式的数量。如果球也不能区分，就变成整数4可能被划分的方式的数量。
1) $n$种物品中取$r$个，unordered(未知数的个数减一个0来分隔$r$个1)： $${n+r-1 \choose r}$$
证明：问题等价于$$x_1+\cdots +x_n = r$$的非负整数解的个数，而这个方程的每个解可以用一个二进制数表达。 $$\underbrace{11\cdots1}_{x_1}\ 0\ \underbrace{11\cdots1}_{x_2}\ 0\ \cdots \ 0\ \underbrace{11\cdots1}_{x_n}$$ 这样的二进制数是$n+r-1$个位置里选$r$个填1，其他的填0。显然1的和是$r$，把$n-1$个0看成间隔，可以得到$n$个数。这样得到方程解和长度为$n-1+r$，并且其中$n-1$个0，$r$个1的二进制数的一一对应。
2) Binomial Coefficients
加法 $${n+1\choose r}={n \choose r}+{n \choose r-1}$$ 乘法 $${n\choose r}=\frac{n}{r}{n-1 \choose r-1}$$ 设整数满足$j\leq k\leq i$，则有： $${i\choose k}{k\choose j}={i\choose j}{i-j\choose k-j}$$ 证明：考虑长度为$i$的三进制数，要求有$j$个0，$k-j$个1，上面的等式表示了两种构造方式
左边：$i$个位置里选$k$个，除去他们其他位置填2，然后在$k$个位置里选$j$个填0，其他填1。
右边：$i$个位置里选$j$个填0，剩下$i-j$个位置，选$k-j$个填1，其他填2。
进一步有： $$\sum_{j\leq k\leq i}{i \choose k}{k\choose j}(-1)^k=0$$ 更进一步，定义矩阵$A$的元素$a_{ij}={i\choose j}$，矩阵$B$的元素$b_{ij}=(-1)^{i+j}{i\choose j}$，其中$0\leq i,j\leq n$则 $$BA=I$$ 也就是方程组 $$a_n = \sum_{k=0}^n{n\choose k}b_k$$的解为 $$b_n = \sum_{k=0}^n(-1)^{n+k}{n\choose k}a_k$$
3) 二阶线性递归关系 $$a_n=Aa_{n-1}+Ba_{n-2}$$ 如果假设 $$a_n=\alpha^n$$ 上面的递归化为 $$\alpha^2-A\alpha-B=0$$
5)Derangement
$1,\cdots, n$的排列，没有不动元素的排列称为Derangement，对某个$n$ Derangement的个数的递归公式是： $$d_n=(n-1)(d_{n-1}+d_{n-2})$$ 因为要把$n$个数的问题约化为$n-1$的问题，观察第$n$个数和第$n$个位置，$n$一定要占某个新位置，记为$i$，必有一个数被分配到位置$n$上，记为$j$。可以按$i=j$和$i\neq j$分为两种情况。
$i=j$的时候比较简单，除了$i, n$外其他的$n-2$个数对应一个$n-2$的Derangement，$i$有$n-1$种选择；
$i\neq j$的时候，考虑一个除了$j$的$n-1$个数需要安排到除了第$n$个位置的$n-1$个位置里；数$n$在这$n-1$个位置里有且只有一个位置$j$不能选，其他$n-2$个数也有且只有一个位置不能选就是这个数原先的位置，所以总个数是$d_{n-1}$。
(前几个$d_1 = 0,\ d_2=1,\ d_3 = 2,\ d_4=9$)
要解Derangement的递归，注意到 $$d_n-nd_{n-1}=(-1)^n$$ 也就是 $$\frac{d_n}{n!}=\frac{d_{n-1}}{(n-1)!}+(-1)^n\frac{1}{n!}$$ 所以 $$\frac{d_n}{n!}=\sum_{k=0}^n(-1)^k\frac{1}{k!}$$
$n!$个排列的划分，任何排列里保持不动的数字的个数可能是$1, 2, \cdots, n$个，不动数字的个数是$k$个的排列数量为 $${n\choose k}d_{n-k}$$ 所以 $$n!=\sum_{k=0}^n{n\choose k}d_{n-k}=\sum_{k=0}^n{n\choose k}d_{k}$$ 上面的式子正好是我们定义的矩阵$A$的一个特例，解出来可得$d_n$的表达式。
有了$n!$的这个分解，我们可以计算$n$个人把帽子集中起来，任选一个，正好拿到自己帽子的个数的人的期望。 $$ \begin{array}{l} E(X)&=\sum_k kP_k=\sum_k k\frac{{n\choose k}d_{n-k}}{n!}\\ &=\sum_k k{n\choose k}\frac{d_{n-k}}{n!}\\ &=\sum_k n{n-1\choose k-1}\frac{d_{n-k}}{n!}\\ &=\frac{1}{(n-1)!} \sum_k{n-1\choose n-k}d_{n-k}\\ &=\frac{1}{(n-1)!} (n-1)!\\ &=1 \end{array} $$
6)排序
用Mergesort合并两个有序的队列的时候，比较的次数是$m+l-1$，可以把Merge的过程看成从比较两个队列的第一个元素，然后去掉小的那个，以此类推，一共有$m+l$分元素需要去掉，但是当两个队列一共只剩一个元素的时候是不需要比较的，所以减去1。
7)Catalan Numbers $p_n$
描述1：$n\times n$的正方形网格，$n+1$为边上的节点数，从左下角到右上角的不越过对角线的路径数。如果把正方形转135度，可以把对角线看成地平线，路径看成从不陷入地平线以下的山的数量。($p_n$里的$n$为一个方向上走了$n$步)
描述2：长度为$2n$的二进制数，有$n$个1，$n$个0，对任何$m \leq 2n$前$m$个数字中的1的个数不超过0的个数，这样的二进制数的个数。
对任意的$1 \leq k < n$，考虑所有在$(k, k)$碰到对角线并且是最后一次碰到对角线的路径，前半部分子路径的个数为$p_k$，后半段路径的第一步和最后一步是定的，可变的部分是(水平方向上)从第$k+1$到$n$，起点终点都减去$k+1$，得从$0$到$n-k-1$，也就是$p_{n-k-1}$个，$k$从$0$取到$n-1$可得Catalan Number的递归公式： $$p_n=\sum^{n-1}_{k=0}p_kp_{n-k-1}$$
解递归得 $$p_n=\frac{1}{n+1}{2n\choose n}$$
8)Stirling Numbers $S(n, k)$
定义：$n$集合划分为$k$子集的，这样划分的总数记为Stirling Numbers，满足递归关系 $$S(n, k)=S(n-1, k-1)+kS(n-1, k)$$ 证明：考虑元素n是单独一个子集还是和其他元素分在一个子集里，分为两种划分方式，可以导出递归关系。
所有n集合的所有划分称为Bell numbers，记为$B(n)$，也就是 $$B(n)=\sum_{k=1}^nS(n, k)$$ 考虑第n个元素，n必然和其他$j$个元素分在一起，其中$j\geq 0$，现在把这$j$个元素拿掉，剩下的$n-1-j$个元素的划分有$B(n-1-j)$个，根据这个可得递归关系 $$B(n)=\sum_{j=1}^{n-1}{n-1 \choose j}B(n-1-j)=\sum_{k=1}^{n-1}{n-1 \choose k}B(k)$$
8)容斥原理：全集记为$S$，这些元素可以有$r$个属性，具有属性$i, j, \cdots, k$的元素的总个数记为i$N(i, j, \cdots, k)$，则至少具有一个属性的元素的个数为 $$\sum_i N(i) - \sum_{i < j}N(i, j) + \sum_{i < j < k}N(i, j, k) - \cdots + (-1)^{r-1}N(1, 2, \cdots, r)$$ 另一种表述，不具有任何属性的元素的个数 $$|S| - \sum_i N(i) + \sum_{i < j}N(i, j) - \sum_{i < j < k}N(i, j, k) - \cdots + (-1)^{r}N(1, 2, \cdots, r)$$ 第二种表述可以用于计算素数的个数，小于n的合数必有小于$\sqrt{n}$的素因子，取所有小于$\sqrt{n}$的素数，假设有$r$个，一个数能被其中一个整除记为一个性质，不具有任何这样性质的数是小于n的所有素数和1去掉小于$\sqrt{n}$的素数。
容斥原理的特点是允许具有不同属性的子集有交集，但是交集有办法计算。开始之前一定要找好全集。
No comments:
Post a Comment