The X-Class and Almost-Increasing Permutations |
| |
Authors: | Sergi Elizalde |
| |
Institution: | (1) Research Center for Combinatorics, Nankai University, Tianjin, 300071, China |
| |
Abstract: | In this paper we give a bijection between the class of permutations that can be drawn on an X-shape and a certain set of permutations
that appears in Knuth 4] in connection to sorting algorithms. A natural generalization of this set leads us to the definition of almost-increasing permutations, which is a one-parameter family of permutations that can be characterized in terms of forbidden patterns. We find generating
functions for almost-increasing permutations by using their cycle structure to map them to colored Motzkin paths. We also
give refined enumerations with respect to the number of cycles, fixed points, excedances, and inversions. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|