<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

Online veröffentlicht: 24. Juni 2016

Seitenbereich: 157 - 176

Eingereicht: 08. Feb. 2015

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

Schlüsselwörter
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

Online veröffentlicht: 24. Juni 2016

Seitenbereich: 157 - 176

Eingereicht: 08. Feb. 2015

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

Schlüsselwörterpattern avoidance, permutation, inversion sequence, kernel method

© 2016

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

Schlüsselwörter
pattern avoidance, permutation, inversion sequence, kernel method