（应用数学专业论文）分拆恒等式的组合证明.pdf

摘要 摘要 本文主要研究分拆恒等式的组合证明方法：著名的e u l e r 分拆定理的一一映 射证明和l e b e s g u e 恒等式的对合证明此外我们还利用标号分拆的概念得到了 关于染色排列的统计量的一些结果 全文共分为四章。在第一章中，我们介绍分拆的概念以及本文中用到的定义 和记号同时，我们还将介绍处理分拆的两种方法：分拆的图像表示和分拆的生 成函数。 在第二章中，我们介绍e u l e r 分拆定理。e u l e r 分拆定理是分拆理论的基石 它由e u l e r 在1 7 4 8 年给出。在1 8 8 2 年，s y l v e s t e r 给出了e u l e r 分拆定理的一个 经典的组合证明及其s y l v e s t e r 限制。f i n e 也给出了e u l e r 分拆定理的两个f i n e 限制g l a i s h e r 也曾研究过e u l e r 分拆定理，并得到了关于e u l e r 分拆定理的 g l a i s h e r 限制随后，还有关于e u l e r 分拆定理的b o u s q u e t m 6 1 0 u - e r i k s s o n 限 制。此外，b e s s e n r o d t 和曾江分别对s y l v e s t e r 映射进行了比较详尽的总结，其 中曾江还给出了三变量限制的e u l e r 分拆定理的一个生成函数的证明。通过对 b e s s e n r o d t 插入算法进行构造性的变形，我们可以得到一个关于e u l e r 分拆定理 的包含g l a i s h e r 限制和b o u s q u e t m 6 1 0 u - e r i k s s o n 限制的两个变量的限制。 在第三章中，我们介绍了l e b e s g u e 恒等式。l e b e s g u e 恒等式可由e u l e r 公 式、h e i n e 变换得到同时它也是q - k u m m e r 求和公式的一个特例a l l a d i 和g o r - d o n 给出了l e b e s g u e 恒等式的一一映射证明此后，b e s s e n r o d t 利用s y l v e s t e r 映射也得到了l e b e s g u e 恒等式的等价形式的一一映射证明最近，基于z e i l - b e r g e r 的插入算法，付梅也给出了l e b e s g u e 恒等式的一个组合证明。我们通过 对v a h l e n 对合进行推广，得到一个新的关于l e b e s g u e 恒等式的对合证明 在第四章中，我们将分拆理论应用到染色排列的统计量的计数中去通过引 入标号分拆的概念，我们得到了f m a j 七的生成函数；通过推广陈永川等关于普通 排列的组合方法，我们还得到了染色排列的口- 错排数此外，通过标号分拆我 i 摘要 们又给出了关于m a j o r 指标的g e s s e l - s i m o n 公式和a d i n - g e s s e l - r o i c h m a n 公式 的对合证明 最后，我们在附录中给出了e u l e r 公式和h e i n e 变换的证明 关键词：分拆，e u l e r 分拆定理，l e b e s g u e 恒等式，标号分拆，染色排列，g - 错 排数 i i a b s t r a c t a b s tr a c t t h eo b j e c t i v eo ft h i st h e s i si st og i v ed i r e c tc o m b i n a t o r i a lp r o o f so fp a r t i t i o n i d e n t i t i e s ，i n c l u d i n gb i j e c t i v ep r o o fo fe u l e r sp a r t i t i o nt h e o r e m ，i n v o l u t i v ep r o o f o ft h el e b e s g u ei d e n t i t y m o r e o v e r ，w eu s et h ec o n c e p t i o no fl a b e l e dp a r t i t i o n s t og e ts o m er e s u l t so fs o m ei n d i c e so fc o l o r e dp e r m u t a t i o n s t h i st h e s i si so r g a n i z e da sf o l l o w s i nc h a p t e r1 ，w eg i v et h eb a c k g r o u n d o fp a r t i t i o nt h e o r y , a n di n t r o d u c es o m ed e f i n i t i o n sa n dn o t a t i o n st h a ta r eu s e d t h r o u g h o u tt h et h e s i s m e a n w h i l e ，w ew i l lp r e s e n tt w oo ft h em o s te l e m e n t a l t o o l sf o rt r e a t i n gp a r t i t i o n s ：g r a p h i c a lr e p r e s e n t a t i o no fp a r t i t i o n sa n di n f i n i t e p r o d u c tg e n e r a t i n gf u n c t i o n s c h a p t e r2i sc o n c e r n e dw i t he u l e r sp a r t i t i o nt h e o r e m i n1 7 4 8 e u l e rg a v e h i sf a m o u st h e o r e mo np a r t i t i o n sw i t ho d dp a r t sa n dd i s t i n c tp a r t s s y l v e s t e r p r e s e n t e dh i sc e l e b r a t e db i j e c t i v ep r o o fa n dg a v es y l v e s t e r sr e f i n e m e n to fe u l e r s p a r t i t i o nt h e o r e m t h e r ea r eo t h e rr e f i n e m e n t so fe u l e r sp a r t i t i o nt h e o r e md u e t of i n e ，g l a i s h e r ，b o u s q u e t m d l o ua n de r i k s s o n f u r t h e r m o r e ，b e s s e n r o d ta n d z e n gg a v eaf u l ls u m m a r yo fe u l e r sp a r t i t i o nt h e o r e m m o r e o v e rz e n gf o u n d ag e n e r a t i n gf u n c t i o np r o o fo fat h r e e - p a r a m e t e rr e f i n e m e n to fe u l e r sp a r t i t i o n t h e o r e m b yu t i l i z i n gav a r i a n to fb e s s e n r o d t si n s e r t i o na l g o r i t h m ，w ep r e s e n t an e wc o m b i n a t o r i a lp r o o fo ft h eu n i f i c a t i o no ft h er e f i n e m e n t so fg 1 a i s h e ra n d b o u s q u e t m 6 1 0 u - e r i k s s o n c h a p t e r3i sd e v o t e dt ot h el e b e s g u ei d e n t i t y t h el e b e s g u ei d e n t i t yc a n b eo b t a i n e db ye u l e r sf o r m u l a ea n dh e i n e st r a n s f o r m a t i o n i ti sas p e c i a lc a s e o fq - k u m m e r ( b a i l e y - d a u m ) s l l i l lw h i c ha l s oc a nb eo b t a i n e db yh e i n e st r a n s - f o r m a t i o n a l l a d ia n dg o r d o ng a v eab i j e c t i v ep r o o fo ft h eo r i g i n a ll e b e s g u e i d e n t i t y a f t e rt h a t ，b e s s e n r o d tp r e s e n t e dab i j e c t i v ep r o o fo fa ne q u i v a l e n tf o r m o ft h el e b e s g u ei d e n t i t yb yu s i n gs y l v e s t e r sb i j e c t i o n r e c e n t l y , f ug i v e sac o i n - b i n a t o r i a lp r o o fb a s e do nt h ei n s e r t i o na l g o r i t h mo fz e i l b e r g e r w bw i l lp r e s e n t a ni n v o l u t i o nt op r o v et h el e b e s g u ei d e n t i t yb yg e n e r a l i z i n gv a h l e n si n v o l u t i o n i i i a b s t r a c t i nc h a p t e r4 ，w ea p p l yt h ep a r t i t i o nt h e o r yt ot h ee n u m e r a t i o no fs t a t i s - t i ci n d i c e so fc o l o r e dp e r m u t a t i o n s b yu s i n gl a b e l e dp a r t i t i o n s w ed e r i v et h e g e n e r a t i n gf u n c t i o n so ft h ef m a j 如i n d i c e so fc o l o r e dp e r m u t a t i o n s b yg e n e r a l - i z i n gc h e n - x u sm e t h o d ，w eg e tac o m b i n a t o r i a lt r e a t m e n to far e l a t i o no nt h e q - d e r a n g e m e n tn u m b e r s f i n a l l y , w eo b t a i ni n v o l u t i v ep r o o f so fg e s s e l s i m o n f o r m u l aa n da d i n g e s s e l - r o i c h m a nf o r m u l a w ec o n c l u d et h i st h e s i sw i t ht h ep r o o f so ft h ee u l e rf o r m u l aa n dh e i n e s t r a n s f o r m a t i o ni nt h ea p p e n d i x k e y w o r d s ：p a r t i t i o n ，e u l e r sp a r t i t i o nt h e o r e m ，t h el e b e s g u ei d e n t i t y , l a b e l e d p a r t i t i o n ，c o l o r e dp e r m u t a t i o n ，q - d e r a n g e m e n tn u m b e r i v 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 2：!： 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： - ；内部5 年( 最长5 年，可少于5 年) 秘密l o 年( 最长1 0 年，可少于1 0 年) 。机密2 0 年( 最长2 0 年，可少于2 0 年) 。，。，。，。一 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位敝储虢拐扣 伽7 年易其日 1 1 c h a p t e r1 i n t r o d u c t i o n _ - 、 f - 6 。o 1 j o b a s i cd e t i n i t i o n sa n qn o t a t l o n s c o n s t r u c t i v ep a r t i t i o nt h e o r yi sa ni m p o r t a n te m b r a n c h m e n to fe n u m e r a t i v ec o r n - b i n a t o r i c s f o rm o r ed e t a i l so fe n u m e r a t i v ec o m b i n a t o r i c s ，o n ec o u l ds e es t a n - 1 e y 5 8 t h e r ea r em a n yc l a s s i c a la n di m p o r t a n tr e s u l t s i np a r t i t i o nt h e o r y , w h i c hi n f l u e n c e dt h ed e v e l o p m e n to fe n u m e r a t i v ec o m b i n a t o r i c si nt h et w e n t i e t h c e n t u r y t h et h e o r yo fp a r t i t i o na sas u b j e c ts t a r t e dw i t he u l e r sc e l e b r a t e dt r e a r t i s ef 2 7 1 i n1 7 4 8 ，e u l e rp r o v e dav a r i e t yo fp a r t i t i o ni d e n t i t i e s ，m o s tn o t a b l y e s p e c i a l l yt h ee u l e r sp a r t i t i o nt h e o r e ma n dt h ep e n t a g o n a lt h e o r e m i nt h e n e x t2 6 0y e ! a r sal o to fp a r t i t i o ni d e n t i t i e sw e r ep r o v e db ym a n yg r e a tm a t h e - m a t i c i a n ss u c ha sc a y l e y , g a u s s ，c a u c h y , h a r d y , j a c o b i ，l a g r a n g e ，l e g e n d r e ， l i t t l e w o o d ，r a d e m a c h e r ，r a m a n u j a n ，s c h u r ，a n ds y l v e s t e r t h em e t h o do fp r o v i n gp a r t i t i o ni d e n t i t i e s “c o n s t r u c t i v e l y w a sp i o n e e r e d b ys y l v e s t e ri n 5 9 1 t h em e t h o dw a sl a r g e l ya c c e p t e da f t e rt h ef a m o u si n v o - l u t i o ng i v e nb yf r a n k l i n ( 3 3 ，w h ow a sas t u d e n to fs y l v e s t e ra tj o h n sh o p k i n s u n i v e r s i t y r i g h tn o wa l o to fc o m b i n a t o r i a lp r o o f so fp a r t i t i o ni d e n t i t i e sh a v e b e e np u b l i s h e db e c a u s eo ft h e i rb e a u t i f u la n de l e g a n tp r o o f s f o rm o r ed e t a i l s ， s e e 5 5 】t h em a i nc o n t r i b u t i o no ft h i st h e s i si s ap a r to fp r o g r e s si nc o m b i - n a t o r i a lp r o o f so fp a r t i t i o ni d e n t i t i e s l e tu sg i v ea no v e r v i e wo fab a c k g r o u n da n df o r m a ld e f i n i t i o n so fs o m e t e r m i n o l o g i e s w ew i l lf o l l o wt h ec o m m o nn o t a t i o n so i lp a r t i t i o n su s e di na n d r e w s 【7 ，1 2 ，p a k 【5 4 ，5 5 a n dg a s p e ra n dr a h m a n 3 6 d e f i n i t i o n1 1 1ap a r t i t i o n 入o fop o s i t i v ei n t e g e r 佗诂af i n i t en o n i n c r e a s i n g s e q u e n c eo yp o s i t i v ei n t e g e r s s u c ht h a t ：1 九= n 入= ( 入1 ，入2 ，入r ) t h ee 1 1 t r i e s 入ta r ec a l l e dt h ep a r t so f 入，a n d 入li s t h el a r g e s tp a r t t h e d u m b e ro fp a r t so f 入i sc a l l e dt h el e n g t ho f 入，d e n o t e db y2 ( 入) t h ew e i g h to f 入 i st h e8 u mo fi t sp a r t s ，d e n o t e db yi 入1 ap a r t i t i o n 入c a na l s ob er e p r e s e n t e di n t h ef o l l o w i n gf o r m 入= ( 1 m 1 2 m 2 3 m 3 ) ， w h e r em li st h em u l t i p l i c i t yo ft h ep a r tii n 入 d e f i n i t i o n1 1 2l e tp ，v ( n ) a n dp ( n ) d e n o t e 饶es 酣d ，a l lp a r t i t i o n s ，t h es e t o fp a r t i t i o n so yn ，a n dt h en u m b e ro fp a r t i t i o n so yn ，r e s p e c t i v e l y e x a m p l e 上i 3o b v i o u s l y ， a r e5p a r t i t i o n so y4 ，i e ， w eh a v e p ( ) = 0 f o ra n y p ( 4 ) = 5 ，w h i c ha r e n e g a t i v ei n t e g e rn a n dt h e r e ( 4 ) ，( 3 ，1 ) ，( 2 ，2 ) ，( 2 ，1 ，1 ) ，( 1 ，1 ，1 ，1 ) w ec a nr e w r i t et h ea b o v e5p a r t i t i o n sa sf o l l o w s ： ( 4 1 ) ，( 1 1 3 1 ) ，( 2 2 ) ，( 1 2 2 1 ) ，( 1 4 ) t w ok i i l d so fs e t so fp a r t i t i o n st h a t a r eo f t e ns t u d i e da r e0t h es e to fa l l d a 毗i t i o 璐w i t ho d dp a r t sa n ddt h es e to fa l lp a r t i t i o n sw i t hd i s t i n c t p a r t s s 如血l 牡l v w ed e n o t et h es e to fp a r t i t i o n so fnw i t ho d dp a r t sw h i c h i sas u b s e to f o ( r e s p 口) b yo ( n ) ( r e s p 口( 佗) ) e x n m p l ej j 彳t h e r ea r e2p a r t i t i o n si no ( 4 ) a n d 4p a r t i t i o n si nd ( 6 ) ? 0 ( 4 ) = ( 3 ，1 ) ，( 1 ，1 ，1 ，1 ) ) a n d d ( 6 ) = ( 6 ) ，( 5 ，1 ) ，( 4 ，2 ) ，( 3 ，2 ，1 ) ) hd t h e rw o r d s ，w eh a v ep ( 4 1o d dp a r t s ) = 2a n dp ( 6 d i s t i n c tp a r t s ) = 4 2 砌口 t nh 以 川陋璐。p僦时 胛妇枷皿羔柚鲫出 坨 叭让e协喊以曲妣骶 e l 喊帆怒 眦见研甙w 慨 堍壮“m嚣 的 c h a p t e r1 i n t r o d u c t i o n 1 2 g r a p h i c a lr e p r e s e n t a ti o n o id a r t i t i o n s o n ee f f e c t i v ee l e m e n t a r yd e v i c ef o rs t u d y i n gp a r t i t i o n si st h eg r a p h i c a lr e p r e s e n - t a t i o n ，w h i c hi se x t r e m e l yu s e f u li nd e a l i n gw i t hp a r t i t i o n s t h e r ea r et w ow a y st or e p r e s e n t g r a p h ，a n dt h eo t h e ri st h ey o u n g d i a g r a m s ap a r t i t i o ng r a p h i c a l l y o n ei st h ef e r r e r s d i a g r a m i nt h i st h e s i s ，w ea d o p ty o u n g f o rt h ep a r t i t i o n ( 5 ，3 ，3 ，2 ，1 ) ，w ea s s o c i a t ei tw i t ht h ef o l l o w i n gy o u n gd i a - g r a ma si nf i g u r e1 2 1 f i g u r e1 2 1 ：t h ey o u n gd i a g r a mo fp a r t i t i o n ( 5 ，3 ，3 ，2 ，1 ) d e f i n i t i o n1 2 1f o re a c hp a r t i t i o n 入，t h ec o n j u g a t ep a r t i t i o no f 入i sd 币礼甜a s 入7 =( 入j ，遐， x ) ， w h e r exi st h en u m b e ro fp a r t so f 入t h a ta r eg r e a t e rt h a no re q u a lt oi w em a yb e t t e rd e s c r i b et h ec o n j u g a t eb yu s i n gg r a p h i c a lr e p r e s e n t a t i o n f r o m t h ed e f i n i t i o n ，i ti sc l e a rt h a tt h ec o n j u g a t eo ft h ep a r t i t i o n 入= ( 5 ，3 ，3 ，2 ，1 ) i s ( 5 ，4 ，3 ，1 ，1 ) ，w h i c hi si nf a c to b t a i n e db yr e f l e c t i n gt h eg r a p hi nt h em a i nd i a g o n a l s e ef i g u r e1 2 2 一 一 一一 廿yu s i n gg r a p h i c a lr e p r e s e n t a t i o nw eh a v e8 0 l et h e o r e m so np a r t i t i o n s t h e o r e m1 2 2t h en u m b e ro fp a r t i t i o n so f 佗w i t ha tm o s tm p a r t se q u a l st h e n u m b e ro fp a r t i t i o n so ni nw h i c hn op a r te x c e e d sm 3 c h a p t e r1 i n t r o d u c t i o n 入7 = ( 5 ，4 ，3 ，1 ，1 ) f i g u r e1 2 2 ：t h ec o n j u g a t ep a r t i t i o n 入7o f ( 5 ，3 ，3 ，2 ，1 ) a p a r t i t i o nai ss e l - c o n j u g a t ei fi t i si t so w nc o n j u g a t e ，i e ，入= 入7 f o r e x a m p l e ，t h es e l f - c o n j u g a t ep a r t i t i o n so f1 1a r e ( 6 ，1 ，1 ，1 ，1 ，1 ) a n d ( 4 ，3 ，3 ，2 ) t h e r ei san a t u r a lt r a n s f o r m a t i o nf r o ms e l f - c o n j u g a t ep a r t i t i o n st op a r t i t i o n s w i t hd i s t i n c to d dp a r t s t h e o r e m1 2 3t h en u m b e ro fs e l f - c o n j u g a t ep a r t i t i o n so fne q u a l st h en u m b e r o fp a r t i t i o n so fnw i t hd i s t i n c to d dp a r t s t h ep r o o fo ft h i st h e o r e mw o u l db eag o o de x a m p l et os h o wh o wc o m b i n a - t o r i a lp r o o f sw o r k s p m o f g i v e nas e l f - c o n j u g a t ep a r t i t i o nao f 扎d e n o t et h en u m b e ro fs q u a r e si n t h ef i r s tr o wa n dt h ef i r s tc o l u m nb yh i ( a ) t h e nw er e m o v et h e s eh l ( a ) s q u a r e s f r o mt h eg r a p h i c a lr e p r e s e n t a t i o no f 入s i n c e 入i ss e l f - c o n j u g a t e ，h l ( a ) i sa no d d n u m b e r w ed e l e t eas y m m e t r i c a ls t r u c t u r ef r o mas y m m e t r i cg r a p h i c a lr e p r e - s e n t a t i o n t h e nt h er e m a i n i n gp a r t i t i o ni ss t i l ls y m m e t r i c ，i e ，s e l f - c o n j u g a t e w ed e n o t et h en u m b e ro fs q u a r e si nt h ef i r s tr o wa n dt h ef i r s tc o l u m no ft h e r e m a i n i n gp a r t i t i o nb yh 2 ( a ) a n dr e m o v et h e s e 2 ( 入) s q u a r e sa g a i n a n di t i s e a s yt ov e r i f yt h a t 危1 ( 入) 2 ( 入) w ec o n t i n u et h ea b o v ep r o c e s su n t i lt h e r ei sn os q u a r e s s u p p o s ef i n a l l yw e o b t a i nas e q u e n c eo fn u m b e r s ( h i ( a ) ， 2 ( 入) ，九蠡( 入) ) t h e n p ：= ( h i ( a ) ， 2 ( 入) ，h k ( a ) ) i st h ec o r r e s p o n d i n gp a r t i t i o nw i t hd i s t i n c to d d p a r t s 4 瀚= 絮：蔓；熙n 、a 篡廿? 沁，研t hd i s t i n c t 。d dp 吼s ，w ec 髓- ，蹴帆rt h ep 吼i t j o naw h i c hi 8 s e l f - c 。n j u g a t e ”“u m q u e l y _ 蒜1 2 4 g i v e n a ，s ，e l f - r c o n 蹦j u g a t e p a r t i t i o na = ( 4 ，4 ，2 ，2 ) o f1 2din ，加e9 e耽egp a r t i t i o n 耽印佗 p = ( 7 ，5 ) s e ef z g 让陀1 2 舅。”尸 删c 眦w 圮 f i 舭e1 2 3 ：as e l f - c o n j u g a t ep a r t i t i 。n 入：( 4 ，4 ，2 ，2 ) o f 1 2 1 3 g e n e r a t i n gf u n c t i o n s 1 3 1 g e n e r a t i n gf u n c t i o n so fo n e v a r i a b l e ，q ) o = 1 ， ，g ) 死= ( 1 一z ) ( 1 - x q ) ( 1 一z g n 一1 ) ： ( z ，g ) = 一l i m 。( x ；q ) 付= 竹 口r 9 8 = q r + 8 5 竹1 i i ( 1 一z 矿) ，佗1 ， 嘲 矸c g耋| 攀 h 酏蟾玩蒜 m 吼= 璐耐 h a 呲姆 ? 舰高 唱 &9 宝j慧姐m 酏研慨如 蚰吣 眠星时 o = z一1 l 触 叭慨 0 v 。l 、 ， t 江y ：善脚炽 m h 地如魄觚唱遍n 1 ， st 一 a h 篙一 m 桫 e l p舰帅 n u 1 呛y k 吖酬 酬8 巾t 口