Séminaire Lotharingien de Combinatoire 67 (2012), Article B67c A SYMMETRICAL q-eulerian IDENTITY GUO-NIU HAN, ZHICONG LIN, AND JIANG ZENG Abstract. We

Size: px

Start display at page:

Download "Séminaire Lotharingien de Combinatoire 67 (2012), Article B67c A SYMMETRICAL q-eulerian IDENTITY GUO-NIU HAN, ZHICONG LIN, AND JIANG ZENG Abstract. We"

山潘
4 years ago
Views:

1 Sémiaire Lotharigie de Combiatoire 67 (2012), rticle B67c SYMMETRICL -EULERIN IDENTITY GUO-NIU HN, ZHICONG LIN, ND JING ZENG bstract. We fid a -aalog of the followig symmetrical idetity ivolvig biomial coefficiets ( m) ad Euleria umbers,m, due to Chug, Graham ad Kuth J. Comb., 1 (2010), 29 38: ( ) a + b,a 1 ( ) a + b,b We give two proofs, usig geeratig fuctio ad bijectios, respectively Itroductio The Euleria polyomials (t) are defied by the expoetial geeratig fuctio (t) z (1 t)ez! e zt te. (1.1) z The classical Euleria umbers, are the coefficiets of the polyomial (t), i.e., (t) 0,t. Recetly, Chug, Graham ad Kuth 2 oticed that if we modify the value of 0 (t), which is 1 by (1.1), by taig the covetio that 0 (t) 0,0 0, the the followig symmetrical idetity holds: ( ) a + b,a 1 ( ) a + b,b 1 (a, b > 0). (1.2) 0 0 Euivaletly, istead of (1.1), we defie the Euleria polyomials by the geeratig fuctio 0 (t) z! (1 t)ez e zt te z 1 ez e tz e zt te z. (1.3) t the ed of 2, the authors ased for, amog other usolved problems, a -aalog of (1.2). The aim of this paper is to give such a extesio ad provide two proofs, of which oe is aalytical ad aother oe is combiatorial. We first itroduce some -otatios. The -shifted factorial (z; ) is defied by (z; ) : 1 i0 (1 zi ) for ay positive iteger ad (z; ) 0 1. The -expoetial fuctio e(z; ) is defied by e(z; ) : 0.

2 2 GUO-NIU HN, ZHICONG LIN, ND JING ZENG Several -aalogs of (1.1) have bee proposed i the literature (see 6). Ispired by the recet wor of Shareshia ad Wachs 6, we cosider the followig -aalog of (1.3): (t, ) 0 e(z; ) e(tz; ) e(tz; ) t e(z; ). (1.4) The -Euleria polyomials (t, ) have may remarable properties aalogous to Euleria polyomials, see Shareshia ad Wachs 6 ad Foata ad Ha 4. The -Euleria umbers, () are the defied by (t, ), ()t ( 0). The first few terms of, () are 0 0,0 () 0, 1,0 () 1, 2,0 () 1, 2,1 () 1, 3,0 () 1, 3,1 () , ad 3,2 () 1. lso, replacemet of t by t 1 ad of z by tz i (1.4) yields that t (t 1, ) t (t, ). Thus we have the symmetrical property, (), 1 (). (1.5) Recall that the -biomial coefficiets are defied by : for 0, (; ) ad 0 if < 0 or >. The followig symmetrical idetity ivolvig both the -biomial coefficiets ad -Euleria umbers, () is a true -aalog of (1.2). Theorem 1. For ay positive itegers a ad b, we have the -symmetrical idetity a + b,a 1 () a + b,b 1 (). (1.6) 0 0 We shall first give a geeratig fuctio proof of (1.6) i Sectio 2 ad the a combiatorial proof i Sectio 3. We coclude the paper with some further extesios ad remars. It follows from (1.4) that 2. geeratig fuctio proof of (1.6) ( ) e(tz; ) t e(z; ) (t, ) (; ) 0 (1 t )z (; ). (2.1)

