A Recursive Bijective Approach to Counting Permutations Containing
3-letter Patterns
We present a method, illustrated by several examples, to find explicit
counts of permutations containing a given multiset of three letter
patterns. The method is recursive, depending on bijections to reduce to
the case of a smaller multiset, and involves a consideration of separate
cases according to how the patterns overlap. Specifically, we use the
method (i) to provide combinatorial proofs of Bona's formula
{2n – 3}choose{n – 3} for the number of n-permutations containing one 132
pattern and Noonan's formula 3/n {2n}choose{n + 3} for one 123 pattern, (ii)
to express the number of n-permutations containing exactly k 123 patterns
in terms of ballot numbers for k <= 4, and (iii) to express the number of
123-avoiding n-permutations containing exactly k 132 patterns as a linear
combination of powers of 2, also for k <= 4. The results strengthen the
conjecture that the counts are algebraic for all k.
