NobleBlocks

Research indexJournal article

Pattern avoidance in inversion sequences

Mansour, Shattuck

Pure mathematics and applications1 Dec 2015Open access

NobleIDark:/48914/w1/20260521/08E5A361DOI10.1515/puma-2015-0016

Abstract

Abstract A permutation of length n may be represented, equivalently, by a sequence a 1 a 2 • • • a n satisfying 0 < a i < 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.

Discussion

Citations

Topics

More

Suggest a correction or report