2002/11/25 by David Callan, Callan, David · 1 citation
Computer Science · Mathematics · #05A05 #05A15 #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A05 #msc:05A15
paper · pdf · doi:10.48550/arxiv.math/0211380
28 pages
arxiv created 2002/11/25 · openalex publication_date 2002/11/25 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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-3choosen-3 for the number of n-permutations containing one 132 pattern and Noonan's formula 3/n 2nchoosen+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.