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 Pk(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 Qk(x) = xkPk(x) and Rn,k(x) = Qk(x)(1 + x + ... + xk)n-k, and raised the question of finding a bijective proof of the symmetry property of Rn,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 Pk(x).

  AMS Classification:  05A05, 05A15.

  descent polynomial, unimodal polynomial, maximum drop.

  Download:   pdf