<abstract xmlns="http://www.w3.org/1999/xhtml"> A permutation of length n may be represented, equivalently, by a sequence a1a2 • • • an satisfying 0 &lt; ai &lt; i for all z, which is called an inversion sequence. In analogy to the usual case for permutations, the pattern avoidance question is addressed for inversion sequences. In particular, explicit formulas and/or generating functions are derived which count the inversion sequences of a given length that avoid a single pattern of length three. Among the sequences encountered are the Fibonacci numbers, the Schröder numbers, and entry A200753 in OEIS. We make use of both algebraic and combinatorial methods to establish our results. An explicit Injection is given between two of the avoidance classes, and in three cases, the kernel method is used to solve a functional equation satisfied by the generating function enumerating the class in question. </abstract>

A permutation of length n may be represented, equivalently, by a sequence a1a2 • • • an satisfying 0 < ai < i for all z, which is called an inversion sequence. In analogy to the usual case for permutations, the pattern avoidance question is addressed for inversion sequences. In particular, explicit formulas and/or generating functions are derived which count the inversion sequences of a given length that avoid a single pattern of length three. Among the sequences encountered are the Fibonacci numbers, the Schröder numbers, and entry A200753 in OEIS. We make use of both algebraic and combinatorial methods to establish our results. An explicit Injection is given between two of the avoidance classes, and in three cases, the kernel method is used to solve a functional equation satisfied by the generating function enumerating the class in question.

Pattern avoidance in inversion sequences

Department of Mathematics University of Haifa 31905 Haifa, Israel

Department of Mathematics University of Tennessee Knoxville, TN 37996 USA

Pure Mathematics and Applications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"Pattern avoidance in inversion sequences"}

A permutation of length n may be represented, equivalently, by a sequence a1a2 • • • an satisfying 0 < ai < i for all z, which is called an inversion sequence....

Pattern avoidance in inversion sequences

Published Online: Jun 24, 2016

Page range: 157 - 176

Received: Feb 08, 2015

DOI: https://doi.org/10.1515/puma-2015-0016

Keywords
pattern avoidance, permutation, inversion sequence, kernel method

© 2016

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Pattern avoidance in inversion sequences

Published Online: Jun 24, 2016

Page range: 157 - 176

Received: Feb 08, 2015

DOI: https://doi.org/10.1515/puma-2015-0016

Keywordspattern avoidance, permutation, inversion sequence, kernel method

© 2016

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Keywords
pattern avoidance, permutation, inversion sequence, kernel method