1) 定义
2012/05/30
2012/05/29
DNA
1) Sequence Alignment：两个字符序列，允许的操作是插入"-"，目标是使得对其的字母最多，但是加入"-"要接受惩罚。
初始字符串
加入"-"使得对齐的字符更多
可以看成A, B两个人出牌，每次出一张，可以不出，不能同时不出，A不出的话横着走一格，B不出竖着走一格，都出走到紧接着右下的格子。任何一个人得牌出完了就结束了，图里看就是到达了右边一列或者下边一排的格子。
用GDPP建模
a) $\Omega_{i,j}$的entiries定义为从开始到A出了$i$张牌，B出了$j$张牌的所有路径。
b) 变换定义为$\Omega_{i-1,j}, \Omega_{i,j-1}, \Omega_{i-1,j-1}$里的entries，通过再次出牌变为$\Omega_{i,j}$的entries。
c) 变换的价值定义为：一个人不出的话-1( $\Omega_{i-1,j}, \Omega_{i,j-1}$里过来的 )，都出了但是不一样+0，出了一样+1( $\Omega_{i-1,j-1}里过来的$ )。
d) 最优函数定义为$\mathcal{F}(\Omega_{i,j})$所有路径价值的最大值，阶段是二维index，每个阶段只输出一个值。
e) 递归关系是： $$\mathcal{F}(\Omega_{i,j})=\max[ \mathcal{F}(\Omega_{i-1,j}) - 1, \mathcal{F}(\Omega_{i,j-1}) - 1, \mathcal{F}(\Omega_{i-1,j-1})+ \delta( M_{i,j} = X ) ]$$
初始字符串
加入"-"使得对齐的字符更多
可以看成A, B两个人出牌，每次出一张，可以不出，不能同时不出，A不出的话横着走一格，B不出竖着走一格，都出走到紧接着右下的格子。任何一个人得牌出完了就结束了，图里看就是到达了右边一列或者下边一排的格子。
用GDPP建模
a) $\Omega_{i,j}$的entiries定义为从开始到A出了$i$张牌，B出了$j$张牌的所有路径。
b) 变换定义为$\Omega_{i-1,j}, \Omega_{i,j-1}, \Omega_{i-1,j-1}$里的entries，通过再次出牌变为$\Omega_{i,j}$的entries。
c) 变换的价值定义为：一个人不出的话-1( $\Omega_{i-1,j}, \Omega_{i,j-1}$里过来的 )，都出了但是不一样+0，出了一样+1( $\Omega_{i-1,j-1}里过来的$ )。
d) 最优函数定义为$\mathcal{F}(\Omega_{i,j})$所有路径价值的最大值，阶段是二维index，每个阶段只输出一个值。
e) 递归关系是： $$\mathcal{F}(\Omega_{i,j})=\max[ \mathcal{F}(\Omega_{i-1,j}) - 1, \mathcal{F}(\Omega_{i,j-1}) - 1, \mathcal{F}(\Omega_{i-1,j-1})+ \delta( M_{i,j} = X ) ]$$
2012/05/27
Colouring
顶点的着色把顶点分成不同的集合，所以着完色后，这些集合之间的边的性质决定了着色的性质。
比如bipart是用分成两个集合，边的性质是：任何一个边的两个端点分别在不同的集合里。
但是并不是所有的图都可以这样把顶点集合分成两部分，使得没有两个相邻顶点的颜色相同。一般的着色问题是，至少需要把顶点分成几部分？
1) 贪心算法：a) 把图的节点排序，颜色排序。 b) 给第$i$个节点着色的时候检查它所有已经着色的邻居找到最小的没被用过的颜色，用这个颜色
分析：如果一个节点的degree为d，那么遍历颜色最坏的情况是前d个颜色都被用了，只能用第d+1个颜色。从整个图来看，图的最大degree给使用的颜色(chromatic number)一个上界$\Delta+1$
n个委员会，其中可能有重复的成员，安排他们开会，显然不能有重复成员的委员会被安排到同一天开会，问题：找到最小的天数使得每个委员会都能开一次会。模型是以每个委员会为顶点，以有重复成员的关系为边画一个图，找出图的chromatic number。
比如bipart是用分成两个集合，边的性质是：任何一个边的两个端点分别在不同的集合里。
但是并不是所有的图都可以这样把顶点集合分成两部分，使得没有两个相邻顶点的颜色相同。一般的着色问题是，至少需要把顶点分成几部分？
1) 贪心算法：a) 把图的节点排序，颜色排序。 b) 给第$i$个节点着色的时候检查它所有已经着色的邻居找到最小的没被用过的颜色，用这个颜色
分析：如果一个节点的degree为d，那么遍历颜色最坏的情况是前d个颜色都被用了，只能用第d+1个颜色。从整个图来看，图的最大degree给使用的颜色(chromatic number)一个上界$\Delta+1$
n个委员会，其中可能有重复的成员，安排他们开会，显然不能有重复成员的委员会被安排到同一天开会，问题：找到最小的天数使得每个委员会都能开一次会。模型是以每个委员会为顶点，以有重复成员的关系为边画一个图，找出图的chromatic number。
2012/05/26
Travelling Round a Graph
Hamiltonian是要求访问所有的节点，所以边越多的图越容易成为可能；Eulerian是要求访问所有的边。
1) Hamiltonian Graph
Dirac定理：$G$是一个简单图，有$p$个节点，如果所有节点的degree都大于$\frac{1}{2}p$，那么图里存在Hamilton回路。
如果图里有Hamilton回路，有一个算法可以决定图是不是平面图，把图的Hamilton回路画在平面上使其是图的外边缘，其他的边都在这个回路的内部。内部的边一般会相交，如果能把这些内部的边分成两类，它们的交点只发生在两类之间(可以用另外一个图，节点是原图的边，如果两边在原图相交，在这个新图里加一条边，如果这个新图是两部图那个这个分类就是可能的)，可以把这两类边一类画在回路内部，一类画在回路外部，这样就得到一个平面图的画法。
TSP：TSP的解的长度大于最小支持树的长度，小于最小支撑树的长度的2，即$MST < TSP \leq 2\ MST$。
下界：根据下面两个事实可以构造下界
a) Hamilton回路有两条边和图里的任何一个节点相关的方式是，一个边进入一个边出来。
b) 如果从图里去掉一个节点$v$，Hamilton回路里这个节点也去掉，剩下的Hamilton回路是剩下的图的一个MST，这个MST加上一条到$v$的边，得到一个原图的MST。
上界：如果沿着图的MST走一遍在转回来是图的一个回路，这个回路的长度是MST的2倍，通过这个回路可以构造一个Hamilton回路，这个Hamilton回路的长度不大于刚才的MST回路。
Gray Godes：是$2^n$个长度为$n$的二进制数的一个排列，特点是相邻的两个只差一位。可以看成$n$立方体的顶点的一个Hamilton回路，下图是3位Gray Godes的生成方式
a) 相邻顶点之间只差一个坐标。
b) 立方体上面的4个顶点最后一位是1，除了最后一位前两位构成$n=2$的Gray Godes，下面4个顶点最后一位是0，除了最后一位前两位构成$n=2$的Gray Godes。把两个$n=2$的Gray Godes接起来的位置是各自的$n=2$起点和终点。上面$n=2$的Hamilton回路反过来走，完成回路的最后一步不去终点，直接到另一个$n=2$的Hamilton回路，正过来在走一次，这样得到$n=3$的Hamilton回路。这个性质可以推广到n维的情况，递归的由$n-1$的Gray Godes获得，给出了一种Gray Godes的生成方法。
2) Eulerian Graph
定理：图里有Euler回路的充要条件是所有节点的degree都是偶数。
证明：如果一个图所有节点的degree都是偶数，那么这个图是由没有共边的回路构成，这个结论可以用归纳法证明，任选一个起点，开始一个walk，当遇到已经被walk包含的节点的时候，得到一个回路，把这个回路包含的边从图里去掉，每个节点减少的degree是2，所以剩下的图仍然满足所有节点都是偶数。
定理：图里存在Euler trail的充要条件是有且只有两个节点的degree是奇数。
得更紧的TSP上界，方法是从MST开始，加入一些边使得得到的新图里面有一个Eular回路，然后改变这个Eular回路遇到重复的节点的时候走shortcut得一个Hamilton回路，可以证明这个Hamilton回路的长度小于$\frac{3}{2}$TSP。
3) 有向图
定理：有向图里Eular回路存在的充要条件是每个节点的indegree和outdegree相等。
Memory wheel：把$2^n$个0,1排成一个圆，这个圆开始转，从任何一个点开始，记录$n$个数字构成一个二进制数，从任何一点开始都可以记录，所以有$2^n$种可能。Memory wheel是使得每个得到的$n$二进制数都不同。
模型：要做记录的二进制长度为$n$的Memory wheel，构造一个有向图，Memory wheel的特点是当前数的后$n-1$个数字和下一个数的前$n-1$个数字相同。也就是说知道当前数字，后面的数字前$n-1$个数字已经定了，后面那个数字有两个可能。用有向图描述，就是出发后可能的去向A0和A1。
先画顶点，顶点为长度为$n-1$的二进制数，顶点代表的是xA，出发到达的顶点是A0和A1。然后在图里找到一个Eular回路就得到了一个Memory wheel构造方式，现在这样的图里Eular回路是存在的。
1) Hamiltonian Graph
Dirac定理：$G$是一个简单图，有$p$个节点，如果所有节点的degree都大于$\frac{1}{2}p$，那么图里存在Hamilton回路。
如果图里有Hamilton回路，有一个算法可以决定图是不是平面图，把图的Hamilton回路画在平面上使其是图的外边缘，其他的边都在这个回路的内部。内部的边一般会相交，如果能把这些内部的边分成两类，它们的交点只发生在两类之间(可以用另外一个图，节点是原图的边，如果两边在原图相交，在这个新图里加一条边，如果这个新图是两部图那个这个分类就是可能的)，可以把这两类边一类画在回路内部，一类画在回路外部，这样就得到一个平面图的画法。
TSP：TSP的解的长度大于最小支持树的长度，小于最小支撑树的长度的2，即$MST < TSP \leq 2\ MST$。
下界：根据下面两个事实可以构造下界
a) Hamilton回路有两条边和图里的任何一个节点相关的方式是，一个边进入一个边出来。
b) 如果从图里去掉一个节点$v$，Hamilton回路里这个节点也去掉，剩下的Hamilton回路是剩下的图的一个MST，这个MST加上一条到$v$的边，得到一个原图的MST。
上界：如果沿着图的MST走一遍在转回来是图的一个回路，这个回路的长度是MST的2倍，通过这个回路可以构造一个Hamilton回路，这个Hamilton回路的长度不大于刚才的MST回路。
Gray Godes：是$2^n$个长度为$n$的二进制数的一个排列，特点是相邻的两个只差一位。可以看成$n$立方体的顶点的一个Hamilton回路，下图是3位Gray Godes的生成方式
a) 相邻顶点之间只差一个坐标。
b) 立方体上面的4个顶点最后一位是1，除了最后一位前两位构成$n=2$的Gray Godes，下面4个顶点最后一位是0，除了最后一位前两位构成$n=2$的Gray Godes。把两个$n=2$的Gray Godes接起来的位置是各自的$n=2$起点和终点。上面$n=2$的Hamilton回路反过来走，完成回路的最后一步不去终点，直接到另一个$n=2$的Hamilton回路，正过来在走一次，这样得到$n=3$的Hamilton回路。这个性质可以推广到n维的情况，递归的由$n-1$的Gray Godes获得，给出了一种Gray Godes的生成方法。
2) Eulerian Graph
定理：图里有Euler回路的充要条件是所有节点的degree都是偶数。
证明：如果一个图所有节点的degree都是偶数，那么这个图是由没有共边的回路构成，这个结论可以用归纳法证明，任选一个起点，开始一个walk，当遇到已经被walk包含的节点的时候，得到一个回路，把这个回路包含的边从图里去掉，每个节点减少的degree是2，所以剩下的图仍然满足所有节点都是偶数。
定理：图里存在Euler trail的充要条件是有且只有两个节点的degree是奇数。
得更紧的TSP上界，方法是从MST开始，加入一些边使得得到的新图里面有一个Eular回路，然后改变这个Eular回路遇到重复的节点的时候走shortcut得一个Hamilton回路，可以证明这个Hamilton回路的长度小于$\frac{3}{2}$TSP。
3) 有向图
定理：有向图里Eular回路存在的充要条件是每个节点的indegree和outdegree相等。
Memory wheel：把$2^n$个0,1排成一个圆，这个圆开始转，从任何一个点开始，记录$n$个数字构成一个二进制数，从任何一点开始都可以记录，所以有$2^n$种可能。Memory wheel是使得每个得到的$n$二进制数都不同。
模型：要做记录的二进制长度为$n$的Memory wheel，构造一个有向图，Memory wheel的特点是当前数的后$n-1$个数字和下一个数的前$n-1$个数字相同。也就是说知道当前数字，后面的数字前$n-1$个数字已经定了，后面那个数字有两个可能。用有向图描述，就是出发后可能的去向A0和A1。
先画顶点，顶点为长度为$n-1$的二进制数，顶点代表的是xA，出发到达的顶点是A0和A1。然后在图里找到一个Eular回路就得到了一个Memory wheel构造方式，现在这样的图里Eular回路是存在的。
凸分析 基本概念
1)凸函数的一阶导数性质： 如果定义在$C$上的函数$f$一阶可导则，则$f$是凸函数和下面的式子等价
$$f(z) \geq f(x) + \nabla f(x)(z-x)$$
用语言描述就是用一阶导数做的线性approximation会低估凸函数。
上面的性质可以导出，$f$在$x^*$取到$C$上极小值的充要条件是 $$\nabla f(x^*)(z-x^*)\geq 0,\ \forall z \in C$$ 2)投影定理：$C$是$R^n$上的非空凸子集，$z\in R^n$，那么存在$C$里的唯一的向量极小化$\|z-x\|$，这个向量称为$z$在$C$上的投影，并且对$C$里的所有向量，$z$的投影$x^*$有下面的性质 $$(z-x^*)^T(x-x^*)\leq 0$$ 也就是两个向量，(从投影出发指向$z$)和(从投影出发指向任何$C$里的一个点)，夹角不小于90度。
上面的性质可以导出，$f$在$x^*$取到$C$上极小值的充要条件是 $$\nabla f(x^*)(z-x^*)\geq 0,\ \forall z \in C$$ 2)投影定理：$C$是$R^n$上的非空凸子集，$z\in R^n$，那么存在$C$里的唯一的向量极小化$\|z-x\|$，这个向量称为$z$在$C$上的投影，并且对$C$里的所有向量，$z$的投影$x^*$有下面的性质 $$(z-x^*)^T(x-x^*)\leq 0$$ 也就是两个向量，(从投影出发指向$z$)和(从投影出发指向任何$C$里的一个点)，夹角不小于90度。
2012/05/22
Emacs
光标移动
C-n(ext logical line), C-p(revious logical line), C-f(orward by character), C-b(ackward by character)
C-a(head to this line), C-e(nd of this line)
M-f(orward by word), M-b(ackward by word), M-a(head a sentence), M-e(nd of next sentence)
C-up(to next paragraph), C-down(to next paragraph)
C-v to scroll down, M-v to scroll up, C-M-v用于翻页另一个frame的内容，M--加前面是负的翻页
M-< to move to the beginning of the buffer, and M-> to move to the end.
C-M-f and C-M-b跳括号或者引号
C-M-d and C-M-u跳入下一个或者上一个括号里。
C-n(ext logical line), C-p(revious logical line), C-f(orward by character), C-b(ackward by character)
C-a(head to this line), C-e(nd of this line)
M-f(orward by word), M-b(ackward by word), M-a(head a sentence), M-e(nd of next sentence)
C-up(to next paragraph), C-down(to next paragraph)
C-v to scroll down, M-v to scroll up, C-M-v用于翻页另一个frame的内容，M--加前面是负的翻页
M-< to move to the beginning of the buffer, and M-> to move to the end.
C-M-f and C-M-b跳括号或者引号
C-M-d and C-M-u跳入下一个或者上一个括号里。
2012/05/21
组合数学基本概念
0)不同组合的图解表示
组合里最基本的两个数是n和r，其中n为可选物品的种类(如果不能重复数量和个数是等价的)，r为实际选出的物品的数量(更准确的说是做出选择的次数，因为如果允许重复，选r次可能选出小于r个物品)，可以用下图表示
任何选择，最基本的要求是最后有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}$的素数。
容斥原理的特点是允许具有不同属性的子集有交集，但是交集有办法计算。开始之前一定要找好全集。
组合里最基本的两个数是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}$的素数。
容斥原理的特点是允许具有不同属性的子集有交集，但是交集有办法计算。开始之前一定要找好全集。
2012/05/15
Microsoft Word 97 Binary File Format
Word uses internally a PLC (PLex of Cps), but writes to files a PLCF (PLex of Cps in File)
CP (Character Position): Based logical text stream of a document.
FC( File Character position): (coordinate of the beginning of a document's text stream) + CP.
PLCF(PLex of Cps(or FCs) stored in File): relation between a certain CP(or FC) and an arbitrary data structure. It consists of an array of n+1 CPs or FCs followed by an array of n instances of a particular arbitrary data structure.
To properly interpret a PLCF stored in a Word file, the length of the stored PLCF and the length of the arbitrary data structure stored in the PLCF must be known. The length of the stored PLCF is recorded in the FIB. The lengths of the data structures stored in PLCFs within Word files are listed later in this document.
piece table: Array of CPs(plcfpcd) === A partitioning of the Word document into disjoint pieces. Array of PCDs (Piece Descriptors) === array of CPs of corresponding piece begins.
CP of the character TO FIND the piece that contains that character.
1)(CP => PCD)Index of the largest CP in the array of CPs that is less than the character CP.
2)Then reference the PCD with that index in the array of PCDs.
3)(PCD => FC of piece begin)The PCD gives the position of the beginning of the piece in the file.
4)CP + position of the piece beginning.
sprm (Single PRoperty Modifier): An instruction to modify one or more properties within one of the property defining data structures (CHP, PAP, TAP, SEP, or PIC). It consists of an operation code which identifies the field(s) to be changed, and an operand which gives the value that a particular field is changed to or else which is a parameter to a procedure which will change the field or fields. A prl (property modifiers stored in a list) is a sprm plus its operand.
A prl (property modifiers stored in a list) is a sprm plus its operand.
grpprl (group of prls): a set of sprms. to find: opcode => length of the sprm, then skip, and so on.
prm (PRoperty Modifier): A field in piece table entries, contains an index to a grpprl, If the user has made only a small change to formatting that can be expressed as a single 2 or 1-byte sprm, that sprm is stored within the prm.
FKP: count(of run or paragraph), array of FCs( boundaries between runs or paragraphs ), array of offsets within the FKP <==> array of FCs (beginning of a run)
A PLC records the association between a particular range of FCs and the PN (Page Number) of the FKP that contains the properties for that FC range in the file
RUN: A bin table (plcfbte) partitions the total extent of the Word file that contains text characters into a set of contiguous intervals marked by a fcFirst and an fcLim. The fcFirst for the nth interval would be plcfbte.rgfc[n] and the fcLim for the nth interval would be plcfbte.rgfc[n+1]. Associated with each interval is a BTE. A BTE holds a four-byte PN (page number) which identifies the FKP page in the file which contains the formatting information for that interval. A CHPX FKP further partitions an interval into runs of exception text.
CP (Character Position): Based logical text stream of a document.
FC( File Character position): (coordinate of the beginning of a document's text stream) + CP.
PLCF(PLex of Cps(or FCs) stored in File): relation between a certain CP(or FC) and an arbitrary data structure. It consists of an array of n+1 CPs or FCs followed by an array of n instances of a particular arbitrary data structure.
To properly interpret a PLCF stored in a Word file, the length of the stored PLCF and the length of the arbitrary data structure stored in the PLCF must be known. The length of the stored PLCF is recorded in the FIB. The lengths of the data structures stored in PLCFs within Word files are listed later in this document.
piece table: Array of CPs(plcfpcd) === A partitioning of the Word document into disjoint pieces. Array of PCDs (Piece Descriptors) === array of CPs of corresponding piece begins.
CP of the character TO FIND the piece that contains that character.
1)(CP => PCD)Index of the largest CP in the array of CPs that is less than the character CP.
2)Then reference the PCD with that index in the array of PCDs.
3)(PCD => FC of piece begin)The PCD gives the position of the beginning of the piece in the file.
4)CP + position of the piece beginning.
sprm (Single PRoperty Modifier): An instruction to modify one or more properties within one of the property defining data structures (CHP, PAP, TAP, SEP, or PIC). It consists of an operation code which identifies the field(s) to be changed, and an operand which gives the value that a particular field is changed to or else which is a parameter to a procedure which will change the field or fields. A prl (property modifiers stored in a list) is a sprm plus its operand.
A prl (property modifiers stored in a list) is a sprm plus its operand.
grpprl (group of prls): a set of sprms. to find: opcode => length of the sprm, then skip, and so on.
prm (PRoperty Modifier): A field in piece table entries, contains an index to a grpprl, If the user has made only a small change to formatting that can be expressed as a single 2 or 1-byte sprm, that sprm is stored within the prm.
FKP: count(of run or paragraph), array of FCs( boundaries between runs or paragraphs ), array of offsets within the FKP <==> array of FCs (beginning of a run)
A PLC records the association between a particular range of FCs and the PN (Page Number) of the FKP that contains the properties for that FC range in the file
RUN: A bin table (plcfbte) partitions the total extent of the Word file that contains text characters into a set of contiguous intervals marked by a fcFirst and an fcLim. The fcFirst for the nth interval would be plcfbte.rgfc[n] and the fcLim for the nth interval would be plcfbte.rgfc[n+1]. Associated with each interval is a BTE. A BTE holds a four-byte PN (page number) which identifies the FKP page in the file which contains the formatting information for that interval. A CHPX FKP further partitions an interval into runs of exception text.
2012/05/08
Subscribe to:
Posts (Atom)