Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps

Details Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps

1997-02-11

arxiv.org/abs/math/9702223v1

Mathematics

Combinatorics

Scientific paper

Solving the first nonmonotonic, longer-than-three instance of a classic enumeration problem, we obtain the generating function $H(x)$ of all 1342-avoiding permutations of length $n$ as well as an {\em exact} formula for their number $S_n(1342)$. While achieving this, we bijectively prove that the number of indecomposable 1342-avoiding permutations of length $n$ equals that of labeled plane trees of a certain type on $n$ vertices recently enumerated by Cori, Jacquard and Schaeffer, which is in turn known to be equal to the number of rooted bicubic maps enumerated by Tutte in 1963. Moreover, $H(x)$ turns out to be algebraic, proving the first nonmonotonic, longer-than-three instance of a conjecture of Zeilberger and Noonan. We also prove that $\sqrt[n]{S_n(1342)}$ converges to 8, so in particular, $lim_{n\rightarrow \infty}(S_n(1342)/S_n(1234))=0$.

Affiliated with

Also associated with

No associations

Rating

Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps 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 Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-393404