On Permutations with Bounded Drop Size
Joanna N. Chen and William Y.C. Chen
Abstract: The maximum drop size of a permutation π of [n] = {1, 2,..., n} is defined to be the maximum value of i - π(i). Chung, Claesson, Dukes and Graham found polynomials P_{k}(x) that can be used to determine the number of permutations of [n] with d descents and maximum drop size at most 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 + ... + 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 construct a map ψ_{k} on the set of permutations with maximum drop size at most k. We show that ψ_{k} 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 B analogue of the polynomials P_{k}(x). AMS Classification: 05A05, 05A15. Keywords: descent polynomial, unimodal polynomial, maximum drop. Download: pdf |