Enumerations of Permutations Simultaneously Avoiding a Vincular and a Covincular Pattern of Length 3
Christian Bean and Henning Ulfarsson
School of Computer Science
Reykjavik University
Menntavegi 1
101 Reykjavik
Iceland
Anders Claesson
Science Institute
University of Iceland
Dunhaga 5
107 Reykjavik
Iceland
Abstract:
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,
dvi,
ps,
latex
(Concerned with sequences
A000079
A000108
A000124
A001006
A098569
A121690
A249560
A249561
A249562
A249563.)
Received February 14 2017; revised versions received June 9 2017; July 3 2017.
Published in Journal of Integer Sequences, July 5 2017.
Return to
Journal of Integer Sequences home page