Descent polynomials for permutations with bounded drop size
Fan Chung, Anders Claesson, Mark Dukes, Ronald Graham
Abstract
Motivated by juggling sequences and bubble sort, we examine permutations on the set {1, 2, …, n} with d descents and maximum drop size k. We give explicit formulas for enumerating such permutations for given integers k and d. We also derive the related generating functions and prove unimodality and symmetry of the coefficients.
Résumé. Motivés par les ``suites de jonglerie'' et le tri à bulles, nous étudions les permutations de l'ensemble {1, 2, …, n } ayant d descentes et une taille de déficience maximale k. Nous donnons des formules explicites pour l'énumération de telles permutations pour des entiers k et d fixés, ainsi que les fonctions génératrices connexes. Nous montrons aussi que les coefficients possèdent des propriétés d'unimodalité et de symétrie.
Résumé. Motivés par les ``suites de jonglerie'' et le tri à bulles, nous étudions les permutations de l'ensemble {1, 2, …, n } ayant d descentes et une taille de déficience maximale k. Nous donnons des formules explicites pour l'énumération de telles permutations pour des entiers k et d fixés, ainsi que les fonctions génératrices connexes. Nous montrons aussi que les coefficients possèdent des propriétés d'unimodalité et de symétrie.
Full Text: PostScript PDF