Skip to content

《组合数学》缩写(四)

第8章

本章介绍了很多著名的数列,我认为这是本书最激动人心的一章。

Catalan数:C_n = C(2n,n) / (n+1);C_n = ΣC_i*C_(n-i),其中0≤i<n;C_n=C_(n-1)*(4n-2)/(n+1)。它的意义有很多,例如:n+1边形用对角线划分成三角形的方法数;n个+1和n个-1满足所有部分和不小于零的排列数;具有n个节点的二叉树的数量……

对于数列h_i,定义它的(一阶)差分序列Δh_i=h_(n+1)-h_n。它的p阶差分序列就是p-1阶差分序列的差分序列。如果某个序列是n的p次多项式,它的p+1次差分就全是0,p次差分是常数列。利用这个原理可以在给出前n+1项的前提下求解这种序列。差分运算满足对加法的分配率。

序列差分表由它的第0行确定,也就是原序列,但同时也可以由第0条对角线上的元素确定。换句话说,由差分表的第0条对角线就可以确定原序列。有这样两个公式:原序列为h_i,第0条对角线为c_o,c_1,…,c_p,0,0,0,…则h_n = c_0*C(n,0)+c_1*C(n,1)+…+C(n,p),Σh_k(k=0..n) = c_0*C(n+1,1)+c_2*(n+1,2)+…+c_p*C(n+1,p+1)。记住这两个公式,差分表(的第0条对角线)就变得非常有用了。

第二类Stirling数:S(p,k) = k*S(p-1,k) + S(p-1,k-1);S(p,0)=0(p≥1),S(p,p)=1。它的意义是将p个元素的集合划分成k个不可辨别的非空集合的方法数。上面的递推式可以用组合证明:一方面,如果将元素1单独拿出来划分成1个集合,那么方法数是S(p-1,k-1);另一方面,如果元素1所在的集合不止一个元素,那么可以先将剩下的p-1个元素划分好了以后再选一个集合把1放进去,方法数是k*S(p-1,k);有加法原理得证。第二类Stirling数有公式:S(p,k) = (Σ(-1)^t * C(k,t) * (k-t)^p) / k!,不过看上去好像意义不大,记住一开始的递推式就好了。

Bell数B_p表示将p个元素的集合划分成一些不可辨别的非空集合的方法数,由第二类Stirling数的定义,显然有:B_p = S(p,0) + S(p,1) + …… + S(p,p)。还有一个递推式:B_p = ΣC(p-1,i)B_i(0<=i<p),可以组合证明。

第一类Stirling数s(p,k)满足的递推关系是:s(p,k) =(p-1)*s(p-1,k) + s(p-1,k-1);初始条件与S(p,k)一样是s(p,0)=0(p≥1),s(p,p)=1。它表示n个物体排成k个非空的循环排列(就是圆圈)的方法数。

第一类和第二类Stirling数事实上的意义比上面讲到的要丰富,它们是P(n,p)与n^p这两组多项式向量空间的基互相表示的系数。哦……这个不理解没关系的。

将整数n写成一个无序的正整数的和式的方法数就是分拆数p_n。p_n相当于方程n*x_n + … + 2*x_2 + 1*x_1 = n的整数解的个数。书中没有给出递推的或者直接计算的式子,只给出了一个生成函数,实际计算的时候加一维用DP求解就好了。

用n个一般位置上的(k-1)维超平面分割k-维空间所成的区域数是h(n,k)=C(n,0)+C(n,1)+…+C(n,k)。一般的推导较繁。

格路径,就是在平面直角坐标系的整点中从一个点到一个点的最短路径。从(0,0)到(p,q)的格路径数是(p+q,p),因为一共要走p+q步,选择其中p步向上走。下对角线格路径就是从源点到目标点的对角线的上方(不包括线上的点)不可到达时的格路径数。从(0,0)到(n,n)的格路径数就是Catalan数C_n,根据那个+1、-1部分和很容易证明。一般地,从(0,0)到(p,q)的下对角线格路径条数是R(p,q)=C(p+q,q)*(p-q+1)/(p+1)。如果允许对角步进,计算会有点麻烦,给一个公式好了:从(0,0)到(p,q)经过r个对角步进的格路径数K(p,q:rD)=C(p+q-r,(p-r,q-r,r))(这是多项式系数);如果下对角线,更加麻烦,R(p,q)=K(p,q)*(q-p+1)/(q-r+1)。

大Schroder数R_n就是上面讨论过的R(n,n),所以R_n=。小Schroder数s_n指给n个数“加括号”的方法,“加括号”的规则是:一个数不能加括号,可以给任意多个数的序列加上一个括号并在之后把它当作一个数处理,整个序列最外面的括号可以省略。有结论R_n=2*s_(n+1),用生成函数的方法证明。

上面这些东西重要的是掌握思想,特别是组合证明,至于式子的记忆还是次要的。

3 Comments

  1. deslors wrote:

    你涉及的范围真广~现在又跑到yo2来啦~嗬嗬~支持~

    Saturday, May 12, 2007 at 18:10 | Permalink
  2. ?? wrote:

    回信收到了吗?
    你这个数学水平,不用读本科了。

    Sunday, May 13, 2007 at 19:56 | Permalink
  3. traveler wrote:

    本章介绍了很多著名的数列,我认为这是本书最激动人心的一章。

    呵呵 有同感
    这章是应用前面组合理论的辉煌篇章

    Thursday, May 31, 2007 at 23:56 | Permalink

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*