发布时间 : 星期一 文章组合数学中常见的计数方法更新完毕开始阅读
沈阳理工大学学士学位论文
图4.1两条长为4的Dyck格路
图4.2 五条长为6的Dyck格路
我们把长度为2n的Dyck格路的集合记做Cn。Cn是由Catalan数来计数的,Catalan数的初值是1,1,2,5,14,42,132,429,1430,4862,…,并且Catalan数C0,C1…满足西面的递归关系式:
命题4.1.2 Cn??CiCn-1-i,其中C0?1
i?0n-1 命题4.1.3 C?x??1?xC2?x??1-1-4x 2x命题4.1.4 Cn?1?2n??? ??n?1?n?4.1.3 Fine数的基本性质和概念
本文主要研究Fine数的相关知识,在前面我们提到了Catalan数,对Catalan数有了一定的了解后,下面我们就来讨论Fine数的定义及其相关的性质。
定义4.15 在Z2中,一条2n长的Fine格路是一条不包含hill的2n长的Dyck格路。一个hill是由(1,1)方向的上升步和(1,-1)方向的下降步形成的高度为1的峰。从(0,0)出发到(2n,0)的Fine格路记做n-Fine格路。
为了更好地理解定义,我们画出n=2, n=3和n=4时的所有的Fine格路
29
沈阳理工大学学士学位论文
图4.3一条长度为4的Fine格路
4.4两条长度为6的Fine格路
4.5 五条长度为8的Fine格路
在这篇文章中,我们用u来表示上升步,用d来表示下降步。在一条格路中一对连续的ud步叫做峰,一个峰中所包含的d步叫做fall。格点指的是每一步的两个端点,我们把峰所包含的ud步中所有格点的纵坐标的最大值叫做峰的高度,一条格路的高度是所有峰的高度的最大值。
我们把长度为2n的Fine格路的集合记做Γn。Γn是由Fine数Fn来计数,Fine数的初值是1,0,1,2,6,18,57,186,622,2120,…,Fine数{Fn}n?0的发生函数记做F(x),即
F(x)??Fnxn。Fine数的发生函数和Catalan数的发生函数之间满足如下关系:
n?0?命题4.16 F(x)?1?x(C(x)-1)F(x)?11-1-4x
x3-1-4x命题4.17 Fine数和Catalan数满足关系式:Cn?2Fn?Fn-1 4.1.4 Fine数的几个重要的恒等式
根据Fine数和Catalan数之间的关系,我们得到Fine数的若干性质如下: 性质1 2(n+1)Fn=(7n-5)Fn-1+2(2n-1)Fn-2
30
沈阳理工大学学士学位论文
性质2 Fn?1?2n-2?2?2n-4?3?2n-6???????????,其中n?2 ??????n-1?n?n-2?n?n-3?n?1?11?n-21C-C?C-??(-1)Cnn-1n-22? 2n-22?222??性质3 Fn?性质4
Fn4~ Cn94.1.5 Fine数的组合意义
Fine数有很多组合解释,它和一些重要的组合对象,比如它和Dyck格路,Young表,分拆,平面树,Motzkin格路有比较紧密的联系。Deutsch和Shapiro在文献[17]中给出Fine数的一些组合解释,我们首先给出一个重要引理,下面的很多证明都是以此引理为基础。 引理1 如果Dyck格路中第一峰的高度是k,那么它的发生函数是xkCk(x)。
性质2 从左向右看,满足第一个峰的高度是偶数的长度为2n的Dyck的格路计数是Fn。
k性质3 具有型(n,n)且每列不出现形式的标准Young表的计数为Fn。
k?1性质4 [n]的第一个块的长度是偶数的不变划分的计数是Fn。 性质 5 [n]的不包含可视的单点的不变划分的计数是Fn。
性质 6 n个结点的有序树中第一层上不包含叶子的有序树的计数是Fn-1。 性质 7 长度为n的2-Motzkin格路中x轴不包含水平步的计数是Fn。
4.2 Pólya计数
4.2.1 Pólya计数产生的历史
G·Pólya是美籍匈牙利数学家、教育家。他在数学的广泛领域里都有许多发现,又热心于教育,1980年被邀请担任第四次国际数学教育会议的名誉主席。他一生中发表过二百多篇论文和许多专著,其作品清晰优美,方法灵巧独特。被人们誉为“Pólya的风格”、 “Pólya的方法”……。
Pólya早在1937年就对树的计数和化合物的同分异构体的枚举问题进行研究,他巧妙地把发生函数、置换群和权函数三者结合起来,设计出一个枚举多项式,揭示了构形计数级数与构形群的循环指标和图形计数级数的关系,解决了许多计数问题。人们把这一方法叫做Pólya计数定理。之后, Pólya基本定理又有许多种推广形式,都有极为广泛的实际应用。
31
沈阳理工大学学士学位论文
4.2.2预备知识
我们参照Pólya原来的说法,把给定的两个有限集合D和R分别叫位置集和图形集。如d?D就说有位置d,称r?R是图形r。D到R的一个映射f叫做一个构形,由所有定义在D上取值于R中的构形作为一个集合叫构形集,并记作RD。若D是n元集,R是m元集,则有D=n,R=m,RD=mn。
把作用在n元集D上的一个n次置换群G叫做D的一个构形群。G中每一个置换g均可表为没有共同元的循环置换之积,若其中有b1个长度为1的循环,b2长度为2的循环等等,且b1?2b2?3b3???n,则说g是{b1,b2,b3?}型的,并令
PG(x1,x2,?xn)?1Gg?G?xb1xbnb2x2?xn
称为置换群G的循环指标。
我们说两个构形等价f1~f2,当且仅当存在一g?G,是对每个d?D有
f1(d)?f2(g(d))。又把构形集的每一等价类叫做一个构形格式。
给R的每个图形r指定一个权w,取值为k维空间的非负整数,记作
w(r)?(w1(r),w2(r),?,w(r)
同样地指定一个构形f的权为
w2(f(d))W(f)??x1w1(f(d))x2?xkwk(f(d))
d?D其中x1,x2,?,xk为形式参量。
若R中权等于(i1,i2,?,ik)的图形有hi1i2?ik个,令
iki1i2 h(x1,x2,?,xk)??hi1i2?ikx1x2?xk称为图形计数级数。
iki1i2若RD中权等于x1的构形格式有Hi1i2?ik个,令 x2?xki1i2ik H(x1,x2,?,xk)??Hi1i1?ikx1x2?xk称为构形计数级数。
令
O(x)??yg(x)?y,x,y?D,g?G?
称为x的稳定核。易知G(x)是G的一个子群。
引理4.2.1 G?O(x)?G(x)
引理4.2.2 一个构形格式F中的诸构形有相同的权。
引理4.2.3(Bursibe定理) 若λ1(g)是置换g?G的1-循环的个数,也就是n元素D中
32