（应用数学专业论文）major+index+and+inversions+on+permutations+or+derangements.pdf

1 摘要 对排列上的统计量的研究是组合数学中的经典课题，至今依然十分活 跃而在这些统计量中最重要的就是m a j o ri n d e x 和i n v e r s i o n 本文在前人 的基础之上对这两个统计量又进行了进一步的研究首先利用数学归纳法这 一古老的数学方法，通过插入和调整的办法给出了m a j o ri n d e x 和i n v e r s i o n 之间一个简便的一一对应。当限制在错排( d e r a n g e m e n t ) 上时，w a c h s 1 9 1 得到了一个关于m a j o ri n d e x 的递推关系式，本文给出了这个递推式的两种 新的证明方法；更进一步，m a j o ri n d e x 和i n v e r s i o n 在错排上的对应关系也 更加明朗此外，本文在背景部分详细介绍了该方面的许多研究成果以及他 们在相关方面的应用，在最后部分也提封了一些有待解决的问题 关键词：双射，反序数，主序数，生成函数，归纳法，错排，分拆 a b s t r a c t s e a r c h i n gb i j e c t i o n sb e t w e e nm a j o ri n d e xa n di n v e r s i o n si sac l a s s i c a l a n da c t i v ep r o b l e mi ne n u m e r a t i v ec o m b i n a t o r i c s m a n yr e s u l t sh a v e b e e no b t a i n e da b o u tm a j o ri n d e xa n di n v e r s i o n s ，i n c l u d i n gs o m eb i j e c - t i o n s ，o rt h e i rr e s t r i c t i o no nd e r a n g e m e n t s i nt h i st h e s i s ，w ep r e s e n t o n en e wb i j e c t i o nb e t w e e nt h e mb yi n d u c t i o n a l s oar e c u r s i o no f m a j o ri n d e xo nd e r a n g e m e n t ，w h i c hw a sf i r s tp r o v e db yw a c h s 【1 9 i s p r o v e d i na n o t h e rt w ow a y s b a s eo n t h e s e ，w ea l s os e et h er e l a t i o n sb e - t w e e n d e r a n g e m e n ta n dd e s a r a n g e m e n t ，w h i c hi m p l i e so t h e rb i j e c t i o n s b e t w e e nm a j o ri n d e xa n di n v e r s i o n w e b e g i nw i t ht h er e l a t i n gr e s u l t sa n db a c k g r o u n d sa n de n dw i t hs o m e o p e np r o b l e m s k e y w o r d s ：b i j e c t i o n ，i n v e r s i o n ，m a j o ri n d e x ，g e n e r a t i n gf u n c t i o n ，i n 。 d u c t i o n ，d e r a n g e m e n t ，d e s a r a n g e m e n t ，p a r t i t i o n 3 2b a c k g r o u n d s a n dn o t a t i o n s t h es y s t e m a t i cr e s e a r c ho fs t a t i s t i c so np e r m u t a t i o n sb e g a nf r o m 【1 5 】 m a c m a h o n 1 5 】s t u d i e d f o u rs t a t i s t i c so nt h ep e r m u t a t i o ng r o u ps n ；d e s c e n t s ( d e s ) 、e x c e e d s ( e x c ) 、i n v e r s i o n s ( i n v ) 、m a j o ri n d e x ( m a j ) d e f i n i t i o n2 1l e t7 r = 丌1 丌2 nb ea n ye l e m e n to & ， i f7 1 i 7 1 i + 1 ，w ec a l lia sad e s c e n to f 丌； 王f i = 礼， o r1s i n l ，仉 i ，ii sa ne x c e e do f 丌； i f m 7 0 ，i t f i + 1 ) ，e x c ( t r ) = # i l l r , e ) ； i n v o r ) = 带 ( i ，j ) l i 乃 ，m a j ( ，r ) = 。，。+ 。i w h e r ei n vi st h ei n v e r s i o nn u m b e ro f 丌m a ji st h em a j o ri n d e xo f7 r i n a d d i t i o n ，w ed e n o t ed l ( 7 r ) = i l i f ，啦 a i + 1 ) ，d e s ( 7 r ) = d l ) a st h e s e to fd e s c e n t so f7 r n e t t o ，m a c m a h o no b t a i n e dt h eg e n e r a t i n gf u n c t i o n s o fi n v ，m a j r e s p e c t i v e l y ： q l n v ( ”) = 【1 【2 】- 【n 】， ( 2 1 ) - olj 、7 w e s 4 f q m a j ( ”) = 1 】 2 m( 2 2 ) _ 一 w w h e r e 【n = 1 十q + 口2 + + 矿一1 = ( 1 一q “) ( 1 一q ) u s i n ga l g e b r a i c m e t h o d s ，m a c m a h o np r o v e dt h a ti n v 、m a jh a v et h es a m ed i s t r i b u t i o n o n s op e o p l ec a l lt h es t a t i s t i c st h a th a v et h es a m ed i s t r i b u t i o nw i t hi n v a s “m a h o ns t a t i s t i c ” s o o n ，t h er e s e a r c h0 1 1m a h o ns t a t i s t i ce x t e n d st om u l t i s e t am u l t i s e t s ( 1 ”1 2 ”2 r ”7 1 ( o rs i m p l yb y s ) i sc o m p o s e db y j 1i s 、m 22 s 、 o fi n va n dm a jo nm u l t i s e tsa r e 薹矿“州= i m ，瓮j s o一一 4 r e f e r st oas e te a c ho fw l o s ee l e m e n t s 、 br0 t h eg e n e r a t i n gf u n c t i o n s ：_ = 摭， 。， m ，j( g ) 。( g ) 。， 薹a “珈) = “，三一j ：，1 ( z t ， t h e r ea r em a n y w a y st op r o v e ( 2 3 ) ，i n c l u d i n gan u m b e ro fb e a u t i f u lc o r n b i n a t o r i a lp r o o f s o n ec a nr e f e rt o 【1 7 ，p 2 7 ，o r 【2 ，p 4 1 】f o rs o m e a tl e a s t t om y k n o w l e d g e ，t h e r ei so n l yo n ec o m b i n a t o r i a lp r o o fo f ( 2 4 ) ，t h ep h d t h e s i so ft h ec o m b i n a t o r i a lm a t h e m a t i c i a nr p s t a n l yi sa b o u tt h ee x t e n s i o no ft h i sk i n do f m e t h o d s ( s e e 【1 7 ，p 2 1 6 d b e f o r ei n t r o d u c i n gt h em e t h o d ， w en e e daf e wc o n c e p t so np a r t i t i o n s d e f i n i t i o n2 2a p a r t i t i o na i sas e q u e n c e o f n o n n e g a t i v ei n t e g e r s ( a 1 ，a 2 ， s u c ht h a ta l a 2 2 d e n o t ei a j = a 1 + a 2 + - + 丸， c a l l e dt h e w e i g h t 万天；j ( a ) ：t ，c a l l e dt h el e n g t h 酊a i l n = 1 a l ，w ea l s os a yt h a t 入i so p a r t i t i o no f n d e n o t e db ya 卜n d e n o t e 焉= 川z ( a ) m ，a i 扎) o n e c a nr e f e rt of 1 7 ，p r o p o s i t i o n1 3 1 9 】 o r 【2 】f o rt h ef o l l o w i n gg e n e r a t i n gf u n c t i o n ： 到刈= 酬 皿s ， 糯 。 i fm + o 。w eh a v et h eg e n e r a t i n gf u n c t i o no f p a r t i t i o n sw h o s ee a c hp a r t n ： q 陋l l 茎“ ( g ) 二1( 2 6 ) t h a t sa l s ot h eg e n e r a t i n gf u n c t i o no fp a r t i t i o n sw h o s e l e n g t h n t h ec o m b i n a t o r i a lp r o o f o f ( 2 4 ) c a nb ep r e s e n t e da sf o l l o w s t r a n s f o r m ( 2 4 ) a s 糕= 而杀丽 ( 2 ，) ( 口) m 。+ m 2 + + 。，( g ) m 。( g ) 。( g ) 。， 、 ( g ) = i st h eg e n e r a t i n gf u n c t i o nf o rp a r t i t i o n sw i t ha tm o s tm p a r t s e a c h p a r t i t i o nw i t ha tm o s tm ip a r t s ( p o s i t i v e ) c o r r e s p o n d st oap a r t i t i o nw i t h e x a c t l ym n o n n e g a t i v ep a r t s ( j u s tf i l l i nt h en e c e s s a r yn u m b e ro fz e r o s ) t h e r e f o r e ( g ) 二：( 口) 磊：国) 二：i st h eg e n e r a t i n gf u n c t i o no f rp a r t i t i o n sw i t h e x a c t l ym 1 ) m 2 ，m rn o n n e g a t i v ep a r t sr e s p e c t i v e l y a n d ( g ) m - 1 1 + + m ，i s 5 ) t h eg e n e r a t i n gf u n c t i o no f p a r t i t i o n sw i t he x a c t l ym l + - - + m ，n o n n e g a t i v e p a r t s c o n s i d e r i n gt h ec o e f f i c i e n t so f 叮o ft h et w os i d e so f ( 2 7 ) ，w eh a v et o f i n dt h eb i j e c t i o nf r o mp a i r s ( a ，丌) t ot h e f o l l o w i n gm a t r i x a l l a 2 1 a 1 2 口2 2 a l t o ，0 a 2 m 2 o ( 2 8 ) a r l 口r 2 a ，。0 w h e r eah a se x a c t l ym l + m 2 + + m r n o n - n e g a t i v ep a r t s 。7 r s ，a n d t + o n = m a j ( 7 r ) + 一 i = i w ed i v i d et h eb i j e c t i o ni n t ot w o p a r t s t h ef i r s to n ei s ( a ，丌) h ( a o ，7 r ) s u c ht h a ti f 吼 7 r t + it h e n 硼 豫1 ，a n d a i + m a j ( t r ) = i a o t h i ss t e pi sa l s ot h ec r i t i c a lp a r t s u p p o s ea = ( a 1 ，a 2 ，- - ，a m l _ + m ) ( i f f ( a ) o n ) a so r l 一1 ，t h u sw eg e tan e w p e r m u t a t i o n 盯7 k 一1 o nt h eo t h e rh a n d ， e a c h 口既一1 c a nb eo b t a i n e df r o m 几d i f f e r e n t 盯s ( e 晶) ，a sl o n ga s 口如一l ；盯7 = “一1 ，c 孤b eo b t a i n e df r o mn 一1d i f f e r e n t 口s ( e 既) t h e n w e g e t i 磊i = n i 晶一1 l + ( - 1 ) “( 2 1 1 ) n o w ，l e t sc o n s t r u c tt h eb i j e c t i o n ：d nh 昂s u p p o s e0 - d n p e r f o r mc y c l ed e c o m p o s i t i o n ( s e e 1 7 ，p 1 7 ) o n 盯a n dp u tt h es m a l l e s te l e m e n t o fe a c hc y c l ei nt h es e c o n dp l a c e a tl a s t ，a r r a n g et h e s ec y c l e ss ot h a tt h e s m a l l e s te l e m e n t sa r ei nd e c r e a s i n go r d e r t h e nl e t 毋( 口) b et h ep e r m u t a t i o n o b t a i n e db yd r o p p i n gt h ep a r e n t h e s e so fc y c l e s f o re x a m p l e ，o r = 2 6 4 3 1 5 8 7 ， a f t e rc y c l ed e c o m p o s i t i o na n dr e a r r a n g e m e n tw eh a v e 口= f 8 7 ) ( 4 3 ) ( 5 1 2 6 ) t h e n 审( 口) 一8 7 4 3 5 1 2 6 o b v i o u s l y , ( 口) 。e 。i t sa l s oe a s yt oi n v e r tt h e p r o c e s s w i t ht h eb i j e c t i o nb e t w e e nd na n d 正k ，i ti sc l e a rt og e t ( 2 1 0 ) f r o m ( 2 1 1 ) s u p p o s et h en o n - f i x e dp o i n t so f 7 ra r ep l ，p 2 ，p k t h e d e r a n g e m e r i tp a r to fap e r m u t a t i o n7 r ，d e n o t e d d p ( 7 r ) ，i s d e f i n e da sap e r m u t a - t i o n o n 1 ，2 ，) i n t h eo r d e ro f 丌p 1 ，丌p 2 ，唧k f o r e x a m p l e ，7 r = ( 1 ，5 ，3 ，7 ，6 ，2 ，9 ，8 ，4 ) ，t h en o n f i x e dp o i n t so f t ri s 2 ，4 ，5 ，6 ，7 ，9 ) t h e nd p ( 7 r ) = r e d u c t i o no f ( 5 ，7 ，6 ，2 9 ，4 ) = ( 3 ，5 ，4 ，1 ，6 ，2 ) w h e r e ，t h em e a n i n go f ”r e d u c t i o no fas e tr ”i st or e p l a c et h es m a l l e s te l e m e n to fra s1 t h es e c o n ds m a l l e s t e l e m e n ta s2 ，一，a n ds oo n w ep o i n to u tt h a td 扫( 丌) d k o nt h eo t h e rh a n d ，g i v e n ”& ，w ec a ni n s e r taf i x e dp o i n tj ( 1 j k + 1 ) i n t o 丌t og e tan e wp e r m u t a t i o n7 r 7 & + l ： ”= ”i 吒吒一- j 弓s k + 8 w h e r e7 r ：= 丌 i f 吼 f ( a ) ) l e ti = 1 ，d o 1 ) s u p p o s et h e r ea r ee x a c t l yjd e s c e n t si n7 r ，d e s ( ”) = 妇l ，p 2 ，功) d e n o t ek = 凡a n dc o n s i d e rt h ef o l l o w i n gt h r e ec a s e s ： c a s e1 ：k = 0 j u s ti n s e r to n ert ot h ee n do f7 r c a s e2 ：1 j i n s e r to n eri n t o ”a tt h ep o s i t i o np j k + l + 1 c a s e3 ：七 j s e tp 0 = 一1 ，p j + i = 。n o t et h a tp t f + 1i sa ni n c r e a s i n g f u n c t i o no nf t h e r ee x i s t ss o m eu n i q u et ( o f j ) s u c ht h a t p f f + 1 i h e n c eo n c es o m e 九s a t i s f i e sc a n elo r2 ，w en e e dn o tc o n s i d e r c a s e3 f o ra l l ) i nc a s e3 ，i ti ss u f f i c i e n tt os h o wt h a tt h ep o s i t i o nk j 十fi e a d st oai l e w d e s c e n t ，d e s ( _ 7 r ) = p l ，一，p t ，k j + f ，p t + a + 1 ，功+ 1 ) ，a n dt h e r e f o r e t h em a j o ri n d e xo f ”i n c r e a s e s ( k j + f ) 十0 一f ) = k t h i sc a nb ed o n eb yi n d u c t i o no i li i fa 1b e l o n gt oc a s e3 ，t h ep o s i t i o no f rb e i n gi n s e r t e di n t o7 ri so b v i o u s l yad e s c e n ts i n c eri st h eu n i q u em a x i m a l e l e m e n ti n 丌s u p p o s et h ea t b e l o n g st oc a s e3a n dt h e r ei s au n i q u ei i s a t i s f y i n g ( 3 5 ) a f t e ri n s e r t i o n d e s ( 7 r ) = ( p l ，p t ，九一j + f ，矶十l + 1 ，一，聊+ 1 ) = 如：，p ：，一，巧，蟛+ 1 ) w h e r e 矾= p l ，- ，p ：。= p l l ，p t 十l = 凡一j + k ，p ，。+ 2 = p 。+ 1 + i ，p ；+ 1 = p j + 1 ，a n d a l s os u p p o s e t h a t t h e r e i sn or i n f r o n to f 一j + l i n o w ，i f a i + l a l s ob e l o n gt oc a s e3 ，t h e nt h e r ee x i s t sau n i q u ef + 1s u c ht h a t w eh a v e d 。+ 1 一f 件1 + 1 a 件1 一( j + 1 ) p ：l + 1 一f 件1 a 件1 一( j + 1 ) 九一j 一1 = p ：。十l 一( 如+ 1 ) p ：。+ 1 一如 h e n c e2 t + 1 “a n d a t + 1 一( j + 1 ) + l i + ls 九一( j + 1 ) + k = ( a ，一j + “) 一1 1 2 t h a ti st os a y , t h e ( i + 1 ) 一t hri si n s e r t e ds t r i c t l yi nf r o n to ft h ei - t hr ( i ft h e y a r ca l lb e l o n gt oc a s e3 ) t h e r e f o r ea 件1 一( j + 1 ) + f 件1i san e wd e s c e n t t h ep r o o fi sf i n i s h e d i r e m a r k a c c o r d i n gt h ep r o o fa b o v e ，t h ep o s i t i o n so f rb e i n gi n s e r t e di n t o7 r f i r s t l yd e c r e a s e ( b e l o n g i n gt oc a s e3 ) ，a n dt h e ni n c r e a s e ( b e l o n g i n gt oc a s e2 o r1 ) c o n s i d e rt h ei n v e r s ec o r r e s p o n d e n c e g i v e n7 r s r ，l e t 盯= 7 r ，i = m i n i t i a l l ya n dd o t h ef o l l o w i n gp r o c e s su n t i li = 0 1 ) s u p p o s et h ep o s i t i o n so fra x e p l ，p 2 ， ( 1 p l f ( a ) ： 1 ) s u p p o s e t h e r ea r ejd e s c e n t si n7 r ，d e s ( 7 r ) = p 1 ，p 2 ，功) ，o n ea n d o n l yo n eo ft h et h r e ec a s e so c c u r ， i 九= 0 。珏t h i sc a s eh a p p e n ，j u s ti n s e r ta f i x e dp o i n t ( 丌) 十li n t o 丌，i e ， 7 r = ( 7 r ，f ( 丌) + 1 ) ，w h e r ej ( 7 r ) d e n o t et h el e n g t ho f 7 r i i 0 j s e tp 0 = - 1 ，功+ 1 = o o n o t et h a tp l f + 1i s a ni n c r e a s i n g f u n c t i o no nj t h