Combinatorics

polya定理

在这里只谈一下polya定理是如何应用的。对于排成一排的带编号的小球，按照某一种方案改变其中一些球的放置顺序，可以称之为置换。每一种置换方法可以用两排数字來表示，第一排数字和第二排数字一一对应，第一排数字表示小球的原来位置（1～n），第二排数字表示小球交换后的位置。现在我们有n个小球，m种颜色。有k种置换方法，我们认为能通过置换方法交换位置后变成同一种染色情况（颜色的排列状况相同，忽略小球编号），则我们认为这些互相通过置换能达到的状态为同一种染色方法。我们现在要求总共有多少种染色方法。要计算方法数，我们先要计算k种置换方法中每种置换方法中含有的环数，即建立一个图，有n个点，把每个置换方法两排数字中的上下一一对应的数字对看成边的起点和终点，计算这个图中有几个环。我们设环数分别为c1~ck。那么染色方法数为(m^c1+m^c2+...+m^ck)/k。以上就是polya定理，这里要注意的是置换方法集合必须是群，需要满足封闭性，即如果把通过该集合中的若干个方法连续进行置换压缩成一个置换方法（用两排数子表示），那么这种新的置换方法也必须属于该集合。

容斥原理

假设平面上有一些圆，互相之间有重叠部分，我们要求这些圆覆盖的总面积（重叠部分只记一次）。计算方法就是：加上所有被覆盖了至少1次的面积加，减去所有被覆盖了至少2次的面积，加上所有被覆盖了至少3次的面积……对于奇数的就加，对于偶数的就减，最终结果即为覆盖的总面积。把这些圆变成是集合的话，那么这个计算过程就是容斥原理。

有重复组合

从n个元素中有重复地取r个，不计顺序，则不同的取法有多少种？

这个问题的答案被称为有重复组合数。结果很简洁，是C(n+r-1,r)。(注：这表示从n+r-1个数中取出r个数的组合数)

【证明】

将n个元素看做n个盒子,r看作r个无区别的球,则相当于:

把r个同样的球放入n个顺次排列的盒子,求不计放球顺序的放法种数

用0表示盒子,1表示球

我们把这n个0和r个1写在一行上。

由于球必须放在盒子中,规定某个0之前,到上一个0为止的1的个数,表示该盒子中装的球数

注意到最后一个数必须是0

所以相当于从前面n+r-1个位置中挑出r个位置放1，其余n-1个位置放0

求排列Rank

求一个排列是第几种排列的方法：设f(x)表示x位后面比x小的元素的个数，那么该排列的在全排列中的排位 $rank=\sum_{i=1}^{n}{( f(i) * ( (n-i)! ) )}$ 。 $rank \in [0, n!-1]$ 。

期望重组

现有随机变量X，传统求X期望的方法是把X的每个取值乘以其概率再加和。

而现在我们要对X的每个取值进行重组。

例如， $E(X)=\sum{x_i p_i}$ 。当 $X=x_i$ 时，我们把 $X$ 看作是 $n$ 个随机变量的和。 $p_i$ 是恰好和为 $x_i$ 时的概率。

这想当与是按照 $X$ 的每种取值进行分类计算。

现在我们给出另外一种求法。

设这n个随机变量总共有M种不同的取值方法。

（如果这些随机变量相互独立，那么M=m1*m2*...*mn，mi表示第i个随机变量有多少种取值。）

我们对于每一个随机变量ai都把M种情况枚举一次，计算每种情况发生的概率乘以ai在该种情况下的取值，并加和。

最后把所有随机变量的加和再加和，就是我们要求的E(X)。