3 SYMMETRICL -EULERIN IDENTITY 3 Now, ad e(tz; ) (t, ) (tz),i ()t i (; ) 0 (; ) (; ),i +,i ()t i+ +,,i +,i ()t i,,,i t e(z; ) (t, ) t z,i ()t i (; ) 0 (; ) (; ),i +,i ()t i+1 +,,i +,i 1 ()t i.,,i Substitutig the last two expressios i (2.1) ad idetifyig the coefficiets of t i / o both sides, we obtai,i () 1, if i 0,,i 1 () 1, if i 0, 0, otherwise. Settig i a, a + b, ad usig the symmetrical property (1.5), we obtai (1.6). We ca also derive -aalogs of other idetities i 2. For example, let H (t; ) t i i be the Rogers-Szegő polyomials, see 1, p. 49. The i0 e(tz; )e(z; ) 0 H (t; ). If we multiply (1.4) by e(tz; ) 2 t 2 e(z; ) 2 (e(tz; ) + te(z; ))(e(tz; ) te(z; )), the the right-had side is eual to (e(tz; ) + te(z; ))(e(z; ) e(tz; )) ((1 t)h (t; ) + (t t )H (1; )). (; ) 0

4 4 GUO-NIU HN, ZHICONG LIN, ND JING ZENG O the other had, we have ad (e(tz; )) 2 (t, ) (; ) 0,i, t 2 (e(z; )) 2 (t, ) (; ) 0,i, H (1; ) H (1; ),i ()t i,,i 2 ()t i. Hece, idetifyig the coefficiets of t i / i these expressios, we arrive at H (1; ),i () H (1; ),i 2 () H (1; ), if i 1, + H i i 1 (1; ), if i 1, 0, otherwise. Of course, we ca also multiply (1.4) by e(tz; ) r t r e(z; ) r for ay iteger r 1 ad derive a -aalog of the more geeral (ad complicated) idetity i combiatorial proof of (1.6) For each permutatio π π 1 π 2... π of : {1,..., }, defie the followig four statistics: exc(π) : {i : 1 i, π i > i} ; des(π) : {i : 1 i 1, π i > π i+1 } ; maj(π) : π i >π i+1 i; iv(π) : {(i, j) : i < j, π i > π j } ; called umber of excedaces, umber of descets, major idex ad iversio umber, respectively. It is well-ow that the Euleria umber, couts the umber of permutatio of with descets or excedaces. Let S be the set of permutatios of. Shareshia ad Wachs 6 prove that (t, ) π S (maj exc)π t exc π. For our purpose we shall use aother iterpretatio of (t, ) due to Foata ad Ha 3,4. This iterpretatio is based o Gessel s hoo factorizatio of permutatios 5, which we recall ow. word w x 1 x 2... x m is called a hoo if x 1 > x 2 ad either m 2, or m 3 ad x 2 < x 3 <... < x m. Clearly, each permutatio π π 1 π 2... π admits a uiue factorizatio, called its hoo factorizatio, pτ 1 τ 2... τ r, where p is a icreasig word ad

5 SYMMETRICL -EULERIN IDENTITY 5 each factor τ 1, τ 2,..., τ is a hoo. To derive the hoo factorizatio of a permutatio, oe ca start from the right ad factor out each hoo step by step. For each i let iv τ i deote the umber of iversios of τ i ad defie lec(π) : iv(τ i ). (3.1) 1 i For example, the hoo factorizatio of π is Hece p , τ , τ , τ ad lec(π) iv( ) + iv(8 6 7) + iv( ) 7. Let pτ 1 τ 2... τ r be the hoo factorizatio of a permutatio π. Let 0 (respectively i, 1 i r) deote the set of all letters i the word p (respectively i the hoo τ i ). We call 0 cot(p) (respectively i cot(τ i ) (1 i r)) the cotet of p (respectively of the hoo τ i ) ad cotet of π the seuece Cot(π) ( 0, 1,..., r ). The statistic (iv lec)π is eual to the umber of pairs (, l) such that i, l j, > l ad i < j, a umber we shall deote by iv( 0, 1,..., r ). From Foata ad Ha 3, 4, we derive the followig combiatorial iterpretatio: (t, ) π S (iv lec)π t lec π. Therefore, () π S lec π Recall 1 that the -multiomial coefficiet a 0, a 1,..., a (; ) a0 (; ) a1 (; ) a has the iterpretatio a 0, a 1,..., a ( 0, 1,..., ) (iv lec)π. (3.2) iv( 0, 1,..., ), (3.3) where the sum is over all ordered partitios ( 0, 1,..., ) of such that i a i, 0 i. We will give a combiatorial proof of (1.6) usig (3.2) ad (3.3). s a warm-up, we first prove the symmetry property (1.5) by costructig a explicit ivolutio o permutatios. Lemma 2. There is a ivolutio π σ o S satisfyig lec(π) 1 lec(σ), ad (iv lec)π (iv lec)σ.

