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

1997/02/10 by Miklós Bóna, Bóna, Miklós · 2 citations
Mathematics · #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Algebraic structures and combinatorial models #Combinatorics (math.CO) #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.math/9702223

openalex publication_date 1997/02/10 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28

Abstract

Solving the first nonmonotonic, longer-than-three instance of a classic\nenumeration problem, we obtain the generating function H(x) of all\n1342-avoiding permutations of length n as well as an em exact formula for\ntheir number S_n(1342). While achieving this, we bijectively prove that the\nnumber of indecomposable 1342-avoiding permutations of length n equals that\nof labeled plane trees of a certain type on n vertices recently enumerated by\nCori, Jacquard and Schaeffer, which is in turn known to be equal to the number\nof rooted bicubic maps enumerated by Tutte in 1963. Moreover, H(x) turns out\nto be algebraic, proving the first nonmonotonic, longer-than-three instance of\na conjecture of Zeilberger and Noonan. We also prove that \√[n]S_n(1342)\nconverges to 8, so in particular, lim_n\→\n\∞(S_n(1342)/S_n(1234))=0.\n

Cited by

• Pattern Avoiding Permutations as Walks
• Ordinal and disjoint sums of partially ordered patterns

Related

• A new record for 1324-avoiding permutations
• A generating tree with a single label for permutations avoiding the vincular pattern 1-32-4
• Restricted non-separable planar maps and some pattern avoiding permutations
• A Combinatorial Proof for 132-Avoiding Permutations with a Unique Longest Increasing Subsequence
• Complete non-ambiguous trees and associated permutations: new enumerative results