On permutations with bounded drop size

DOI10.1016/J.EJC.2015.12.008MaRDI QIDQ5964261zbMATH OpenOpenAlexFDO

Authors Joanna N. Chen, William Y. C. Chen

Publication date 29 February 2016

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.5428

zbMATH Keywords

maximum drop size of a permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: The maximum drop size of a permutation $pi$ of $[n]=1,2,ldots,n$ is defined to be the maximum value of $i-pi(i)$. Chung, Claesson, Dukes and Graham obtained polynomials $P_k(x)$ that can be used to determine the number of permutations of $[n]$ with $d$ descents and maximum drop size not larger than $k$. Furthermore, Chung and Graham gave combinatorial interpretations of the coefficients of $Q_k(x)=x^k{P}_k(x)$ and $R_{n,k}(x)=Q_k(x)(1+x+cdots+x^k{)}^{n-k}$, and raised the question of finding a bijective proof of the symmetry property of $R_{n,k}(x)$. In this paper, we establish a bijection $varphi$ on $A_{n,k}$, where $A_{n,k}$ is the set of permutations of $[n]$ and maximum drop size not larger than $k$. The map $varphi$ remains to be a bijection between certain subsets of $A_{n,k}$. %related to the symmetry property. This provides an answer to the question of Chung and Graham. The second result of this paper is a proof of a conjecture of Hyatt concerning the unimodality of polynomials in connection with the number of signed permutations of $[n]$ with $d$ type $B$ descents and the type $B$ maximum drop size not greater than $k$.

Recommendations

• Descent polynomials for permutations with bounded drop size
• Descent polynomials for permutations with bounded drop size
• Inversion-descent polynomials for restricted permutations
• Descent polynomials for \(k\) bubble-sortable permutations of type B
• Descents of permutations in a Ferrers board

Cites work

• \(q\)-Eulerian polynomials arising from Coxeter groups
• Descent polynomials for \(k\) bubble-sortable permutations of type B
• Descent polynomials for permutations with bounded drop size
• scientific article; zbMATH DE number 3584785 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• Inversion-descent polynomials for restricted permutations
• On the descent numbers and major indices for the hyperoctahedral group
• The depth of a permutation.

Cited in

(11)

• A note on the binomial drop polynomial of a poset
• Inversion-descent polynomials for restricted permutations
• Descent polynomials for \(k\) bubble-sortable permutations of type B
• scientific article; zbMATH DE number 140099 (Why is no real title available?)
• Descents of permutations in a Ferrers board
• Descent polynomials for permutations with bounded drop size
• scientific article; zbMATH DE number 1445297 (Why is no real title available?)
• A maxdrop statistic for standard Young tableaux
• scientific article; zbMATH DE number 7053339 (Why is no real title available?)
• Descent polynomials for permutations with bounded drop size
• Enumerating anchored permutations with bounded gaps

This page was built for publication: On permutations with bounded drop size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5964261)