A recursive bijective approach to counting permutations containing 3-letter patterns
| dc.creator | Callan, David | |
| dc.date | 2002-11-25 | |
| dc.date.accessioned | 2026-07-07T04:53:16Z | |
| dc.date.available | 2026-07-07T04:53:16Z | |
| dc.description | 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. | |
| dc.description | 28 pages | |
| dc.identifier | https://arxiv.org/abs/math/0211380 | |
| dc.identifier | http://arxiv.org/abs/math/0211380 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/65775 | |
| dc.subject | Combinatorics | |
| dc.subject | 05A05; 05A15 | |
| dc.title | A recursive bijective approach to counting permutations containing 3-letter patterns | |
| dc.type | text |