A recursive bijective approach to counting permutations containing 3-letter patterns

Details A recursive bijective approach to counting permutations containing 3-letter patterns A recursive bijective approach to counting permutations containing 3-letter patterns

2002-11-25

arxiv.org/abs/math/0211380v1

Mathematics

Combinatorics

28 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A recursive bijective approach to counting permutations containing 3-letter patterns does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A recursive bijective approach to counting permutations containing 3-letter patterns, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A recursive bijective approach to counting permutations containing 3-letter patterns will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-254099