（应用数学专业论文）riordan群综述.pdf

r i o r d a n 群综述摘要 摘要 本文主要就l a g r a n g e 反演公式、眦d ib r u n o 公式和r i o r d a n 群各自理论 形成、内容方法以及彼此之间的联系和区别所做的一个综述， 第一章总结了r i o r d a n 群的各种主要定义以及与它相关的l a g r a n g 反演公 式和黜d ib r u n o 公式、 第二章对r i o r d a n 群理论的主要运算规则、目前已经建立的r i o r d a n 群的 主要理论做一概述，其中由l a g r a n g e 反演公式给出的运算法则对级数求和有 着重要作用 第三章主要分析了r i o r d a n 群在计算组合和式方面以及反演关系方面的 应用，并且纠正了e g o r y c h e v 等人文章中的一个组合反演关系，推广了h w i l f 的著作g e n e r a t i n gf u n e t i o n o l o g y 中一个问题结论 第四章通过详细计算阐述了这样一个历史误会( 这也是本篇综述的目的 所在) ：r i o r d a n 群不是人们理解成的一个新方法，其思想早就蕴含在一个多 世纪前就存在的眦d ib r u n o 公式中了 最后一章提出了一个尚待解决的问题 关键词：r i o r d a n 群；反演关系；r i o r d a n 矩阵；求和公式；f a a d i b r u n o 公 式；l a g r a n g e 反演公式 作者：任利梅 指导教师：马欣荣( 教授) as u r v e yo nr i o r d a ng r o u pa b s t r a c t as u r v e yo nr i o r d a ng r o u p a b s t r a c t i nt h i st h e s i s ，w et r yt om a k eac o m p r e h e n s i v es u m m a r yo nr i o r d a ng r o u pa sw e l l a si t si n t e r p l a yw i t ht h ec e l e b r a t e dl a g r a n g ei n v e r s i o nf o r m u l a ，t h ef a m o u sf a ad ib r u n o f o r m u l aa n dt h e i rv a r i o u sa p p l i c a t i o n si nc o m b i n a t o r i a la n a l y s i s c h a p t e ro n ew es u m m a r i z ea l lm a i nc o n c e p t so ft h er i o r d a ng r o u pa n dr i o r d a n a r r a ya n di t sc o n n e c t i o n sw i t ht h el a g r a n g ei n v e r s i o nf o r m u l af a 色d ib r u n of o r m u l a c h a p t e rt w oi sd e v o t e dt oa l lm a i nr e s u l t si nt h et h e o r yo ft h er i o r d a ng r o u p o b t a i n e du pt od a t e ，s o m ef r e q u e n t l yu s e dt e c h n i q u e si n v o k i n gt h el a g r a n g ei n v e r s i o n f o r m u l aa r ea l s or e p h r a s e d i nt h et h i r dc h a p t e r ，w es k e t c ht h r e ea s p e c t so fa p p l i c a t i o n so ft h er i o r d a ng r o u p ， m o r ep r e c i s e l y , i nc o m b i n a t o r i a ls u m m a t i o n sa n dt h e i rd u a lf o r m si nv i e w p o i n to fi n - v e r s er e l a t i o n s i na d d i t i o n ，w eg i v et h ec o r r e c tf o r mo fa ni d e n t i t yp o i s e db ye g o r y c h e v e ta 1 w i t ha ne v i d e n te r r o r ，a n dag e n e r a l i z a t i o no fa ni d e n t i t yr e c o r d e db yw i l fi nh i s b o o k “g e n e r a t i n g f u n c t i o n o l o g y ” i nc h a p t e rf o u r ，a sab a s i cm o t i v a t i o no ft h i st h e s i s ，w ep u tf o r w a r dan o v e lo p i n i o n o nah i s t o r i c a lm i s u n d e r s t a n d i n gb yad i r e c tc a l c u l a t i o n ：t h er i o r d a ng r o u pi sj u s ta s p e c i a lc a s eo ft h ef a ad ib r u n of o r m u l aw h i c hc a nd a t eb a c kt om o r et h a no n ea n d h a l fc e n t u r ya g o t h ef i n a lc h a p t e rw ep o s ean e wk i n do fr e c u r s i v er e l a t i o n sa sa no p e np r o b l e m k e y w o r d s ：r i o r d a ng r o u p ；i n v e r s et e c h n i q u e ；r i o r d a na r r a y ；s u m m a t i o nf o r - m u l a ；f a a , d ib r u n of o r m u l a ；l a g r a n g ei n v e r s i o nf o r m u l a i i w r i t t e nb yr e nl i m e i s u p e r v i s e db yp r o f m ax i n r o n g 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不含其他个入或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本 声e 且的法律责任。 研究生签名：丝矗：1 整日期：迦刍：垒：! y 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 期：西：垒：坠 聚、竺i ? 匕二f r i o r d a n 群综述 第一章绪论 第一章绪论 鉴于l a g r a n g e 反演公式、f a hd ib r u n o 公式和r i o r d a n 群理论在计数组合 学中的独特地位和作用，本文将对其各自理论形成、内容方法以及彼此之 间的区别和联系做一完整的综述 自从r i o r d a n 群的概念提出来之后，r i o r d a n 群渐渐为越来越多的学者所 青睐，现在它已经成为组合分析中的一个热点问题它的重要性不言而喻， 但是迄今为止几乎所有的研究者均把r i o r d a n 群视为最近二十多年发展起来 的一种新理论或新方法来看待，其实不然通过本文第四章的分析，可以 清楚地看到：r i o r d a n 群的思想早就蕴含在一个多世纪前提出的麟d ib r u n o 公式中了为了还历史一个公正，我们以此作为论文的选题为此我们先 引述一个重要公式 定理1 1 1 设，= n o 矿为形式幂级数，c t ：= a n = ，中t n 项的系数设 口o = 0 ，口l 0 ，则存在， = n la n t n ，使得，o ， = ， o ，= t ，且对所 有的整数后，1 k m 有 删“节= 转t ( 华) 此定理在文献中被人们称之为l a g r a n g e 反演公式，是l a g r a n g e 在1 7 7 0 年 提出的除此之外我们还需了解另一个公式，其重要性或多或少被研究者 忽略了 定理1 1 2 设，9 为两个形式幂级数 ，：= 莓礤舻m 0 等一。， h 为，和9 的复合，则h 也是形式幂级数 2 赢k 两t - = f og = 他1 第一章绪论r i o r d a n 群综述 且系数k 可表示为； h o = y o ，k = k s n ，k ( g l ：9 2 ，鼽斟1 ) ， l 七g n ，k t n 由( 2 2 5 ) 式可得g k 一1 ( z ) = a ( t ) g ( t ) t 所以 g 础，= 南g 一- = ( 南) 2 g 以， 记g o ( o = d l ( t ) ，h i ( t ) = 赢则可得 鼽，k = 【t n d , ( t ) h k l ( t ) 由于a o 0 ，易验证d l ( o ) o ，h l ( o ) = 0 ，且h i ( o ) 0 故g = ( d l ( t ) ，h l ( ) ) m n ，显 然d m n ，且d = ( 翮1 ，( t ) ) ，其中h 2 ( t ) 是 1 ( t ) 的复合逆即h 2 ( t ) 是方程 扛刁h 2 丽( t ) ( 2 2 6 ) 砧 2 q n 匙 n ” k厶 哆 触 i i +奄 + 如 得 使 0 *幻 第二章r i o r d a n 群理论的主要结果 r i o r d a n 群综述 的唯一解且如( o ) = 0 ，燧( o ) 0 记瓣1 = d ( ，则d ( ) 是序列 靠，o 。n 的生成 函数由r i o r d a n 矩阵的定义可得d = ( d ( ) ：九( t ) ) ，其中h ( t ) = 掣，由( 2 2 6 ) 可 得危( ) 满足h ( t ) = a ( 忱( 观显然h ( o ) r 一 o ) 口 十多年来，随着对r i o r d a n 矩阵理论的研究，人们逐渐认识到其在组合 和式的求和与变换中的重要作用。其中马欣荣在文【3 2 】中建立了r i o r d a n 反 演链，并讨论了r i o r da ：n 反演链在组合和中的应用下面引述该文章的主要 结果： 设，( ) ，g ( t ) 和f ( ) 是实函数，( o ) = 0 ，9 ( o ) 0 ，且f ( t ) = 盘 o a k t ，系数 d ，l ，七= t l g ( t ) 七( t ) ，无穷阶下三角矩阵( 如，) 。，七o 又被记为a = ( 9 ( t ) ，( z ) ) 显然， 当9 ( t ) f ( ，( ) ) 在t = 0 点处的t a y l o r 级数存在且易求，则从( 2 2 1 ) 式知组合和 式琶。磊，七a k 是封闭的下面给出m r 中元素构成r i o r d a n 链的充要条件 定理2 2 3 【3 2 ，定理2 1v a = ( 9 ( ) ，( ) ) ，b = ( c l ( ) ，d l ( t ) ) 和c = ( c 2 ( ) ，d 2 ( t ) ) m r ， r i o r d a n 链( a ；b ，c ) 存在的充分必要条件是 c l ( t ) 9 ( ，一1 ( t ) ) = c 2 ( ，一1 ( t ) ) 夕( d 2 ( ，一1 ( t ) ) ) ，( 2 2 7 ) 且 d l ( t ) = ，( d 2 ( 厂1 ( t ) ) )( 2 2 8 ) 其中- 1 ( ) 表示f ( t ) 的复合逆 推论2 2 1 【3 2 ，推论1 】v a = ( 9 ( ) ，( t ) ) ，b = ( c l ( t ) ：d l ( t ) ) 和c = ( 9 ( ) ，d ( t ) ) ，则r i o r d a n 链( a ；b ，c ) 存在当且仅当c l ( t ) = g ( d ( f q ( ) ) ) ，d l ( t ) = f ( d ( f - 1 ( t ) ) ) 推论2 2 2 【3 2 ，推论2 1v a = ( 夕( t ) ，( ) ) ，b = ( c l ( t ) ，d l ( ) ) 和c = ( d ( ) ，t ) m a ，贝q r i o r d a n 链( a ；b ，c ) 存在当且仅当o ( t ) = d ( f _ 1 ( ) ) ，d l ( t ) = t 本定理也可以用9 一方式来刻画 定理2 2 4 【3 2 ，定理3 】v a = ( 9 ( ) ，( ) ) ，b = ( c 1 ( z ) ，d l ( t ) ) 和c = ( c 2 ( t ) ，比( ) ) m r ，假 定f ( t ) = 七oo 七驴，g ( z ) = ob k t 后，f l ( ) = 知o 舭7 t 惫和g l ( t ) = k ob k m t ，且有关 系式 a ( t ) = 9 ) f ( ，( t ) ) ，f 1 ( t ) = c 1 0 ) f ( d l ( t ) ) ，g 1 ( t ) = c 2 ( t ) g ( d 2 ( t ) ) 则g l ( t ) = 9 ( ) 日( ，( z ) ) 当且仅当( 2 2 7 ) ( 2 2 8 ) 成立 特别当矩阵a ：b 和c 均为可逆矩阵时，则有以下的结论 1 2 r i o r d a n 群综述 第二章r i o r d n n 群理论的主要结果 定理2 , 2 5 【3 2 ，定理4 1v a m n ，a q 存在，则r i o r d a n 链( a ；b ，c 1 存在的充分必要 条件是r i o r d a n 链( a 一1 ；b ，c ) 存在 定理2 2 6 【3 2 ，定理5 】同链关系是a 的所有r w r d a n 偶的等价关系 从理论上看，同链关系可以用来划分组合恒等式，共轭链又可以用来给 出组合恒等式的等价变形进一步地，利用矩阵幂和函数复合运算，可给 出推论2 2 ，l 更一般的形式 定理2 , 2 7 【3 2 ，定理6 1v a = ( 9 ( t ) ，( t ) ) ，b = ( c 1 ( t ) ，d 1 ( ) ) 和d = ( c 2 ( t ) ，d 2 ( o ) m n ，且 r i o r d a n 链( a ；b ，c ) 存在，则r i o r d a n 链( a ；b ”，c 竹) 也存在，其中 一( 垂舢1 砒咿旷吵m = ( j i f i = 0 撕玑叫， b m = 9 ( ( 厂1 ( 亡) ) ) ，( d m ( 厂1 ( t ) ) ) ，c m = ( n9 ( ( ) ) ，扩( t ) ) ， t = 1 其中扩( t ) = t ，( t ) = _ 1 ( d ( ) ) ，m 为任一自然数 下面两个定理主要就a = ( ( ：) ) = ( 南，南) m n ，计算它的r i o r d a n 链和相 应的求和公式在此情形下，定理2 2 3 诱导出如下定理 定理2 2 8 3 2 ，定理7 】( ( ( ：) ) ；b ，c ) 存在当且仅当 b = 1 雨，篙) 且c = ( 南，d ( t ) ) m n 最简单的情况是d ( t ) = t 结合定理2 2 7 和定理2 2 8 很自然地导出下面的 定理 定理2 2 9 【3 2 ，定理8 】v ( ( ( ：) ) ；，k ) ，构作新的实数数列 7 ) ， 6 n 7 ) 如下： 小 楚( 三) 扎猢 【怨o ( 品) a k ， n m 啦k 壹- - - 0 ( 牡 则有关系式 水塞( 一三二k 1 3 第二章r i o r d a n 群理论的主要结果 利用r i o r d a n 矩阵，王天明等人在文【8 0 】中通过下面的三个定理发现了一 系列的组合恒等式 定理2 2 1 0 s o ，定理1 1 设( d ( t ) ，九( z ) ) 是一个r i o r d a n 矩阵， f ( 佗，七) 是由正整数詹 定义的二元函数，且，( t ) = 詹oa t 七若设 则 证明： t i f ( 几，后) = 妒( m 歹) k = j i，l f ( ，砒】( 9 ( ) 巾荆) ) = ：o ( n ，j ) ( 2 2 9 ) k = o j = o n f ( 琊老m ) 邢危( t ) ) ) k = o = f ( 他，七) d k ，西 k = o j = o nt l = 乃f ( n ，k ) d k , i 口 定理2 2 1 1 【8 0 ，定理2 1 设( d ( t ) ，危( t ) ) 是一个r i o r d a n 矩阵，f ( 礼，七) 是由正整数n ，k 定义的二元函数，( t ) = n o ，n 扩且五 ) ( t ) = f ( y ) i y = t h ( y 一1 ) 】= n o 五以若设 n f ( n ，k ) d k ，j = 妒( 珏，j ) k = j 则 扎 露 f ( 他，七) ( d ( t ) 巾) ) = 乃妒( n ，j ) ( 2 2 1 0 ) k = o j - - 0 若h ( 0 ) = 1 ，则由l a g r a n g e 反演公式，有 知 乃= 1 1 】( ，( 蝴) 一) 壹f ( n ，k ) i t 】( d ( ) 巾) ) ：妻妒( 他，歹) 击1i - 】( ，心) ( 九( ) ) ) ( 2 2 1 1 ) ，】( d ( ) 巾) ) = 妒( 他，歹) 引一1 】( ，( ) ( ) ) ( 2 2 1 1 ) k = oi = o o 1 4 他 妒 疗 n 舢 i f r i o r d a n 群综述 第二章r i o r d a n 群理论的主要结果 证明：由定理3 1 【6 7 1 和l a g r a n g e 反演公式，可得 n f ( n ，呲】( d ( t ) 仲) ) = k = 0 不完全b e l l 多项式 l _ 一 后! f ( n ，免) d k ，j 艿 k = o j = o nn 五f ( 扎，k ) d k d n 五妒( 歹) j = o j = o妒( n ，j ) 刍【一1 】( ，7 ( t ) ( 九( ) ) 一) b n ，七= b n ，k ( x l ，x 2 ， m z m 而 根据r i o r d a n 矩阵的定义，可得 ，x n - + - ) 是由下式定义的： 2 p ，t 熹k = 0 , 1 , 2 , - - - 幢z 。磊) 嘏蒯， 对于不完全b e l l 多项式b n m 有下面经典结论( f 瓴d ib r u n o 公式 1 0 ，p 1 3 7 ) 其中 b 。，( 亘1 ，彘，一k + 1 ) ， a o 巾) = k - - 0五笔， 鲍) ：暑讥嘉 七= 1 且 尥，= 塾蔷 设b n ，o = 晶，o ，则上面的式子可以写为 e 1 k = 五风，知( 蚕l ? 蚕2 ，：孤一七十1 ) k = 0 1 5 口 似 n 胁 | | 。k一向 = b 第二章r i o r d a n 群理论的主要结果r i o r d a n 搿综述 定理2 2 1 2 【8 0 ，定理3 1 设f ( 磁七) 是由正整数珏，定义的二元函数若设 n f ( 他，k ) b k , j = m ( n ，j ) j c = j 则 n n f ( n ，k ) h k = f ( n ，o ) a + j m ( n ，歹) k = 0 j ；1 证明：由( 2 2 1 2 ) 可得 n f ( 礼，k ) h k = k = 0 r ik f ( n ，后) 五b 幻 k = o j = o = f ( n ，o ) a + f ( n ，克) 乃b k d k = l j = l nn = f ( n ：o ) k + 五f ( n ，启) b 七j j = lk = j n = f ( n ，o ) a + 五m ( 他，j ) 2 3l a g r a n g e 反演公式与r i o r d a n 群 口 如前所述，l a g r a n g e 反演公式在证明组合级数求和与变换、计数问题、 编码理论等方面都有重要作用这一节中主要讨论它在r i o r d a n 群理论中的 应用 若记( 磊，知) n 旌n 为( d n ，七) k n 的逆，则必有 nn 鲰= d ，七 营，n = 五，k g k k = ok = o 这样许多组合和式的反演问题就简化为一个正常的r i o r d a n 矩阵的反演问 题，也就是一个严格依赖于l a g r a n g e 反演公式的问题当处理一般的求组合 和式的反演问题时，经常用到隐式的生成函数 假设序列) n n 是由c n = f ( ) 庐( t ) n 定义的因为表达式依赖于佗，所 以提取的系数时，f ( ) 咖( t ) n 不能作为( c ，1 ) n n 的生成函数为了得到隐式 的生成函数，应用g 6 ，可得 驴n = 揣l 汀揣l 1 6 r i o r d a n 群综述 第二章r ，i o r d a n 群理论的主要结果 在这里需要解函数方程伽= r e ( w ) 但有时这个方程的解无法用初等函数表 示，故将其称为称为( ) n n 隐式的生成函数 足埋2 3 1 1 4 4 ，定理2 1j 设口，q 】l ；巴，则确 匈盼隐式的生成凶数： g ( 赤( n 气口? ) 卸川嘶卯； g ( ( 。气q 惫) ) = 糕i 加：。，+ 叫，。 证明：对于( j 3 1 ) 有 乡( 赤( d ) = 9 ( 等警( 。) = 9 ( ( 8 气g 忌) 一口( 。+ 七q k ，- 1 ) ) = 9 ( 【矿1 ( 1 + t ) 口+ g 七一口【驴一1 】( 1 + ) 。+ 咖一1 ) = 9 ( p 2 】( 1 一( q 一1 ) t ) ( 1 + ) 。+ 咖一1 ) 设( t ) = ( 1 + t ) 口，由g 6 可得 9 ( 志( 口) = 爿崭铲l 卯 = ( 1 + 伽) n | 钟：t ( 1 + 。) q 对于( 2 3 2 ) 有 9 ( ( 。气口七) ) = 9 cct七】c，+t，。十q七，=i-=-羚l伽：“。+钮，。 ( 1 + 伽) 口+ 1 2 二百q = 了面b 肿 l 一( 一1 ) 伽k ：t f l 知，。 夕( 志( 口) 刈矿； 9 ( ( 。) = 满 定理2 3 2 4 4 ，定理2 3 】设a ，q r ，则有下面的隐式生成函数： 9 ( 掣) = e 砘州 9 ( 掣) = 禹l 一 ( 2 3 1 ) ( 2 3 2 ) 口 ( 2 3 3 ) ( 2 3 4 ) ( 2 3 5 ) ( 2 3 6 ) 第二章r i o r d 。 m 群理论的主要结果 l i o r d a n 群综述 证明：对于( 2 3 5 ) 有 丁a ( a + q k ) k - i：譬拦一口铄+ q k ) k - l ：i t k 】e ( m t _ q 妒_ l 】e ( 咖蛳 七!后1 1 ( 后一1 ) 1 1 。r。 = f t 七】( 1 一口t ) e a t e q k t 扩1 i 等i 加：把。 = t k e 口”l 叫：e 9 ” 对于( 2 3 6 ) 有 掣= i t k l e ( a + q k ) t = i t 七，南l e 删l = 一f 1 一q wi ：t e 口u 口 由于正常的r i o r d a n 矩阵具有群结构( 恒等元为j = ( 1 ，t ) ) ，理论上若d = ( d ( ) ， ( t ) ) ，则西= ( ) ，元( t ) ) 存在且唯一但是问题并不是那么简单一般来 说，若d = ( d ( t ) ，危( t ) ) ，e = ( ，( t ) ，9 ( ) ) 是两个正常的r i o r d a n 矩阵，它们的乘积 由( 1 1 1 ) 定义，当e = 西= ( 盈t ) ，元( t ) ) 时，结果应该是恒等元，一( 1 ，t ) 在这种 情况下，可以得到矗( t ) a ( h ( t ) ) = 1 ，元( 危= t ，于是由l a g r a n g e 反演公式得 d ( 。) 。南b 叫1 ， ( 。) = 伽廿 毫无疑问，最简单的反演是 a n = 壹k = o ( b k * tb n = 七e 薹。( - i 广七( 这里厶，奄= ( 譬) ，即为正常的r i o r d a n 矩阵p = ( 1 ( 1 t ) ，t ( 1 一t ) ) ，可以证明 d r , ，七= i t ，吉( 击) 南部础，矗击 = ( - 1 产卅( 捌) = ( 妃二七) = ( 0 所以 1 d ( t ) = 1 一钮i 伽= t ( 1 一叫) 1 = 1 一钏i 叫= 南2 南 且五( t ) = t d ( t ) ，这时有 k 卅t n 南( 南) 七= ，杀= ( 羔) 斗妒乩( 实际上，当组合和式可以用生成函数来表示时，下面定理中的方法有助 于求出它的逆矩阵 1 8 r i o r d a n 群综述第二章r i o r d a n 群理论的主要结果 定理2 3 3 f 4 5 ，定理1 】设( 靠，) 。，k e n 是正常的r i o r d a n 矩阵，d ( t ) 和b ( t ) 分别是序列 ( a k ) k n 和( k ) 忌n 的生成函数则a n = 冬。厶，k b