6 6 GUO-NIU HN, ZHICONG LIN, ND JING ZENG Proof. Let τ be a hoo with iv(τ) ad cot(τ) {x 1,..., x m }, where x 1 <... < x m. Defie d(τ) x m +1 x 1... x m x m x m. Clearly d(τ) is the uiue hoo satisfyig cot(d(τ)) cot(τ) ad iv(d(τ)) m cot(τ) iv(τ). Let τ be a word with iv(τ) ad cot(τ) {x 1,..., x m }, where x 1 <... < x m. Defie d (τ) x m x 1... x m 1 x m x m. Clearly d (τ) is the uiue word satisfyig cot(d (τ)) cot(τ) ad iv(d (τ)) m 1 cot(τ) iv(τ) 1. Let π pτ 1 τ 2... τ r be the hoo factorizatio of π S. If p, let σ d (p)d(τ 1 )d(τ 2 ),..., d(τ r ). If p, let σ d (τ 1 )d(τ 2 )d(τ 3 )... d(τ r ). Sice d ad d are two ivolutios, it is routie to chec that such a mappig is a ivolutio with the reuired properties. For each fixed positive iteger, a two-pix-permutatio of is a seuece of words v (p 1, τ 1, τ 2,..., τ r 1, τ r, p 2 ) (3.4) satisfyig the followig coditios: (C1) p 1 ad p 2 are two icreasig words, possibly empty; (C2) τ 1,..., τ r are hoos for some positive iteger r; (C3) The cocateatio p 1 τ 1 τ 2... τ r 1 τ r p 2 of all compoets of v is a permutatio of. We also exted the two statistics to the two-pix-permutatios by It follows that lec(v) iv(τ 1 ) + iv(τ 2 ) + + iv(τ r ), iv(v) iv(p 1 τ 1 τ 2... τ r 1 τ r p 2 ). (iv lec)v iv(cot(p 1 ), cot(τ 1 ), cot(τ 2 ),..., cot(τ r ), cot(p 2 )). (3.5) Lemma 3. The geeratig fuctio of all two-pix-permutatios v of such that lec(v) s by the statistic iv lec is,s (). (3.6) 0 Proof. By the hoo factorizatio, the two-pix-permutatio v i (3.4) is i bijectio with the pair (σ, p 2 ), where σ p 1 τ 1 τ 2... τ r 1 τ r is a permutatio o \ cot(p 2 ) ad p 2 is a icreasig word. Thus, by (3.2), (3.3), ad (3.5), the geeratig fuctio of all two-pixpermutatios v of such that lec(v) s ad p 2 with respect to the weight (iv lec)(v) is,s (). Lemma 4. There is a bijectio v u o the set of all two-pix-permutatios of satisfyig lec(v) 2 lec(u), ad (iv lec)v (iv lec)u.

