6533b85dfe1ef96bd12be89c
RESEARCH PRODUCT
Lehmer code transforms and Mahonian statistics on permutations
Vincent Vajnovszkisubject
Discrete mathematicsCode (set theory)Mathematics::CombinatoricsValue (computer science)020206 networking & telecommunications0102 computer and information sciences02 engineering and technologyMathematical proof01 natural sciencesPermutation codeTheoretical Computer ScienceCombinatoricsPermutation010201 computation theory & mathematicsLehmer codeStatistics[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]FOS: Mathematics0202 electrical engineering electronic engineering information engineeringMathematics - CombinatoricsDiscrete Mathematics and CombinatoricsCombinatorics (math.CO)Bijection injection and surjectionComputingMilieux_MISCELLANEOUSMathematicsdescription
Abstract In 2000 Babson and Steingrimsson introduced the notion of vincular patterns in permutations. They show that essentially all well-known Mahonian permutation statistics can be written as combinations of such patterns. Also, they proved and conjectured that other combinations of vincular patterns are still Mahonian. These conjectures were proved later: by Foata and Zeilberger in 2001, and by Foata and Randrianarivony in 2006. In this paper we give an alternative proof of some of these results. Our approach is based on permutation codes which, like the Lehmer code, map bijectively permutations onto subexcedant sequences. More precisely, we give several code transforms (i.e., bijections between subexcedant sequences) which when applied to the Lehmer code yield new permutation codes which count occurrences of some vincular patterns. These code transforms can be seen as a pre-compression step of the Lehmer code because they map some redundancies into runs of 0s. Also, our proofs, unlike the previous ones, provide explicit bijections between permutations having a given value for two different Mahonian pattern-based statistics.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2012-06-11 |