Output details

Descent polynomials for permutations with bounded drop size

<12>This paper connects the combinatorial theory of juggling, developed in the last couple of decades, to the theory of sorting in computer science. A novel aspect of the paper is the highly surprising fact that permutations requiring exactly k passes of bubble-sort to be sorted are equivalent to particular juggling sequences that have k balls in the air at any given time. This paper thus provides a bridge between two previously unconnected research areas, and the possibility of applying juggling theory to the study of sorting.