7 SYMMETRICL -EULERIN IDENTITY 7 Proof. We give a explicit costructio of the bijectio. Let v be a two-pix-permutatio ad write v (τ 0, τ 1, τ 2,..., τ r 1, τ r, τ r+1 ), where τ 0 p 1 ad τ r+1 p 2. If τ i (respectively τ j ) is the leftmost (respectively rightmost) o-empty word (clearly i 0, 1 ad j r, r+1), we ca write v i the followig compact way by removig the empty words at the begiig or at the ed: v (τ i, τ i+1,..., τ j 1, τ j ). (3.7) It is easy to see that the above procedure is reversible by addig some ecessary empty words at the two eds of the compact form (3.7). Now we wor with the compact form. Recall that (iv lec)v iv(cot(τ i ), cot(τ i+1 ),..., cot(τ j 1 ), cot(τ j )) (3.8) ad lec(v) j i lec(τ ). If i j, the oly oe word τ i is i the seuece v. We defie u (, σ i, ), where σ i is the uiue word (hoo) with cotet such that lec(σ i ) 2 lec(τ i ). If j > i, we defie the two-pix-permutatio u by u (d (τ i ), d(τ i+1 ), d(τ i+2 ),..., d(τ j 1 ), d (τ j )), where d ad d are two ivolutios defied i the proof of Lemma 2. Sice lec(d (τ i )) cot(τ i ) 1 lec(τ i ), lec(d (τ j )) cot(τ j ) 1 lec(τ j ) ad lec(d (τ )) cot(τ ) lec(τ ) for i, j, we have lec(u) cot(τ ) 2 lec(v) 2 lec(v). Fially it follows from (3.8) that (iv lec)u (iv lec)v. We give a example to illustrate the bijectio. Let v (27, 6389, 514, ). The v is a two-pix-permutatio of 9 ad iv(v) 19, lec(v) 3, (iv lec)v 16. The compact form is (27, 6389, 514), so that u (d (27), d(6389), d (514) (72, 9368, 145). Sice the first word 72 is ot icreasig, we obtai the stadard form by addig the empty word at the begiig, so that u (, 72, 9368, 145). Hece iv(u) 20, lec(u) 4, ad (iv lec)u 16. Combiig Lemmas 2, 3 ad 4, we obtai a combiatorial proof of (1.6). 4. Further extesios ad remars The classical Euleria polyomials correspod to the geeratig fuctio of descet umbers of symmetric groups. Let r 1 be a iteger. s a atural extesio of (1.4),

8 8 GUO-NIU HN, ZHICONG LIN, ND JING ZENG we cosider the polyomial (r) (t, ) defied by the geeratig fuctio e(z; r ) e(t r z; r ) e(t r z; r ) te(z; r ) (r) (t, ). (4.1) ( r ; r ) 1 It is easy to see that (r) (1, 1) r!, which is the cardiality of C r S, that is, the wreath product of a cyclic group C r of order r with the symmetric group S. Itroduce the coefficiets (r),i by (r) (t, ) i (r),i ()ti. (4.2) The geeratig fuctio proof of (1.6) ca be applied to derive immediately the idetity (r),r i 1 () (r),i 1 () (4.3) r r for positive itegers i ad such that i r. Let r ad be two positive itegers. Let {a, b,...} be ay subset of. We defie the r-colored versio of by Order the elemets of r by r : {a 1, b 1,..., a 2, b 2,...,..., a r, b r,...}. 1 1 < < 1 r < 2 1 < < 2 r <... < 1 < 2 <... < r. pix-r-colored-word is a seuece of colored words w (p, τ 1, τ 2,..., τ ) satisfyig the followig coditios: (C1) p is a icreasig word, with cotet r 0, the r-colored versio of 0, possibly empty; (C2) τ i (1 i ) are hoos, with cotet r i, the r-colored versio of i, ad the positive iteger is ot fixed; (C3) ( 0, 1,..., ) is a ordered partitio of. Let W,r be the set of all pix-r-colored-words of. For each w W,r we defie two statistics by iv r (w) iv(pτ 1 τ 2... τ r 1 τ r ), lec r (w) iv(τ 1 ) + + iv(τ ). Propositio 5. Let (r) (t, ) be defied by (4.1). The (ivr lecr)(σ) t lecr(σ) (r) (t, ). σ W,r

9 SYMMETRICL -EULERIN IDENTITY 9 Proof. By defiitio ad (3.3), we have (ivr lecr)(σ) t lecr(σ) σ W,r a 0 +a a a i 1 a 0 +a a a i 1 1 i P rai (t) a 0, a 1,..., a ( 0, 1,..., ) # i a i r 1 i ivr( 0, 1,..., ) P rai (t), where P m (t) : t + t t m 1. So the geeratig fuctio is (ivr lecr)(σ) t lecr(σ) z ( r ; r ),i σ W,r P a 0, a 1,..., a rai (t) 0 a 0 +a a ( r ; r ) r ( a 0 e(z; r ) a i 1 z a ( r ; r ) a ( ) ( 1 b 1 1 i z b 1 P rb (t) ( r ; r ) b b 1 t t rb 1 s (1 t)e(z; r ) e(t r z; r ) t e(z; r ). This completes the proof i view of (4.1). z b ( r ; r ) b ) 1 ) 1 Similarly, we ca defie two-pix-r-colored-words to be seueces of colored words with the followig coditios: w (p 1, τ 1, τ 2,..., τ, p 2 ) (C1) p 1 ad p 2 are icreasig words, with cotet r 0 ad B r 0, possibly empty; (C2) τ i (1 i ) are hoos, with cotet r i, the r-colored versio of i, ad the positive iteger is ot fixed; (C3) ( 0, 1,...,, B 0 ) is a ordered partitio of. Clearly we ca give a combiatorial proof of (4.3) by applyig the followig geeralizatio of Lemma 4. Propositio 6. There is a bijectio v u o the set of all two-pix-r-colored-words such that lec r v r 2 lec r u, ad (iv r lec r )v (iv r lec r )u.

10 10 GUO-NIU HN, ZHICONG LIN, ND JING ZENG Whe r 1, through Gessel s hoo factorizatio, we ca traslate the statistic (iv r, lec r ) to S. It would be iterestig to see whether there is a aalogous hoo factorizatio for geeral r 1 so that we ca traslate our (iv r, lec r ) defied o W,r to C r S. We coclude this paper with aother symmetric idetity for the Euleria umbers. Notice that for ay positive itegers ad we have ad ( ). It is ow 8, Cor. 6.2 that if d ad ω d is a primitive d th root of uity, the ( ) 1 t d (t, ω d ) (t). 1 t I particular, if d 2, the ω d 1. Hece, assumig that a + b is eve, the substitutio 1 i (1.6) yields ( a+b ) ( ) 2,j ( a+b ) ( ) 2,j. (4.4) i i 0 i+ja 1 0 i+jb 1 This idetity ca be rephrased i the form ( ) c + d ( ),j ( ) c + d i 0 i+j2c 1 0 ad ( ) c + d 1 0 i+j2(c 1) ( ),j i 0 i+j2d 1 ( ) c + d 1 ( ),j i i+j2(d 1) ( ),j i for ay positive itegers c ad d. The last two symmetrical idetities ivolvig biomial coefficiets ad Euleria umbers cry out for a combiatorial iterpretatio. cowledgemet. This wor was partially supported by the grat NR-08-BLN Refereces 1 George E. drews, The Theory of Partitios, Readig M: ddiso-wesley, Fa Chug, Ro Graham, Do Kuth, symmetrical Euleria idetity, J. Comb., 1 (2010), Domiiue Foata ad Guo-Niu Ha, The -taget ad -secat umbers via basic Euleria polyomials, Proc. mer. Math. Soc., 138 (2009), Domiiue Foata ad Guo-Niu Ha, Fix-mahoia calculus III; a uadruple distributio, Moatsh. Math., 154 (2008), Ira Gessel, colorig problem, mer. Math. Mothly, 98 (1991), Joh Shareshia ad Michelle L. Wachs, Euleria uasisymmetric fuctio, dv. i Math., 46 (2011),

11 SYMMETRICL -EULERIN IDENTITY 11 7 Joh Shareshia ad Michelle L. Wachs, -Euleria polyomials: excedace umber ad major idex, Electro. Res. ouc. mer. Math. Soc., 13 (2007), Bruce Saga, Joh Shareshia ad Michelle L. Wachs, Euleria uasisymmetric fuctios ad cyclic sievig, dv. i ppl. Math., 46 (2011), (Guo-Niu Ha) I.R.M.. UMR 7501, Uiversité de Strasbourg et CNRS, Frace address: guoiu.ha@uistra.fr (Zhicog Li) Departmet of Mathematics ad Statistics, Lazhou Uiversity, Chia, ad Istitut Camille Jorda, UMR 5208 du CNRS, Uiversité de Lyo, Uiversité Lyo 1, Frace address: li@math.uiv-lyo1.fr (Jiag Zeg) Istitut Camille Jorda, UMR 5208 du CNRS, Uiversité de Lyo, Uiversité Lyo 1, Frace address: zeg@math.uiv-lyo1.fr

ENGG1410-F Tutorial 6

ENGG1410-F Tutorial 6 Jianwen Zhao Department of Computer Science and Engineering The Chinese University of Hong Kong 1/16 Problem 1. Matrix Diagonalization Diagonalize the following matrix: A = [ ] 1 2 4 3 2/16 Solution The