（计算数学专业论文）计数组合学中若干问题的研究.pdf

摘要 计数组合学是组合数学的重要研究方向之一，主要研究有限集合上的组合结构在 给定条件下的计数问题本文的主要工作包括以下几个方面： 在第一章，定义了两族广义p - s t i r l i n g 数，将二项式系数和经典s t i r l i n g 数统一起 来。讨论广义p - s t i r l i n g 数的组合意义，将一维的有限集合分拆和排列推广到p 维情 形；得到p - s t i f l i n g 数的封闭形式的差分恒等式；并研究p - s t i r l i n g 矩阵的行列式性质。 在第二章，研究一种简单而又重要的组合结构d y c k 路，这是近几年国内外 的组合学者研究的一个热点课题。首先刻画了波谷严格递增的d y c k 路与整数有序分 拆之间的关系；然后利用双射、生成树以及r i o r d a n 阵的方法来对集合口。的一些子集 进行计数，得到一些以经典的序列如c a t a l a n 数、n a r a y a n a 数、m o t z k i n 数、f i b o n a c c i 数、s c h r 6 d e r 数以及第一类无符号s t i r l i n g 数来计数的组合结构。特别地，给出两个新 的c a t a l a n 结构，它们并没有出现在s t a n l e y 所给的关于c a t a l a n 结构的列表中，最后 定义一种新的有禁排列模式，并讨论关联d y c k 路与这种有禁排列之间的一些问题。 在第三章，研究广义f i b o n a c c i 多项式的代数性质，包括广义f i b o n a c c i 多项式的 系数组成的矩阵的性质；广义f i b o n a c c i 多项式系数的组合意义；以及广义f i b o n a c c i 多项式的普通型卷积求和公式。 在第四章，基于m a c m a h o n 分拆技巧，将s e l l e r s 关于整数分拆的一个定理推广到 更一般的情形( 即将向量限制形式推广到矩阵限制形式) ，并给出了大量有益的应用， 其中涉及到许多经典的序列如b e l l 数、f i b o n a c c i 数、l u c a s 数和p e l l 数等。利用二叉表 示之问的变换来研究将整数表示成不同f i b o n a c c i 数之和的表示法的公式n ( n ) ， 得到了r ( n ) 的新的递推关系式，通过这些关系，很容易计算r ( n ) 在很大时的值 关键词：p s t i r l i n g 数、k 一矩阵分拆、矩阵排列、差分恒等式、行列式、p f 性 质、d y c k 路、c a t a l a n 数、生成树、r i o r d a n 阵、s c h r 6 d e r 数、广义f i b o n a c c i 多项 式、l u c a s 数、m a c m a h o n 分拆技巧、z e c k e n d o r f 表示、c a u c h y 留数定理 a b s t r a c t e n u m e r a t i v ec o m b i n a t o r i c si so n eo fv i t a l l yi m p o r t a n tr e s e a r c hb r a n c h e si nc o m h i n a - t o r i c s ，m a i n l yi n v e s t i g a t e sc o u n t i n gp r o b l e m so fc o m b i n a t o r i a ls e t t i n g so nf i n i t es e tu n d e r g i v e nc o n d i t i o n s t h em a i nc o n t e n t so ft h i sd i s c o u r s ea r el i s t e da 8f o l l o w s ： i nt h ef i r s tc h a p t e r ，w ed e f i n et w of a m i l i e so f g e n e r a l i z e d p - s t i r l i n gn u m b e r sw h i c hu n i f i e s t h eb i n o m i a le o e m c i e n t sa n dt h ec l a s s i c a ls t i r l i n gn u m b e r sw ed i s c u s st h ec o m b i n a t o r i a l i n t e r p r e t a t i o no fp s t i r l i n gn u m b e r sa n de x t e n dt h eo n e - d i m e n s i o n a lf i n i t es e tp a r t i t i o n sa n d p e r m u t a t i o n st og e n e r a lp - d i m e n s i o n a lc a s e s ；o b t a i ns e v e r a ld i f f e r e n c ei d e n t i t i e so fc l o s e df o r m o fp s t i r l i n gn u m b e r sa n di n v e s t i g a t et h ed e t e r m i n a n t a lp r o p e r t i e so fp s t i r l i n gm a t r i c e s 。 i nt h es e c o n dc h a p t e r ，w ew o r ko v e ras i m p l eb u ti m p o r t a n tc o m b i n a t o r i a ls t r u c t u r e d y c kp a t h s ，w h i c hi sah o tr e s e a r c ht o p i ci nr e c e n td e c a d e s f i r s t jw ed e s c r i b et h ec o n n e c t i o n s b e t w e e nt h es e to fd y c kp a t h sw i t hs t r i c t l yi n c r e a s i n gv a l l e y sa n dt h es e to fc o m p o s i t i o n s o fa ni n t e g e r ；t h e nb i j e c t i o n sa n dt h em e t h o d so fg e n e r a t i n gt r e e st o g e t h e rw i t ht h o s eo f r i o r d a na r r a y sa r eu s e dt oe n u m e r a t et h e s es u b s e t so f ，r e s u l t i n gi ns u c hw e l l - k n o w n s e q u e n c e sa st h ec a t a l a nn o s ，n a r a y a n an o s ，m o t z k i nn o s ，f i b o n a c c in o s ，s c h r s d e rn o s ， a n dt h eu n s i g n e ds t i r l i n gn u m b e r so ft h ef i r s tk i n d i np a r t i c u l a r wg i v e st w oc o n f i g u r a t i o n s t h a ta p p a r e n t l yd on o ta p p e a ri ns t a n l e y sw e l l - k n o w nl i s to fc a t a l a ns t r u c t u r e sf i n a l l y ，w e d e f i n ean e wk h l do fr e s t r i c t e dp e r m u t a t i o np a t t e r na n dd i s c u s st h ec o n n e c t i o nb e t w e e nt h e s e to fa s s o c i a t e dd y c kp a t h sa n dt h es e to fr e s t r i c t e dp e r m u t a t i o n s i nt h et h i r dc h a p t e r ，w es t u d yt h ea l g e b r a i cp r o p e r t i e so fg e n e r a l i z e df i b o n a c c ip o l y n o m i a l s li n c l u d i n gt h ep r o p e r t i e so fm a t r i c e sc o m p o s e do ft h e i rc o e f f i c i e n t s ，t h ec o m b i n a t o r i a l m e a n i n g so ft h e i rc o e f f i c i e n t sa n dt h ec o n v o l u t i o ns u m m a t i o nf o r m u l a so fg e n e r a l i z e df i - b o n a c c ip o l y n o m i a l so ft h eg e n e r a lt y p e i nt h el a s tc h a p t e r b a s e do nt h et e c h n i q u eo fm a c m a h o n sp a r t i t i o n sa n a l y s i s ，w eg e n e r a l i z es e l l e r s t h e o r e mo np a r t i t i o n st oam o r eg e n e r a lc a s ea n dg i v es e v e r a la p p l i c a t i o n s ， i n v o l v i n gm a n yc l a s s i c a ls e q u n e n c e ss u c ha sb e l ln u m b e r s ，f i b o n a c c in u m b e r s ，l u e a sb u m h e r s ，a n dp e l ln u m b e r s ；w ea l s oi n v e s t i g a t et h ef o r m u l a so fr ( n ) o ft h en u m b e ro fp a r t i t i o n s o fa ni n t e g e rni n t od i s t i n c tf i b o n a c e in u m b e r sb yat r a n s f o r m a t i o no nt h eb i n a r yr e p r e s e n t a t i o ua n dp r e s e n ts e v e r a lr e e u r s i v ef o r m u l e si nd i f f e r e n tf o r m s ，b yw h i c hw ec a ne a s i l y o b t a i nr f 1f o ra n yl a r g en u m b e rn k e y w o r d s ：p s t i r l i n gn u m b e r s ，k - m a t r i xp a r t i t i o n ，k - m a t r i xp e r m u t a t i o n d i f f e r e n c e i d e n t i t i e s ，d e t e r m i n a n t ，p fp r o p e r t 弘d y c kp a t h s ，c a t a l a nn u m b e r s ，g e n e r a t i n gt r e e ，r i o r d a na r r a y , s c h r s d e rn u m b e r s ，g e n e r a l i z e df i b o n a c c ip o l y n o m i a l ，l u c a sn u m b e r ，m a c m a h o n 8 p a r t i t i o nm e t h o d ，z e c k e n d o r fr e p r e s e n t a t i o n lc a u c h yr e s i d u et h e o r e m 独创性说明 作者签名 经塑! 盘：日期：坦、左，蛰) 媲储镇烊黼丽 一一一一一一 榔姗州掀一椭 一一一一一 大连理工大学学位论文版权使用授权书 保密口，在年解密后适 本学位论文属于 ( 请在以上方框内打”，) 作者签名 导师签名 垒! 塑丝! 垂! 逊 易以年五月丝日 骷雌刚躺姆 | ；婵黼一一一脚一一懈一阱蹁 撒稽断 一一一 茹 0 前言 o 1 引言 计数组合学是组合数学的重要研究方向之一，主要研究有限集合上的组合结构在 给定条件下的计数问题。有限集合上的组合结构是非常丰富的，基本的结构有；圈结 构，如置换群上的排列，有禁排列等；树结构，如格路、树、多边形的三角剖分等；序 结构，如前序、偏序关系、相似关系等研究组合结构自然就产生了几个有意义的问 题t ( 1 ) n 元集合上的某种组合结构的分类，也就是结构的计数问题； ( 2 ) 因在研究问题( 1 ) 时会产生组合序列，那么反过来给定组合序列，能否找到与 之对应的组合结构( 这种结构可能不唯一) ； ( 3 ) 在研究问题( 1 ) 时，由于可能采用了不同的研究方法而得到组合恒等式，那么 反过来已知了组合恒等式，能否找到它的组合解释( 一般的并不唯一) 。 s t a n l e y 在他的著作e n u m e r a t i v ec o m b i n a t o r i c s 中深刻地阐述了这种思想。在 这种思想的指导下本文拟在下列四个方面作些探讨。 ( 一) n 元集合比如m = 1 ，2 ，一，n 的分拆和排列是组合数学中最为熟知的基本 研究对象，集合的分拆和排列分别是由经典的第二类s t i r l i n g 数和无符号第一类s t i r l i n g 数来计数的8 t i r l i n g 数一直是研究者非常感兴趣的对象，因为它在数论、概率论、组 合论等方面有着重要的应用并且经常出现在有禁分拆、有禁排列、以及格路的计数 中。从不同的角度出发，不同的学者对经典的s t i r l i u g 数进行了各种推广，r i o r d a n 8 4 1 研究了非中心s t i r l i n g 数，c a r l i t z 2 0 ，2 1 研究了加权s t i f l i n g 数和退化s t i r l i n g 数， h o w a r d l 5 7 研究了加权的退化s t i f l i n g 数，b r o d e r 研究了r - s t i f l i n g 数，c h a r m a m b i d e s 和k o u t r a ，s 2 4 】、g o u l d 和h o p p e r 5 1 】、t s y l o v a 1 0 6 等研究了s t i r l i n g 数的其他不同形 式的推广。在1 9 9 8 年徐利治先生和薛昭雄先生 5 8 】对这些不同形式的推广作了一个统 大连理工大学博士学位论文：计数组合学中若千问题的研究 一的处理，也就是：定义s t i r l i n g 型数偶 s ( n ，；n ，卢，r ) ，s ( n ，女；口，q 一r ) ) 如下， n 0 i ) 。= 。s ( n ，；。，卢，r ) r f 卢) ， 女= 0 n ( t l z ) 。= 芝，s ( 竹，七；卢，。，一r ) o + r i n ) ， k = o 其中对n i ，( z i q ) 。= 9 0 一n )扛一几+ 口) 以及( z l 口) o = 1 。在s t i r l i n g 型数偶中对 参数( n ，口，r ) 取不同的值时，就可以得到前面提到的各种不同的推广形式。这些推广 形式之所以能统一在同一个框架之内，是因为这些推广有着同一共性，即它们都满足 三项线性递归关系式， 占( 札+ 1 ，南；d ，p ，r ) = ( 七口一n 口+ r ) s ( 礼，七；口，卢，r ) + s ( n ，七一1 ；，卢，7 ) 并且这种广义s t i r l i n g 型数偶有明显的实际应用。是表述离散时间的“纯生育过程”的 最适合的工具。此外，e h r e n b o r g 4 2 】研究了q - s t i f l i n g 数组成的矩阵的性质；r e m m e l 8 3 1 研究了推广的s t i r l i n g 数和它们的( p ，口) 模拟在r o o k 理论中的应用；l a b e o e 6 8 1 等用 有禁排列来给出了s t i f l i n g 数的酽模拟的组合解释；w a c h s 和w h i t e 1 0 7 】通过集合分 拆的某些统计量来研究s t i f l i n g 数的，g ) 一模拟。因此，从组合的意义上来对经典的 s t i r l i n g 数进行推广和研究这种推广了的s t i r l i n g 数的其他性质将是十分有意义的。 ( 二) 近二三十年来，国际国内研究者广泛地研究了格路、有禁分拆、有禁排列等 课题，取得了丰富地成果。即将在2 0 0 6 年数学家大会上作一小时报告的s t a n l e y 在他的 网页中收集了一百多个与d y c k 路等价的组合对象，并称它们为c a t a l a n 族或c a t a l a n 结构，因为它们都是以c a t a l a n 数来计数的。最近还有新的等价结构不断出现。d e u t s c h 在f 3 6 】中讨论了研究d y c k 路的基本方法，并集中研究了不同统计量的d y c k 路的计 数。c o k e r 3 2 用符号法和l a g r a n g e 反演来研究一类格路。d e n i s e 和s i m i o n 3 5 1 研究 了d y c k 路中的两个组合统计量t 赋权金字塔和内对数。d o , l i d 等3 8 1 研究了r n a 第 二结构的计数。k r a t t e n t h a l e r 6 6 】研究了d y c k 路和有禁排列w e s t 1 0 9 ，1 0 8 研究了 生成树和有禁排列，b a r c u c c i 1 3 等人利用生成树的思想发展成了一个对组合对象计 数的行之有效的方法，称为e c o 方法，南开大学陈永川和他的合作者皿6 ，2 8 ，2 7 ，2 9 在格路的计数，恒等式的组合证明，有禁排列等方面作出了很好的成果，他们的思想 方法被国内外同行高度评价为原创性的。中国台湾的游森棚、刘树忠和叶永南f 4 4 1 对 格路的计数，对格路的统计量的研究，组合证明恒等式等方面作出来很好的结果。对 d y c k 路的研究之所以能够引起众多学者的关注，主要因为它是研究其他问题，比如多 边形的剖分、不变分拆、整数分拆等的一个有效的办法。因此对d y c k 路本身结构的研 究，就是显得很重要。作者在硕士阶段研究了格路、有禁分拆、有禁排列等课题的， 在本文的第二章是原来课题的迸一步研究的结果 2 第0 章前言 ( 三) 三项递归关系式最+ l ( ) = n ( 。) r ( 。) + b ( 口) f 托一d x ) 在满足某些条件下所确 立的多项式r ( 。) 被称为广义f i b o n a c c i 多项式，它一直吸引着众多研究者对这个多项 式投入了不同的观点。比如在1 9 9 1 年，f e r r i 、f a c c i o 和d a m i c o 4 6 介绍并研究了两 类与之相关的数值三角：d f f 三角和d f f z 三角；后来，t r z a s k a 1 0 5 】也考虑了d f f 三角的其他性质；j e a n n i n 5 9 1 在1 9 9 4 年推广了上面两个三角。f e r r i 等【4 7 】在1 9 9 2 年 研究了r ( z ) 在电子阶梯网络中的应用；最近王毅和贺明峰 5 4 l 等研究了这类多项式 的零点。张文鹏教授和他的合作者【1 1 4 ，1 1 5 1 最近对广义f i b o n a c c i 数和多项式的卷积 公式作了一系列的研究。而本文将重点着眼在r ( z ) 的系数上，研究了这些系数所组 成的矩阵和它们的逆，并且给出了这些系数的组合解释；以及多元广义f i b o n a c c i 多项 式的普通型卷积求和公式。 ( 四) 整数的分拆是一个古老的问题，迄今为止仍然是计数组合学中一个生机勃 勃的研究领域。某些特殊的分拆问题甚至可以追溯到中世纪，然而最早作出深刻研究 的当数1 8 世纪的e u l e r ，他证明了许多漂亮而又重要的分拆定理，从而奠定了整数分 拆理论的基础。之后，许多数学家如c a y l e y 、g a u s s 、j a c o b i 、l a g r u n g e 、s c h u r s y l v e s t e r 、l e g e n d r e 、h a r d y 、p m d e m a c h e r 、l i t t l e w o o d 以及r a m a a u j a n 等都对分 拆理论的发展作出了重要的贡献。当今，a n d r e w s 1 1 是这一理论的集大成者和进一步 发展的领航人。 所谓整数分拆指的是将正整数n 写成n = p l + p 2 + p 3 + p 4 + 的形式，其中正整 数p l p 2 ) 3 p 4 0 。设d ( n ) 表示n 的所有奇数分拆的个数，_ d ( n ) 表示n 的不同分部量的所有分拆的个数e t d e r 定理指出：0 ( n ) = d ( n ) 。迄今为止，e u l e r 定理已有五种不同的证明，对e u l e r 定理也有不同形式的推广。 在2 0 0 1 年，s a n t o s 8 8 利用双射证明了o ( ) 也等于将n 分拆成如下形式的分拆个 数，即佗= p 1 + p 2 + p 3 + m + 蒂争足p t p 2 p 3 p 4 - 0 且p 1 2 船+ p 3 + p 4 + t 。 随后，利用m a c m a h o n 分拆分析技巧 7 3 】，s e l l e r s 8 9 ，9 0 】推广了s a n t o s 的结果。最 近，c h e n 2 5 改进并精细了s e l l e r s 的结果。本文第四章的主要工作将s e l l e r s 的结果推 广到更一般的情形，并给出大量有意义的应用。 0 2 论文内容概述 在第一章，定义了两族广义p - s t i r l i n g 数，将二项式系数和经典s t i r l i n g 数统一起 来。讨论广义p - s t i r l i a g 数的组合意义，将一维的有限集合分拆和排列推广到p - 维情 形；利用容斥原理、c a u c h y 留数定理和算子的方法，得到p - s t i h i n g 数的封闭形式的差 分恒等式并研究p - s t i r l i n g 矩阵的行列式性质。这一章主要是文章 9 5 ，9 6 1 中的结果。 3 大连理工大学博士学位论文，计数组合学中若干问题的研究 在第二章，研究一种简单而又重要的组合结构一一d y e & 路，这是近几年国内外的 组合学者研究的一个热点课题。首先刻画了波谷严格递增的d y e & 路与整数有序分拆 之间的关系；然后利用双射、生成树以及r i o r d a n 阵的方法来对集合研。的一些子集进 行计数，得到了一些以经典的序列如c a t a l a n 数、n a r a y a n a 数、m o t z k i n 数、f i b o n a c e i 数、s e h r 6 d e r 数以及第一类无符号s t i r l i n g 数来计数的组合结构特别地，给出两个 新的c a t a l a n 结构，它们并没有明显地出现在s t a n l e y 所给的关于c a t a l a n 结构的列表 中最后定义了一种新的有禁排列模式，并讨论了关联d y e k 路与这种有禁排列之间 的一些问题。这一章主要是文章 9 8 1 中的内容 在第三章，研究广义f i b o u a e e i 多项式的代数性质，包括广义f i b o n e u c c i 多项式的 系数组成的矩阵的性质；广义f i b o n a e e i 多项式系数的组合意义；利用生成函数技巧和 偏导数，得到关于广义f i b o n a e e i 多项式的普通型卷积求和公式这一章主要是文章 f 99 和 1 1 3 】中部分结果的内容。 在第四章，基于m a e m a h o n 分拆技巧，将s e l l e r s 关于整数分拆的一个定理推广到 更一般的情形( 即将向量限制形式推广到矩阵限制形式) ，并给出了大量有益的应用， 其中涉及到许多经典的序列如b e l l 数、f i b o n a c e i 数、l u c a s 数和p e l l 数等利用二叉表 示之间的变换来研究将整数表示成不同f i b o n a c c i 数之和的表示法的公式r ( n ) ，得 到了n ( n ) 的新的递推关系式，通过这些关系，很容易计算r ( ) 在很大时的值 这一章主要是文章【1 0 0 ，1 0 1 】中的内容。 4 1 两类广义s t i r l i n g 数 设n ：( 。o ，n ，n ) 为一无限实数序列第一类和第二类广义s t i r l i n g 数由下 面变换定义t n ( z = o a o ) ( x a 1 ) 忙一a - 1 ) = s 。( n ，) ， 且( z = 1 ， k = o n 矿= ( n ，) 扛一o o ) 扛一a 1 ) k = o 且s a ( n ，k ) 的列生成函数为 薹s n ( 嘶k 矿丽高面雨 s 。( 凡) 和& ( mk ) 的许多基本性质在文献1 3 3 ，1 0 4 3 中已经谈及。但两个特别的情形没 有具体涉及，即对任何整数p 0 ，当o n = 旷或o n = ( “驾- 1 ) 时这两个重要情形 s l ( n ，p ) 扩 k = i s l ( n ，p ) 扩 = ( z 一矿) t = 0 刊( 酊托，) 。1 = 嚣” 咖矽一( 萤心，) 我们称黾( n ，p ) ，s i ( n ，p ) 为j 一型0 = 1 ) ，1 1 - 型0 = 2 ) 第一类、! $ i - - - 类p - s t i f l i n g 数。在这一章，我们将讨论p - s t i r l i n g 数的组合解释，差分恒等式，矩降陛质，以及p f 性质等。 5 曲 z k m 。 = 以毗 一z p 七n 靶 。 大连理工大学博士学位论文：计数组合学中若干问题的研究 1 1 p - s | l ；i r i n g 数的组合解释及差分恒等式 1 1 1 p s t ：i r l i n g 数的组合解释 设州表示集合 l ，2 ，n ) ，s 。是m 上排列的集合。设吖( n ，p ) = ( 尬j ) 为 p n 矩阵，其中对i 陋 有慨j = j h 。对任何m ，定义两个p k 矩阵 b ( n ；，p ) = ( b o ) ，c | ( n ；，p ) = ( g ，) ，其中嘞是【n j 的一个子集、c 0 足某个”s 。 的圈，并分别满足下面的条件： 1 对每个i 洳】，m 是b 4 ( j ) 的不交并，且1 m i n ( b 。1 ) m i n ( b 。2 ) m i n ( 最女) n 。 2 对每个i 陋1 ，不交积n 名l c 匆是s 。中的排列，且1 m i n ( g 1 ) m i n ( o ：2 ) r a i n ( q ) 曼n 。 其中m i n ( b i j ) 、r a i n ( c 0 ) 分别是和g ，中最小的数，且处在最前位置。 定义1 1m ( n ，p ) 的一矩阵分拆指的是书m ( n ，p ) 的每一行作为集合分拆成个不交 块，且作为矩阵b 咖；，p ) = ( b “) 每一行的元素并满足对任何j 嘲，m i n ( b 】，) = m i n ( b 卸) 一= m i n ( ) 。m ( n ，p ) 的- 矩阵分拆称为强的，如果对任何h “1 ，t 2 ，“) ，存在子集序列b i j ，日。，嘞，使得这个子集序列的每个子集都包 含元素h ，其中如0 ) 表示m i n ( b l j ) 以及1 j l j 2 如曼七。 定义12 ：m ( n ，p ) 的一矩阵排列指的是将m ( n ，的每一行作为集合进行排列，这个排 列有个不交圈，且作为矩阵g ( n ；，p ) = ( g j ) 每一行的元素并满足对任何j ， m i n ( c 1 j ) = m i n ( b ) 一= r a i n ( c 南) 。m ( n ，p ) 的女矩阵排列称为强的，如果对任 何h ( n 一 t l ，t 2 ，“) ，其中0 ( j ) 表示m i n ( c 1 ) ，在g ( n ；，p ) 的第e 行中， 处在h 的前面并比 小的数的个数u ， ) ，对1 i 曼p 形成一严格递增的数列，即 l ( ) 2 ( h ) + 嘶( ) 。 为了进一步说明定义1 1 和定义1 2 ，我们考虑m ( 6 ，2 ) ， m ( 6 ，。) = ( ；i 。5 。6 ) ， 56 ( 56 ) ( 56 ) ( 5 ) 2 6 5 ) 234 ) 5 6 ( 26 )( 5 ) ( 243 ) ( 56 ) 其中b 1 ( 6 ；3 ，2 ) 、岛( 6 ；3 ，2 ) 和c l ( 6 ；3 ，2 ) 、q ( 6 ；3 ，2 ) 分别为m ( 6 ，2 ) 的3 矩阵分拆和 3 一矩阵排列，但只有b 2 ( 6 ；3 ，2 ) 和q ( 6 ；3 ，2 ) 是强的。 6 、二 q 却 坞u h ”f； ， = = 2 2 3 3 6 6 岛 国 、 ) 4 口d刁嘲功n 姐租q，、 = j | 2 2 3 3 6 6 b c 第2 章两类广义s t i r l i n g 数 当然由定义1 1 和定义1 2 ，当 p 、n 时，肘( n ，p ) 没有强的矩阵分拆 或者强的k 一矩阵排列，为了避免这些退化情形，我们假设n k p ，并在适当的时 候设n ：= n + p 一1 ， ：= + p 一1 首先我们有下面的命题。 定理1 1 ：设正整数n ，p 1 ，有 ( 1 ) m ( n ，p ) 的k 一矩阵分拆的个数为s l ( n ，k ，p ) 。 ( 2 ) m ( n ，p ) 的一矩阵排列的个数为l s l ( n ，p ) _ 。 ( 3 ) i ( n + p 一1 ，p ) 的+ p1 一矩阵分拆的个数为岛( n ，p ) 。 ( 4 ) m m + p 一1 ，p ) 的+ p 一1 矩阵排列的个数为；s 2 ( n ，p ) 。 证明：设( n ，p ) 和岛( n ，k ，p ) ( i = 1 ，2 ) 为所要求的数。由它们的定义，我们可以导 出它们分别满足下面的递推关系式。 + 1 ，p ) = l ( 札+ 1 ，p ) = 岛( n + 1 ，女，p ) = 妒茸1 ( n ，p ) + 5 i ( n ，一1 ，p ) 护l ( n ，p ) ( ；。) ( n ，惫，p ) + 岛( n ，岛一1 ，p ) 2 ( n + 1 ，自，p ) = ( “+ p 。1 ) 2 ( n ，p ) + 2 ( n ，一1 ，p ) ， 且对i = l ，2 ，有初值条件 眦加 ；喜墨雾列“汜如，= ；喜型箩0 我们仅具体地考虑第三个关系式，其他的可同理得证。一方面，给定m ( n + p 一1 ，p ) 的一个强( + p 一1 ) 一矩阵分拆口m + p 一1 ；k + p 一1 ，p ) ，将符号m + p ) 从上到下，严 格地从左到右地插入到日+ p l ；+ p 一1 ，p ) 的每一行中，产生盯m + p , p ) 的一些 ( + p 一1 ) 一矩阵分拆亩m + p ；+ p 1 , p ) ，且这样的方式有( + ：。) 种。因此共可产 生( “p 。- - i ) 岛( n 、，p ) 个m 坼+ p ，p ) 的强( + p 一1 ) t i g g 分析，且对j 啤+ p 一1 1 满足 m i n ( b l j l n + 1 。 另一方面，给定m ( n + p 一1 ，p ) 的一个强( k + p 2 ) 一矩阵分拆b ( n + p 一1 ；k + p 一2 ，p ) ， 可以将它扩展为m m + p ，p ) 的强( t + p 一1 ) 一矩阵分拆b ( n + p ；+ p 一1 ，p ) = ( 捌，) 满 足m i n ( 咧，) = n + 1 ，其中i ，j = + p 一1 定义 耻 并， 若j i k + p 一2 若j = k + p 一1 从而在这种情形下有9 2 ( n ，k 一1 ，p ) 个m 扣+ p l p ) 的强恤+ p 一1 ) 矩阵分拆。注意到 是( n ，k , p ) 也满足同样的递推关系式和同样的初值条件，故它们相等。 7 大连理工大学博士学位论文：计数组合学中若干问题的研究 定理12 ：设v = ( ，。) 为一p n 的整数矩阵，满足0 u ，。8 1p 加】，5 叫) 并 恰有个零列，且其他列的元素皆大于零，则这样妁整数矩阵的个数为1 s 1 协，b ，p ) 1 证明：给定m ( n ，p ) 的一个一矩阵排列e ( n ；k ，p ) ，设t j = m i n ( c u ) ，( j ) ，我们如 下定义一个p n 矩阵v = ( ，。) ， 吲岫= ，萋5 呻e n ”- 、嚣m ， 其中嘶( s ) 是在g ( n 沌p ) 的第r 行中，处在s 之前且比s 小的数的个数，从而脚( s ) s 注意到t 1 = 1 ，故对8 嘲一 t l ，“) 有u ，( 8 ) 1 反过来，给定这样的一个矩阵，由于它的每一行可以唯一作为s 。中某个排列的 逆序数表，从而可以唯一的得到这个排列和它的圈，进而可以唯一的得到m ( n ，p ) 的 k 矩阵排列因此，利用定理1 1 的第二个断言，就可完成证明 口 定理1 3 ：设v = ( 。) 为一p ( n + p 一1 ) 的整数矩阵，满足0 u ，。s 一1 ( rep 】，s h + p 一1 ) 并恰有k + p 一1 个零列，且其他列的元素皆大于零并严格递增。则这样的 整数矩阵的个数为i s 2 ( n ，p ) f 。 证明- 在定理1 2 中设n ：= n + p 一1 ，k ：= k + p 一1 ，注意到对任何s h + p 一1 卜 f 】，亡2 ，t 女押一1 ，根据定义t 2 有1 u l s ) 地( s ) 嘶( s ) 兰s 一1 故如上结 果成立 口 1 1 2p - s t i r l i n g 数的差分恒等式 在组合数学中，有许多包含( 广义) s t i r l i n g 数的恒等式 1 7 8 j 。在这一小节中给 出了几个新的有意义的关于p - s t i r l i n g 数的差分恒等式 定理1 4 ：设正整数n ，r o ，p 1 ，有 静r 。一) 跏+ r + i , r + i , p - 1 ， 善p nc 叫一 ) 吣n + r + i , r + i , p - - 1 ， 静p ) & c n + r 一- i , r a - i , p - 1 ， 扣p 1 陆c n + r + i , r + i , p - 1 ， 8 ；竺型 矿n ! = ( - 1 ) “鼎 ：世 01 ) “州 = ( 叫”揣 1 2 3 4 1 i 1 1 1 q 姐 q n 第2 章 两类y - y s t i r l i n g 数 证明：注意到当p = 1 时，最( m ，o ) ，s t ( 吼女，0 ) ( # 1 ，2 ) 退化为二项式系数，这种情形 的证明是简单的。在p 2 时，我们只给出( 1 1 1 ) 的具体证明。其他三个式子( 11 2 ) 、 f ll3 ) 和( 1 1 4 ) 可同理得证。 对任何整数r 0 ，令a 。( s b 叫) 为m ( 肌+ 7 , + r 1 p 一1 ) 的( p n + r ) 一矩阵分拆 b ( p n + n + r ；p n + n p1 ) 的子集，且满足在b ( p n + 礼+ r i p 7 l + _ p 一1 ) = ( 反，) 中有一列 以( 8 ) 作为它的分量元素，也就是对某个胁+ r 】，b b = s ) 0 如一1 ) 易得，集 合a 。的基数为岛n + n + r 一1 ，p n + r l ，p 一1 ) 。事实上，可以证明对m 个不同的集 合凡，a 。，a 。，它们之交n 坠1 a “的基数为岛( m + n + r m ，肌+ r m ，p 1 ) 。 设五表示集合a 。的补集。考虑集合n 墨l 五，。对任何( b “) n 銎l 五，设t j = m i n ( b a 3 ) ( j l o n + r 1 ) 。显然t l t 2 n r e s ( t ”1 ( 1 + ) “2 。”5 k 一”一1 = 0 。 # 注意到s ( n ，) 和t ( n ，k ) 指数生成函数分别为 主n = k 咖，m ) 筹= 扣( t 删 壹孙，m ) 淼：两1 ( 2s m ( 扩t ( n ，女) 赢= 两( 1 n h ( 耖“ n = k 、 、 同理可证( 1 1 5 ) 和( 1 1 5 ) ，从略 b ：l = | l 盔垄堡三盔堂堂主兰垡堡塞! 盐墼塑鱼堂生董王旦望盟堑墨一 1 2p - s t i r l i n g 数的矩阵性质 涉及经典的第一类和第二类s t i f l i n g 数8 ( n ，) 和s ( n ，) 的矩阵的行列式，x i l n 样有极大的兴趣。比如在文献( 3 3 ，p 2 2 8 ，【4 2 1 ， 1 1 0 等中，就有许多漂亮的这方面的例 子，我们从中列出一些。对任何整数r ，0 ，有 ，d ；j e t 。( i s ( r + ，j ) i ) 。燕。( 若番珩，n ，) det(s(r+i+joij，r + ) ) _ k 、 ， 。热( 高巷跗，旧) 。墨忽( 器) = ( r ! ) 。， ，r 、( ：1 ) = l j ， = i i ( r + ， i = 0 卉 1 5 怂而研 在前一节，我t f c f f b tl 型( m = 1 ) ，i i - 型= 2 ) 第一类、第二类p s t i r l i n g 数s 。( n ，p ) 和( n ，p ) ，且它们分别满足下面递推关系式 舅( n + 1 ，p ) = 南”岛( 竹，膏，p ) + s 1 ( n ，七一1 ，p ) t s l + 1 ，七，p ) i= 妒j 5 l m ，忌，p ) l + 1 5 1 ( n ，k 一1 ，p ) l ， s 2 婶+ 1 ，p ) = ( 2 + p p - 1 ) 岛n ，p ) + ( m 一1 ，p ) ， 咄n “l = p + ；。1 ) 协( 啪厕s z ( n , k - 1 , p ) ( 1 2 1 ) ( 12 2 ) ( 1 2 3 ) ( 1 2