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
Pattern avoidance in inversion sequences
Mansour, Shattuck · Pure mathematics and applications · 2015
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.