（基础数学专业论文）发生函数方法在组合计数理论中的若干应用.pdf

大连理工大学硕士学位论文 摘要 组合计数理论是组合数学中一个最基本的研究方向，它主要研究满足一定条件 的安排方式的数目及其计算问题，所用到的基本原理和方法大体有：容斥原理、反演 原理、p 0 l y a 计数定理以及发生函数方法等本文借助其中的一种基本且应用广泛 的方法一一发生函数方法，对在组合计数理论中具有举足轻重地位的两类组合数： l u c a s 数和s t i r l i n g 数进行了进一步地学习和研究 本文的主要工作可概括如下 1 第一章主要介绍了本文的两个研究对象：l u c a 8 数和s t i r i i g 数介绍了它们的 起源、定义、基本性质以及研究状况 2 第二章详细介绍了本文研究所用到的主要方法：发生函数方法借助抽象代数 的观点，将发生函数定义为形式幂级数，在引进形式幂级数的一种加法和乘法 运算后，可使一切形式幂级数做成一个整环，为发生函数的四则运算建立了严 谨的理论基础最后通过举例，形象地展示了这一方法的具体应用 3 第三章把发生函数方法的思想运用到对广义l u c a s 数的研究中，借助各种已知 数列的发生函数，得到了若干包含广义l u c a s 数的平方及三次方的恒等式，并 在最后借助所得到的恒等式给出了l u c a s 数的几个同余性质 4 第四章从组合意义角度对两类普通s t i r h n g 数进行了推广结合推广后的两类 s t 试i n g 数的组合意义，首先给出了它们满足的基本递推关系接着又给出了它 们的各种形式的发生函数进一步又得到了推广后的两类s t i r l i n g 数的若干基 本性质，如“三角”递推关系， “垂直”递推关系，同余性质等 关键词：发生函数； l u c 鼬数；同余； s t i r l i n g 数 修风光：发生函数方法在组合计数理论中的若干应用 s o m ea p p l i c a t i o n so ft h eg e n e r a t i n gf u n c t i o ni n c o i l l b i n a t o r i a lc o u n t i n gt h e o r y a b s t r a c t 。i h ec o m b i n 8 t o r i a lc 0 1 1 1 1 t i n gt h e o r yi st h em o s t 缸n d 舡n e n t a lr e s e 8 r c ho r i e n t a t i o n 洫 c o m b i n a t o r i c si tp r i m a r i l ys t u d i e st h e um _ b e ro ft h ep l a c e m e n tw a y sw h i c hs a t i s 母s o m e 印e c m cc o n d i t i o n sa n da l s ot h ec o m p u t a t i o p r o b l e m t h eb a s i cp r i n c i p l e s 锄dm e t h o d s i tu s e si n c l u d e ：t h ep r i c i p l eo fi n c l u s i o na n de ) ( c l u s i o n ，t h ep r i c i p l eo fm o b i u si n v e r s i o n ， p o l y at h e o 。yo fc o u n t i 舀t h em e 址1 0 do fg e n e r a t i n gf l l n c t i o na n ds o o n b yu s eo ft h e b a s i ca n dw i d e l ya p p l i c a b l em e t h o d0 f 址lt h ea b o v em e 七h o d s 一七h em e t h o d0 fg e n e r a t i n g m c t i o n ，t h el u c a sn u l b e ra n dt h es t i r l i n g u 1 _ b e r sa r es t u d i e di nt h j sp a p e r ，w h i d lp l a y a ni m p o r t 粕tr o l ei nt h ec o m b i a t o r 试c o u n t i n gt h e o r m t h em a j nr e s u l t so b t 舒n e di nt h i st 1 1 e s i sc a 丑b es u n l m a r i z e da sf 0 o w s ： c h a p t e r1o ft h i sd i s s e r t a t i o ni sd e v o t e dt oi t r o d u c i n gt h et w op r i m 盯y 瑚e a r c h o b j e c t so ft h i sp 印e r ：t h el u c a sn 眦b e ra 皿dt h es t i r l i n gn u m b e r t h e i ro r i g i n ，d 曲n i t i o n ： b a 8 i cp m p e r t i e sa 丑dt h er 鹳e a r c hs i t u a t i o n 缸ei n t r o d u c e d c h a p t e r2i n t r o d u c e 8t h o r o u g h l yt h em 8 i nm e t h o du s e di nt h i sp a p e r ：t h eg e n e r a t i g f u n c t i o n b ym e a so ft h ep o i n to fa b s t r a c t 越g e b r a ，t h eg e n e r a t i n gf l l n c t i o ni 8d 血n e da s f o r m mp d w e rs e r i e s a n d 越lt h ef o r m a lp a w e rs e r i e sc a nf o r ma ni t e g r 日】d o m a i n 时t e r i n t r o d u c i n gak i n do fa d d i t i o na n d m t i p l i c a t i o n0 ft h ef o 珊a lp o w e rs e r i e s t h e s e 西v ea r 逗o r o u st h e o r e t i c a lb a s i st ot h ef o 眦撕t h 工e t i co p e r a t i o n so ft h eg e n e r a 七i n gf u n c t i o n ，i n t h ee n dw ed i s p l a y 订、r i d l ys o l ec o n c r e t ea p p l i c a t i o n s0 ft h j 8m e t h o db y 进u s t r a t i o n h c h 印t e r3w ea p p l yt h ei d e ao fg e n e r a t i n gf u n c t i o nt ot h es t u d yo ft h eg e n e r a l i z e d l u c a sn u m b e r b ym e a n s v 缸i o u sl 哪g e n e r a t i l l gm n c t i o 80 fs o m e8 e q u e n c e s ，s o 击e i d e n t i t i e si v o l 血gt h e8 q u 盯e sa n dt h ec u b i c so ft h i sn u l b e r 甜e9 0 t t e n ha d d t i o n ，b y 1 1 s eo ft h eo b t a j n e di d e t i t i e sw e 西v es o m ec o n g r u e c er e l 毗i o n 8o ft h el u c a s u 1 _ b e r c h a p t e r4i sa r r a n g e da sf 0 i l a w 8 a t6 r 8 tw ee 砒e n d 妇et w o 虹d s0 fo r d i n a r v s t i r l i i l gm m l b e r sf r o mt h ec o m b i n a t o r i 缸a n g l e a c r d i n gt ot h ec o n l b i a t o r i a ls e n 8 e0 f t h eg e e r 8 j i z e ds t i r l i n gn u m b e r s ，s o m eb a s i cr e c u r r e n c e st h e ys a t i s 母壮e 西v e n t h e nw e o b t 血a l lk i d so fg e n e r a t i n gm n c t i o n0 ft h e s em l m _ b e r sa n ds t u d yt h e i rb a s i cp r o p e r t i e s ht h ee n dm a yr e s l l l t sr e l a t e dt h eg e n e r a | i z e ds t i r l i n gn u m b e r s 缸ed e r i v e d t a k et h e “t r i a 皿g l e ”r e c u r r e n c e ，t h e “v e r t i c a j ” r e c u r r e n c ea n dt h ec o n g r u e n c ep r o p e r t yf o r e x a m d l e k e ) 啪r d s ：g e n e r a t i n gf i l n c t i o n ；l u c a sn u i n b e r c o n g r u e n c e ；s t i r l i n gn m n b e r i i 大连理工大学硕士学位论文 符号说明 下面给出本文中常用符号代表的含义 1 旧：对于任意实数。，符号m 表示不超过z 的最大整数 2 矧”，( z ) ：设，( z ) 是z 的幂级数，符号矧”，( z ) 表示幂级数，( z ) 中。“的系数 3 o b ( m o dm ) ：设o ，b 是任意两个整数，如果对于正整数m ，有n b 被m 整 除，则称。与6 对模m 同余，记为o ；6 ( m o d m ) 4n ! ：对于任意非负整数n ，令n ! = n m 一1 ) 2 1 ，简称为n 的阶乘这里约定 01 = 1 5 ( z ) 。：设z 为任意复数，n 为任意非负整数，令( z ) 。= 。扛一1 ) 扛一n + 1 ) ，称 为。的长为n 的降阶乘如果n = o ，则约定( z k = ( z ) o = 1 6 ( 。) 。：z ，n 同上规定，( z ) 。= z ( z + 1 ) ( z + n 一1 ) ，称为z 的长为n 的升阶乘 这里同样约定( z ) o = 1 ，( o ：( o = 静塞这卧蝴赖整数 合的r 组合数，通常被称为二项式系数 表示n 元集 。“芦。警，：三：一贼。 s ( ：) ：( ：) = ， 剐 削：二：这里n 为任意实数，m 为任意整数 ( ：) 通常被称为广义二项式系数 。f 。：m 。：1 ：志，一争这鼽，柏腓 玑( ，辟) 乜，b ) 2 f 囊芝粤小h 一，柏腓 负整数 ( ，”，l 称为多项式系数 向1 ，尤r 1 0 牛顿二项式定理：设n 是一个任意实数，则对于满足o 吲 n ) 的最大公园数时，其除法次数不趱过n 的位 数懿5 偿，卷簿。正医斑如此，遽些序列引越了众多数学家和数学爱好畿鹣浓厚兴 怒蘸舔上，速方萄魏研究稻搽讨十分活跃在美溪激子l 粥s 举蹬敝了专门秘穆： 鞭b 姚粥e iq u ”t e r l y 静。从1 9 8 4 年起，叉每蕊两帮召开一次n b o n a c c i 数及其成 建鹣溪瓣会坡，蔽弓| 了毽赛馨魏洛多数学王佟者蔻绫参热。 1 2 s t i r l i n g 数研究的历史背景 在本文巾，我稻要研究豹努一类组合数燕：第一类s t 打n n g 数8 帆盎) 和第二类 s t 妇致n g 数s ( 玮，) s 越r l i 聪数魏藏念蔻凑j 戳妊| i 嚣g 手1 7 3 0 华纛穗鹣，并在毽褥著髂t 酗d 毽s d i i f 群e n t i a l i s 中首次使用这一名称的正式运用则繇归功于t h i e k 和n i 幽e n 1 7 7 0 年，l l a 婀e n g e 推导出了第一类s t i r h n g 数的递推荧系和一些数论性质而p s l 雌l 鑫c e ( 1 8 2 1 ) 帮焘g 聪琏猡囊攘繁二类s 螽鞋醒数懿遥透理沦上驭缮了一鉴残暴。 对8 t 蕊n g 数徽透彻研究的要数铂，j o r d a n ，德得如了s t i r l i n g 散的若干黧要性质 1 9 徽年，l e o m t e t 在诬孵著佟 l 罐中拿出了熬整一濑寒奔绍逸疆类数，势虽提供 了大璧参考文簸。 下面找们首先给出两类s t 妇l i n g 数的定义我们融约定对任辩复数z 及非负整 数佗，( z k 一茹渖一1 ) 一住+ 1 ) 称为z 的长为竹的降阶乘当将彳着作一个复变 量拜孛，窀裁怒一令关予嚣戆n 次多褒式。 记g 为全体次数不超过n 的复系数多项式所形成的线能空闻，则多项式组 l ，。，护 及 ( 。) o ，( 。) l ，嚣) 。 霹为潮懿豢疯，于是嚣缀务凌妓之耀霹蔓 稿绫谯表出： n ( 。) n = s ( ) 扩 ( 1 1 ) 缸= 8 2 大连理工大学硕士学位论文 n 扩= s ( n ，) ( z ) k ( 1 2 ) 七= 0 定义1 2 1 由以列和n 纠式所定义的表出系数s ( n ，) 和s ( n ，) ( o n ) 分 别称为第一类和第二类s i 施凹数有时为了与以后出现的各种其它砌他卵数相区 别，上述两类蹦r 托叼数常分别被称为第一类和第二类普通i 崩叼数 当非负整数 n 时，我们补充定义s ( n ，) = s ( n ，) = o 此外，由定义易验证两类s t i r h n g 数具有如下一些特殊值： s ( n ，o ) = s ( n ，o ) = o ，( n o ) ， s ( 礼，n ) = s ( n ，扎) = 1 ，( 凡o ) 人们发现，如此简单的形式所定义的s t i r l i g 数在组合学中有着广泛的应用 它们具有许多好的性质例如： 定理1 2 1 【10 】第二类州i 唧数s ( n ，) 满足“三角”递推关系： s ( n ，南) = s ( 礼一1 ，七一1 ) + 七s ( n l ，七) ，( n ，屉1 )( 1 3 ) s ( n ，o ) = s ( o ，七) = o ，( 扎，七1 ) ，s ( o ，o ) = 1 ( 1 4 ) 定理1 2 2 【1 q 第一类盹吨哪数s ( n ，k ) 满足。三角”递推关系： 8 ( n ，七) = s ( 竹一1 ，凫一1 ) 一( 礼一1 ) s ( 几一1 ，七) ，( n ，南1 )( 1 5 ) s ( o ) = s ( o ，) = o ，( n ，1 ) ，s ( o ，o ) = 1 ( 1 6 ) 定理1 2 3 【10 s ( n ，) 有如下的显式表达式 跏，垆击妻( _ 1 广协” ( 1 7 ) 定理1 2 4 【1 0 】s ( n ，) 的值为 咖= 。；翻叫“( ：二( 。竺0 扣一蛐， = 。匀曼) j + “( ( ：二( 。竺0 ) 竽b s ， 此外，s ( m ) 和s ( n ，) 还满足如下的“正交”关系 定理1 2 5 1 0 】当m ，n o 时，有 驴，啪限巾= 篡荨： 。， s ( n ，) s ( ，m ) = 如，。 ( 1 1 0 ) 矗0 3 修风光：发生函数方法在组合计数理论中的若干应用 进而有下面的“s t i r l i n g 反演公式”：设 ：n 0 ) ， k ：仲o ) 为任意两个复 数序列，则 = ，8 ( ) k = 争6 。= ：s ( n ，a ) 钆 ( 1 n ) k 0七0 当然，这两类组合数也具有一定的组合意义，这为它们的应用开拓了更为广阔 的天地 第二类s t m i n g 数s ( n ，) 的组合意义如下： ( 1 ) 分配问题；将n 个有区别的球放入个相同的盒子，要求各盒不空，则不 同的方法总数为s ( n ，) ( 2 ) 集合的划分；将含有n 个元素的集合恰好分成个无序非空子集的所有不 同的划分的数目即s ( n ，) 这种划分通常称为集合的一个一划分划分中的每个 非空子集称为一个块 而第一类s t i r l i n g 数s ( n ，) 满足：( 一1 ) “+ s ( n ，) ( 常被称为第一类无符号s t i r h n g 数) 等于恰可表示成个互不相交的轮换乘积的n 元置换的个数 从两类s t 试血g 数所满足的基本关系式( 1 1 ) ，( 1 2 ) 出发，人们在若干文献中推广 了这两个基本关系式，给出了各种各样的广义s t 曲n g 数对例如1 9 8 0 年，l c a r l i t z 在f 6 j 和f 7 】中讨论了一类称之为“w e i g h t e ds t i r l i n gn u n l b e r 8 ”的s t i r l i n g 数对1 9 8 2 年，m k o u t r a s 在阻】中又给出了一类被称作“n o n - c e t r a ls t i r i i n gn u m b e r s ”的 s t i r i i n g 数对1 9 8 5 年，f t h o w d 在 2 5 中研究了一对名为“d e g e n e r a t ew e i g h t e d s t i r l i g 咖出e r s ”的s t i r l i g 数对1 9 9 7 年，徐利治、g lm u u e n 及pj s h i u e 在 f 2 7 中将两类s t i r l i n g 数与d i c k s o n 多项式相结合，又讨论了一类被称为。d i d 【s o n _ s t i r l i n gn 1 1 1 b e r s ”的s t i r l - m g 数对，等等接着，1 9 9 8 年，徐利治和p js h i u e 在 2 9 】中对以往出现的各种s t i r l i g 数对从代数角度进行了统一，并给出了统一后的 广义s t m 洫g 数对的各种基本性质 他们给出的统一的广义s t i r l i n g 数对是满足如下关系式的一对数 s ，铲) = s 1 ( 凡，知) ，铲( 扎，七) ) 兰 s ( n ，七；q ，卢，1 ) ，s ( 礼，南；口，a ，一1 ) ： n ( t 怫= s 1 ( n ，啪一1 陬 七= 0 n ( t = s 2 ( m 啪+ 7 m k = 0 ( 1 1 2 ) ( 1 1 3 ) 其中n 0 ( 非负整数集) ，参数叱卢，1 为任意给定的实数或复数，且要求( a ，卢，7 ) ( o ，o ，o ) 记号( ；) 。= t p 一8 ) q 一缸) 0 一q + a ) ，称为t 关于增量a 的广义阶乘 特别地，约定( 刮) o = 1 ，( 1 ) 。= ( t ) 。 通常我们称满足上述关系式( 1 1 2 ) 及( 1 1 3 ) 的一对数 s 1 ，铲) 为一个 对或 对 容易看出，普通s t i r h n g 数对 s ( n ，) ，s ( n ，) ) 恰是一个 对也就是 4 大连理工大学硕士学位论文 说，按照这里的记法，两类普通s t i r l i n g 数可分别记作 s ( 馆，七) = s ( 礼，膏；1 ，o ，0 ) ，s ( 礼，南) = s ( 礼，南；o ，1 ，o ) 此外，人们在文献 2 6 、 5 7 中，又接着对统一后的广义s t i r l i n g 数对进行了 研究，借助它们给出了若干求和公式及组合恒等式 另外，人们对两类s t i r u n g 数进行研究的另一个着眼点就是它们所具有的组合 意义从这一角度出发又产生了若干具有一定组合意义的广义s t 讪n g 数对，如文 献 2 】、i 鹳】等中所研究的所有这些同时也为s t i r l i n g 数口模拟( 口一a n 0 2 叼) 的研 究工作奠定了基础迄今为止，关于s t i r l i n g 数哥模拟的研究成果也已有很多，可 参阅文献 14 、【1 8 、 4 0 、 4 3 、 5 3 等 5 大连理工大学硬士学垃论文 2 发生函数 发生函数又称生成函数或母函数，它的英文原词是g e e r a t i gf c t i o 它诞生 于1 8 世纪最早d em 0 i w e 在1 7 3 0 年用它来讨论f i b 0 a c c l 数十年后e u l e r 用以研 究正整数的分拆，但直到1 8 1 2 年，在l 印l a c e 的经典名著“t h e o r i ea 丑a l y t i q u ed p r o b a b i m e s ”( 概率的解析理论) 中，发生函数方法才得到充分的发展 发生函数方法的提出巧妙地将离散数学与连续数学结合了起来，为离散数学中 的若干问题提供了很好的解决方法，这极大地推动了离散数学尤其是当中的组合数 学的发展现在，这一方法几乎能处理组合数学中方方面面的各种问题成为了人 们研究组合问题不可缺少的工具之一 2 1 发生函数 我们知道，有不少组合计数问题都是对任一给定的非负整数挖求一个与n 有关 的数。，因此本质上是求个未知数列 ：n o ) 发生函数方法的基本思想是：欲 求未知数列 ：n o ) ，可先求出由此数列做成的幂级数的和函数9 ( 。) = 。z “ ，再反过来把g ( z ) 屣成幂级数1 2 上求出在许多组台计数问题中情况往往是：函数 妒比数列 ：n o ) 本身与所给条件有更直接的联系，因而相对地更容易 口0 o 。 得到前者( z “) 所应满足得( 函数) 关系式，从而将其求出 n = 0 定义2 1 1 对于一个数列 ：口o 一知，0 1 ，晚，我们称幂叛数 g ( z ) = = 蛳+ 叩+ 2 2 2 p ( 2 1 ) n ；0 为这个数列的发生函数为7 与后面的指数型发生函数相区别，数列的这种形式的 发生函数通常被称为普通型发生函敷 这样数列就转化成函数假如能够求得这个函数，则不仅原则上已确定丁原数 列，还可以通过对函数的运算和分析得到这个数列的很多性质 g ，p 0 】y a 生动而又深刻地写遭：。发生函数就象个口袋，可以装许多零碎东西 我们把携带不方便的零碎东西全都放在口袋里，就只需携带单独一个对象了完全 类似的，分别处理数列d 0 ，。，2 ，中的各项不方便，但把它们都放在幂级数( 发 生函数) o 。z “里，就只需处理单独一个数学对象了” r 生函数) 。z n 里，就只需处理单独一个数学对象了” 7 修风光：发生函数方法在组合计数理论中的若干应用 例2 1 1 求方程z l + 。2 + 。3 + z 4 = 2 0 的合于1 z l 6 ，o 。2 7 ，4 茎$ 3 8 ，2 。4 6 的整数解的个数 解记方程z l + z 2 + 。3 + 茹t = 的合于上述条件的整数解的个数为a ，则 o k ：七o ) 的发生函数 9 ( 。) = ( z + z 2 + ，- ，+ 。6 ) ( 1 + + + 。7 ) ( 。4 + + 。8 ) ( z 2 + t + ) = 。7 ( 1 + z + + z 5 ) ( 1 + 茁+ + z 7 ) ( 1 + z + + 。4 ) ( 1 + z + - + z 4 ) = z 7 ( 1 一z 6 ) ( 1 一z 8 ) ( 1 一z 5 ) 2 ( 1 一。) 一4 ， 所以 0 2 0 =i 。2 0 】9 ( z ) = 陋1 3 ( 1 一z 6 ) ( 1 一z 8 ) ( 1 2 2 5 + 。1 。) ( 1 一z ) 一4 = 脚- 咄5 。“。他1 1 拙1 3 ) ( 薹) ( 其嘞州- 1 ) 。( = 等) = 6 1 3 2 魄一b 7 6 5 + 6 3 + 2 蛇+ 2 = 5 6 0 3 3 0 一1 2 0 5 6 + 2 0 + 2 0 + 2 当然在解这个具体问题时可以不必引入 ) 及其发生函数，而直接把问题的 解化为求9 ( z ) 中。2 0 的系数，但这种化归正是发生函数的思想所在 2 2 形式幂级数 前面我们把数列凸o ，口1 ，n 2 ，所确定的幂级数口o + 0 1 z + n 2 2 2 + 称为该数列 的发生函数而要把幂级数g ( z ) = a d + n l z + 0 2 。2 + 确实当作“变量。的函数” ，一种最自然的理解是把。当作复数变量，则9 ( z ) = 吼在其收敛圆 ：( n 。+ b 。) 。“ ( 2 3 ) n = o 称，( z ) + g ( z ) 为形式幂级数，( 。) 与9 ( 。) 之和，把运算“+ ”叫做加法， ，( o ) 与g ( z ) 相乘定义为 o 。n ，( $ ) g ( 。) ；( 口曲 ) 矿 ( 2 4 ) n = 0 女= 0 称，( 。) 9 ( z ) 为形式幂级数，( z ) 与9 ( z ) 之积，把运算“- ”叫做乘法 注我们可看到，在收敛情形时，这里定义的加法和乘法运算与普通幂级数的 相应运算是一致的 定理2 2 1 集合g 【叫 在上述加法和乘法运算下构成一个整环 证明首先容易验证g 恻 关于加法是封闭的，并且加法满足结合律和交换律 此外，a 叫】关于加法有零元，其零元是数列( o ，o ，o ，) 的形式幂级数，记作o 同时，对于任意形式幂级数扩，它在加法运算下的逆元是数列( 一如，一。1 ，一 # 0 o o ，) 的形式幂级数( 一) 妒从而可知，( g f 【胡 ，+ ) 是交换群 其次，证明( e ，) 是一个可交换的含幺半群首先：容易验证，a i m 】在上述 乘法运算下是封闭的，并且乘法满足结合律和交换律其次，若取n 。= 。一“ 【o ，礼三1 ，则形式幂级数扩是一乘法单位元，记作1 因此，( g 恻 ，) 是一个可交换的 ”= 0 含幺半群 9 修风光：发生函数方法在组合计数理论中的若干应用 最后，不难验证乘法对加法满足分配律，而且无零因子事实上，设 则 n 。矿o e 矧 r l = 0 6 。扩o g 叫 n = 0 。000 cn ( o 。扩) ( k 扩) = ( a k k ) 扩 r = d n = 0n = 0b = 0 必不为零 因此，g 防】在上述加法和乘法运算下构成一个可交换、含单位元、无零因子 的环，即整环证毕 定理2 2 2 ，( 。) = 护在c 叫 中可逆的充要条件是o o o ， n = u 证明，( 。) 可逆骨存在g ( z ) = 6 。扩，使，( 。) - 9 ( z ) = 1 # 亭存在 f k ：n 0 ，使以下关系式成立： 。+ + a n a 。= ：蓁：i ： 甘对任意n ，下面的线性方程组对b ，b 1 ，k 有解 ) = ( 号知o 证毕 既然所有形式幂级数的集合在上述规定的加法和乘法运算下构成一个整环，而 且对于具有非零常数项的那些形式幂级数还可求它的乘法逆元，因此如同收敛级数 的情况那样，四则运算可以畅行无阻又因为如上规定的形式幂级数的两种运算方 式和数学分析中对收敛级数规定的相应运算是一模一样的，因此当形式幂级数为收 敛级数的特殊情况下，不管扶哪个角度来处理，计算的最后结果总是一致的，此时 还可用它的和函数去代替它参与运算特别是当和函数为初等函数时更为方便 因此，我们把发生函数当作形式幂级数来处理是方便的，只要运算没有越出上 面所述及的范围。可以一律不用顾及收敛性问题 对于整环g 旧 中的形式幂级数还可以引进形式微商 1 0 帅机缸 ，。一、 0 0 如 0 0 吼。7吣 册 们 咖 f 大连理工大学硕士学位论文 定义2 2 _ 4 对任意，( z ) = 量n 。扩e 盼 】，( z ) 的形式导数八z ) 绒记为差j 定义n = u 。 为 ，k ) = 。l + 2 螂+ 3 0 3 2 2 + = 十1 ) 州 ( 2 ，5 ) 这种运算同样具有通常导数的性质 ( ，( z ) + g ( z ) ) = ，( z ) + 9 7 ( z ) ( ，( z ) 9 ( z ) ) 7 = ，7 ( 。) g ( 嚣) 十，( z ) 9 7 ( 。) 也可以定义积分运算： 尉削v + + 扣一薹击h ( 2 6 ) ( 2 7 ) 而且有乏i ，( ) 曲= ，( z ) 对于，( z ) ：妻扩g 忙 】) 通常形式地记，( 。) = 。= 壁挚，其中，( n ) ( z ) 是，( z ) 的n 次导数这和确定解析函数，( z ) 的t a y l o r 展式中。“的系数的公式完 全一样 下面是几个常用数列 o 。：n2o ) 的发生函数，( 。) = 矿，不难象作t a y l o r 展开那样一一验证 。) ，k = o ，l ，2 ， 发生函数 l 1 o k = 1 1 一z 2 0 k = 七 f l 一七) 2 l 3n = 舻 1 一凸! o 4 凸0 = o ，。k = 1 】一m 5 一( ；) ，a 任意 ( 1 + ) o 6 n 。= 等，a 任意 e ( 一1 ) “ 7 毗2 _ 丽 c o s 、z 8 。t = 吉斋 1 广 孺8 m 、。 此外，在处理与排列有关的计数问题时，经常要考虑数列 ) 进行“加权” 三 后的新数列f 鲁1 的发生函数为此，我们引进如下定义； in ! j ln ! j 修风光：发生函数方法在组合计数理论中的若干应用 定义2 2 5 对于复数域上的任一数列 n o ，口l ，0 2 ，) e o 。：n o ) ，形式幂级数 ，伍) = 。+ 鲁。十詈。2 + 毒暑扩 2 n n 等 n = o 一 称为该数列的指数型发生函数 例如，若a 。；1 机= o ，1 ，2 ，) ，则 ：竹o ) 的指数型发生函数为 薹a 鲁薹筹划 ( 2 8 ) 这也正是“指数型”这一名称的由来 从上述定义知，指数型发生函数与普通型发生函数的一般项仅相差一个因子去 如以 东) = 等) 作为数列，则 菇) 的普通型发生函数就是 。 的指数型发生函 数这样，数列 ) 的指数型发生函数的各种运算( 如加、减、乘、除、微商、积 分等) 就完全可以按照数列 露 的普通型发生函数的相应运算而得出，而不必另 作规定 我们上面提到的两种发生函数是关于简单序列的最常见且应用最广泛的两种类 型当然还有若干其它类型，有兴趣的读者可参阅文献【4 2 、 4 9 此外，关于形式幂级数的较深入的讨论，可参看文献 3 6 】、 、 5 8 1 等 注关于多重序列的发生函数 发生函数的概念可以拓广到多重序列在此我们只简单介绍一下双重序列的情 况， 设 ，k ：n ，o 为一双重序列，则常用到的t n 。，k ：竹，o ) 的三种发生函数 是如下三个形式幂级数 西( t ，“) = ，k “铲， n ，七2 0 蜘，2 毛吣篇竹k u 叫屯2 岳t n ，托= u ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) 作为例子，我们看一下二项式系数的双重序列t = ( 力的各种发生函数，此 1 2 大连理工大学硕士学位论文 时 吣，小善( ：) 吼k = p 侄。( = 俨( 1 + u ) ” n 0 1 1 一t ( 1 + 钍) ( 2 1 2 ) e ”，2 厄( ：) 等扩2 萎孔妒 = e 印0 ( 1 + u ) )( 2 1 3 ) 2 3 发生函数的应用 我们在前面已提到过，发生函数最早主要被应用于正整数分拆及概率论等有关 问题的研究中关于这两方面的较详细地论述，可以参阅文献 1 、【3 3 】、 3 6 等 后来随着人们对这一方法的不断深入研究，如今发生函数方法已经成了离散数学领 域中的重要方法，它能以某种统一的程序方式处理和解决众多不同类型的问题关 于这一方法的著作很多，较详细且基本的论述可参看3 2 1 以及专门论述发生函数的 引人入盛的著作 4 9 此外，关于这一方法的研究，还出现在一些有关差分运算的 文章中，如【3 1 1 、【4 1 等。在组合数学中，它的最显著的应用莫过于求解各种各样 的递推关系、证明组合恒等式及组合计数方面有关发生函数方法在求解递推关系 中的应用，在文献 4 5 】中有详细的介绍，我们在这里不再赘述在此仅举例说明一 下这种方法在组合计数方面的应用 问题2 3 1 设韪，鼠是非负整数集合0 的个子集求在元集y = l ，弛) 中允许重复的取n 个，使玑的重复度属于& 0 = 1 ，) 的重复组合个数c 岛，一，s 。( n ) 若在如上所述的一个重复组合中，元素统的重复度为则有s l “= 1 ，七) ，且0 1 十+ z k = n ，于是我们有 ，一，巩( n ) = 1 o l + 。k = “ 气s ，( t = 1 ，2 -，k ) ( 2 1 4 ) 即c 文，筑( ) 等于下述带限制条件的不定方程。1 + + z = n ( 。 & ，i = 1 ，动 的非负整数解个数 但我们的目的是想给出c 甄，鼠( n ) 的( 关于n 的) 发生函数表达式从而利用 所得发生函数可对一些具体给定的毋，求出c s 。，( n ) 的明确表达式 为此，我们先给出如下的一个定理 1 3 修风光：发生函数方法在组合计数理论中的董量摩甩 定理2 3 1 设 ( n ) ) 0 = 1 ，k ) 是k 个序列，s 1 ，鼠0 是非负整数集的 女个子集则限制和式 的发生函数为 则 = ，1 ( n 1 ) ( 讯) ( 2 1 5 ) 。萄；舞? * ， 若n s ， 若n 仨& ( ( 咖n ( 2 1 6 ) n s ，1 ( n ，) ( n * ) n 1 + 一+ n k = n = 矗( n ，) 五( n t ) + 五印，) 矗( n * ) n 1 + 一+ n 2 n “l ，“k ) s l xs 女 = ( n 1 ) ( n ) + o ( 。? j 乏；赭嚣碱 =nn 于是由多个形式幂级数的乘积公式可得 扩= n = 0 ( ，1 ( n ) 妒) n = o ( ( n ) 矿) n ( 氕( n ) 妒) n = o ( a ( 咖“) n 巩 由此定理，我们马上可以得到问题2 3 1 的以发生函数形式给出的解答 定理2 3 2 若= c 夸“，r ( n ) 为问题2 3 1 中的带一般限制条件的重复组合个数， 其中，研，瓯均看成是固定的则序列 n 。 的发生函数可表为 矿= ( z ”) n = 0 n s l 证明在定理2 3 ，1 中取诸 ( 乱) ；1 0 = 1 的表达式( 2 1 4 ) 之右端由此可得发生函数 ( 扩) ( 2 _ 1 7 ) n s k ) ，则( 2 1 5 ) 式右端成为仍。一，鼠( n ) 郴”= ( 扩) ( 扩) n 0 n s ln 鼠 恰为( 2 1 7 ) 式从而此定理得证 1 4 ， 晒 ； n w c l m 五以 ，、l l i 列 亭助辅作明 篁 盔垄里三盔兰堡主芏垡丝苎一 例2 3 1 设有a 和口两种字，每一种均有无限个 4 利用发生函数求出选取的方法数k 从中选取n 个，其中含偶数个 解此时相当于s 1 = o ，2 ，4 ，凯，) ，s 2 = o 的发生函数为 故运用定理2 3 2 ，可知相应 k 矿= ( 1 + z 2 + z 4 + ) ( 1 + 。+ z 2 + ) n = 0 11 1 2 = 虿f i 2 百i 西两 1 ， 11 2 1 2 i 【百五十f i 十石i 予1 = ； ( 一1 ) v + 扩+ 2 ( 竹+ 1 ) 叫 n = 0 = 0 n = 0 = ；【( 一1 ) “+ 1 + 2 ( n + 1 ) 】“ 从而 ： ( 一1 ) 。+ 1 + 2 ( 。+ 1 ) 】：垄竺掣= i 【( 一1 ) 8 + 1 + 2 ( + 1 ) 】2 2 。 运用类似的方法，借助指数发生函数，我们又可给出下述问题的解答 问题2 3 2 设s 1 ，s k 是非负整数集合o 的个子集求在元集y = 讥，弧) 中允许重复地取n 个，使饥的重复度属于最0 = 1 ，) 的重复排列数两- ，一，乳( n ) 定理2 3 3 设：p s “一，( n ) 为问题2 3 2 中的带一般限制条件的重复排列个数， 其中，s l ，鼠均视为是固定的则c n 的指数型发生函数可表为 薹等= c 丕扣c 轰扣 亿埘 例2 3 2 由1 ，2 ，3 ，4 所组成的n 位数中，合偶数个1 的共有多少? 解设含偶数个1 的共有个，则由定理2 3 3 知，对应的指数型发生函数为 妻。筹= ( ，+ 蔷+ 箬+ ) ( 1 + 岔+ 署+ ) 3 ：竽铲：竿 z ；扩+ 2 “) 等 于艏 。：半甜一，( 2 。+ 1 ) _n n = i 一= z l z1 _ 1 。 上述两个例子也提醒我们，应该深刻体会发生函数的组合学背景，从而才能正 确地应用发生函数方法例如，要解决组合问题，就应该选用普通型发生函数，要 解决排列问题，一般就应该选用指数型发生函数 1 5 大连理工大学硕士学位论文 3 有关广义l u c a 8 数的一些新结果 本章借助发生函数的方法，对广义l u c a s 序列 ：n 0 ) 做了进一步的研 究所谓广义l u c a s 序列 k ：n o ) 是指满足递推关系= p 一1 一g k 一2 ( n22 ) 及初始条件= 2 ，h = p ，其中参数p 1 口均为整数的一个序列我们给出了一些 包含这个序列的平方及三次方的恒等式，同时借助它们得到了一些关于l u c ”序列 l 。：n 2o 的恒等式及同余关系 3 1 引论 h o r a d 岫【2 q 定义了一个满足如下递推关系及初始条件的二阶线性递归序列i = i ( o ，6 ；p ，g ) ，n = 0 ，1 ， i = p 1 一1 一9 1 1 一2 ( n 22 )( 3 1 ) w i = ，m = 6 其中的参数o ，b ，p ，g 均为整数并且指出，如果序列 w 名：n o 的特征多项式 a 2 一砧+ g 有两个不同的根，不妨设为。与卢，则关于序列 w 名：n o ) ，我们有下 述b i n e t 公式： 眠= 等， ( 3 2 ) 其中a ：6 一。卢，b ：6 一。叩：堕粤，卢：芝掣 此时，结合第一章中提到的f i b o n ”d 数r 与l u c a s 数k 的定义，可以知道， r 与k 可分别表示为r = 矸名( o ，l ；1 ，一1 ) ，k = 矸，n ( 2 ，1 ；1 ，一1 ) 通常我们还有如下 记号：