Enumerations of Permutations Simultaneously Avoiding a Vincular and a Covincular Pattern of Length 3
Christian Bean and Henning Ulfarsson
School of Computer Science
University of Iceland
Vincular and covincular patterns are generalizations of classical
patterns allowing restrictions on the indices and values of the
occurrences in a permutation. In this paper we study the integer
sequences arising as the enumerations of permutations simultaneously
avoiding a vincular and a covincular pattern, both of length 3, with at
most one restriction. We see familiar sequences, such as the Catalan
and Motzkin numbers, but also some previously unknown sequences which
have close links to other combinatorial objects such as lattice paths
and integer partitions. Where possible we include a generating
function for the enumeration. One of the cases considered settles a
conjecture by Pudwell (2010) on the Wilf-equivalence of barred
patterns. We also give an alternative proof of the classic result that
permutations avoiding 123 are counted by the Catalan numbers.
Full version: pdf,
(Concerned with sequences
Received February 14 2017; revised versions received June 9 2017; July 3 2017.
Published in Journal of Integer Sequences, July 5 2017.
Journal of Integer Sequences home page