On permutations with bounded drop size
详细信息 查看全文
- 作者：Joanna N. Chena ; joannachen@tjut.edu.cn" class="auth_mail" title="E-mail the corresponding author ; William Y.C. Chenb ; chenyc@tju.edu.cn" class="auth_mail" title="E-mail the corresponding author
- 刊名：European Journal of Combinatorics
- 出版年：2016
- 出版时间：May 2016
- 年：2016
- 卷：54
- 期：Complete
- 页码：138-153
- 全文大小：429 K
文摘
The m>maximum drop size m> of a permutation mmlsi35" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669815002723&_mathId=si35.gif&_user=111111111&_pii=S0195669815002723&_rdoc=1&_issn=01956698&md5=a40fdb1c38b8fb92791fe2a9f595bd46" title="Click to view the MathML source">πmathContainer hidden">mathCode"><math altimg="si35.gif" overflow="scroll"><mi>πmi>math> of mmlsi36" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669815002723&_mathId=si36.gif&_user=111111111&_pii=S0195669815002723&_rdoc=1&_issn=01956698&md5=553b088095acaedffa013b1bce674f61" title="Click to view the MathML source">[n]={1,2,…,n}mathContainer hidden">mathCode"><math altimg="si36.gif" overflow="scroll"><mrow><mo>[mo><mi>nmi><mo>]mo>mrow><mo>=mo><mrow><mo>{mo><mn>1mn><mo>,mo><mn>2mn><mo>,mo><mo>…mo><mo>,mo><mi>nmi><mo>}mo>mrow>math> is defined to be the maximum value of mmlsi37" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669815002723&_mathId=si37.gif&_user=111111111&_pii=S0195669815002723&_rdoc=1&_issn=01956698&md5=89a939afdcc73860f003b7c74bf931f5" title="Click to view the MathML source">i−π(i)mathContainer hidden">mathCode"><math altimg="si37.gif" overflow="scroll"><mi>imi><mo>−mo><mi>πmi><mrow><mo>(mo><mi>imi><mo>)mo>mrow>math>. Chung, Claesson, Dukes and Graham found polynomials mmlsi38" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669815002723&_mathId=si38.gif&_user=111111111&_pii=S0195669815002723&_rdoc=1&_issn=01956698&md5=090230552af39c656246bc4b485656ed" title="Click to view the MathML source">Pk(x)mathContainer hidden">mathCode"><math altimg="si38.gif" overflow="scroll"><msub><mrow><mi>Pmi>mrow><mrow><mi>kmi>mrow>msub><mrow><mo>(mo><mi>xmi><mo>)mo>mrow>math> that can be used to determine the number of permutations of mmlsi39" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669815002723&_mathId=si39.gif&_user=111111111&_pii=S0195669815002723&_rdoc=1&_issn=01956698&md5=1f868e5a8364f3572f55a11729924ad2" title="Click to view the MathML source">[n]mathContainer hidden">mathCode"><math altimg="si39.gif" overflow="scroll"><mrow><mo>[mo><mi>nmi><mo>]mo>mrow>math> with mmlsi40" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669815002723&_mathId=si40.gif&_user=111111111&_pii=S0195669815002723&_rdoc=1&_issn=01956698&md5=2a10affa3056dc00a14555cc56a5b085" title="Click to view the MathML source">dmathContainer hidden">mathCode"><math altimg="si40.gif" overflow="scroll"><mi>dmi>math> descents and maximum drop size at most mmlsi25" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669815002723&_mathId=si25.gif&_user=111111111&_pii=S0195669815002723&_rdoc=1&_issn=01956698&md5=ae516f247f3ae8fcf21e9fdc34daec6c" title="Click to view the MathML source">kmathContainer hidden">mathCode"><math altimg="si25.gif" overflow="scroll"><mi>kmi>math>. Furthermore, Chung and Graham gave combinatorial interpretations of the coefficients of mmlsi42" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669815002723&_mathId=si42.gif&_user=111111111&_pii=S0195669815002723&_rdoc=1&_issn=01956698&md5=c714ac55e5d6cf61fa3c1a0cbe616581" title="Click to view the MathML source">Qk(x)=xkPk(x)mathContainer hidden">mathCode"><math altimg="si42.gif" overflow="scroll"><msub><mrow><mi>Qmi>mrow><mrow><mi>kmi>mrow>msub><mrow><mo>(mo><mi>xmi><mo>)mo>mrow><mo>=mo><msup><mrow><mi>xmi>mrow><mrow><mi>kmi>mrow>msup><msub><mrow><mi>Pmi>mrow><mrow><mi>kmi>mrow>msub><mrow><mo>(mo><mi>xmi><mo>)mo>mrow>math> and mmlsi43" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669815002723&_mathId=si43.gif&_user=111111111&_pii=S0195669815002723&_rdoc=1&_issn=01956698&md5=494724e0b75a2f0d896d1a7fa559c14a" title="Click to view the MathML source">Rn,k(x)=Qk(x)(1+x+⋯+xk)n−kmathContainer hidden">mathCode"><math altimg="si43.gif" overflow="scroll"><msub><mrow><mi>Rmi>mrow><mrow><mi>nmi><mo>,mo><mi>kmi>mrow>msub><mrow><mo>(mo><mi>xmi><mo>)mo>mrow><mo>=mo><msub><mrow><mi>Qmi>mrow><mrow><mi>kmi>mrow>msub><mrow><mo>(mo><mi>xmi><mo>)mo>mrow><msup><mrow><mrow><mo>(mo><mn>1mn><mo>+mo><mi>xmi><mo>+mo><mo>⋯mo><mo>+mo><msup><mrow><mi>xmi>mrow><mrow><mi>kmi>mrow>msup><mo>)mo>mrow>mrow><mrow><mi>nmi><mo>−mo><mi>kmi>mrow>msup>math>, and raised the question of finding a bijective proof of the symmetry property of mmlsi44" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669815002723&_mathId=si44.gif&_user=111111111&_pii=S0195669815002723&_rdoc=1&_issn=01956698&md5=36a53e4ea9e30374a1ffdd5d44f03dd7" title="Click to view the MathML source">Rn,k(x)mathContainer hidden">mathCode"><math altimg="si44.gif" overflow="scroll"><msub><mrow><mi>Rmi>mrow><mrow><mi>nmi><mo>,mo><mi>kmi>mrow>msub><mrow><mo>(mo><mi>xmi><mo>)mo>mrow>math>. In this paper, we construct a map mmlsi45" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669815002723&_mathId=si45.gif&_user=111111111&_pii=S0195669815002723&_rdoc=1&_issn=01956698&md5=f841402e390fdb8c1998dc66f2b88721" title="Click to view the MathML source">φkmathContainer hidden">mathCode"><math altimg="si45.gif" overflow="scroll"><msub><mrow><mi>φmi>mrow><mrow><mi>kmi>mrow>msub>math> on the set of permutations with maximum drop size at most mmlsi25" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669815002723&_mathId=si25.gif&_user=111111111&_pii=S0195669815002723&_rdoc=1&_issn=01956698&md5=ae516f247f3ae8fcf21e9fdc34daec6c" title="Click to view the MathML source">kmathContainer hidden">mathCode"><math altimg="si25.gif" overflow="scroll"><mi>kmi>math>. We show that mmlsi45" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669815002723&_mathId=si45.gif&_user=111111111&_pii=S0195669815002723&_rdoc=1&_issn=01956698&md5=f841402e390fdb8c1998dc66f2b88721" title="Click to view the MathML source">φkmathContainer hidden">mathCode"><math altimg="si45.gif" overflow="scroll"><msub><mrow><mi>φmi>mrow><mrow><mi>kmi>mrow>msub>math> is an involution and it induces a bijection in answer to the question of Chung and Graham. The second result of this paper is a proof of a unimodality conjecture of Hyatt concerning the type mmlsi48" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669815002723&_mathId=si48.gif&_user=111111111&_pii=S0195669815002723&_rdoc=1&_issn=01956698&md5=26c6e2295a4a419051cfb60db9d14bd8" title="Click to view the MathML source">BmathContainer hidden">mathCode"><math altimg="si48.gif" overflow="scroll"><mi>Bmi>math> analogue of the polynomials mmlsi38" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669815002723&_mathId=si38.gif&_user=111111111&_pii=S0195669815002723&_rdoc=1&_issn=01956698&md5=090230552af39c656246bc4b485656ed" title="Click to view the MathML source">Pk(x)mathContainer hidden">mathCode"><math altimg="si38.gif" overflow="scroll"><msub><mrow><mi>Pmi>mrow><mrow><mi>kmi>mrow>msub><mrow><mo>(mo><mi>xmi><mo>)mo>mrow>math>.