Counting (3+1)-avoiding permutations

DOI10.1016/J.EJC.2011.06.006MaRDI QIDQ649006zbMATH OpenOpenAlexFDO

Authors Mike Atkinson, Bruce E. Sagan, Vincent Vatter

Publication date 29 November 2011

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.5568

zbMATH Keywords

generating functionpermutationposet

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorics of partially ordered sets (06A07)

Abstract: A poset is {it $(3+1)$-free} if it contains no induced subposet isomorphic to the disjoint union of a 3-element chain and a 1-element chain. These posets are of interest because of their connection with interval orders and their appearance in the $(3+1)$-free Conjecture of Stanley and Stembridge. The dimension 2 posets $P$ are exactly the ones which have an associated permutation $pi$ where $iprecj$ in $P$ if and only if $i<j$ as integers and $i$ comes before $j$ in the one-line notation of $pi$. So we say that a permutation $pi$ is {it $(3+1)$-free} or {it $(3+1)$-avoiding} if its poset is $(3+1)$-free. This is equivalent to $pi$ avoiding the permutations 2341 and 4123 in the language of pattern avoidance. We give a complete structural characterization of such permutations. This permits us to find their generating function.

Review text

The authors investigate \((\mathbf{3}+\mathbf{1})\)--avoiding permutations. It is well known that every permutation \(\pi\) gives rise to a poset \(P_{\pi}\), where \(i\prec j\) in \(P_{\pi}\) if and only if \(i<j\) and \(i\) appears to the left of \(j\) in \(\pi\). The authors call a permutation \(\pi\) \((\mathbf{3}+\mathbf{1})\)-avoiding, if its poset \(P_{\pi}\) is \((\mathbf{3}+\mathbf{1})\)-free. This means that the poset \(P_{\pi}\) contains no induced subposet isomorphic to the disjoint union of a 3-element chain and a 1-element chain. In this article the authors characterize completely the structure of such \((\mathbf{3}+\mathbf{1})\)-avoiding permutations. They give an exact formula for the generating function of these permutations.

Recommendations

• Pattern avoidance in poset permutations
• Enumeration of graded \((3+1)\)-avoiding posets
• Forbidden subsequences
• Enumeration of graded (3+1)-avoiding posets
• Counting 1324-avoiding permutations

Cites work

• A characterization of (3+1)-free posets
• A chromatic symmetric function in noncommuting variables
• A simple proof for the exponential upper bound for some tenacious patterns
• A symmetric function generalization of the chromatic polynomial of a graph
• An algorithmic sign-reversing involution for special rim-hook tableaux
• Finite transition matrices for permutations avoiding pairs of length four patterns
• Incomparability graphs of \((3+1)\)-free posets are \(s\)-positive
• Intransitive indifference with unequal indifference intervals
• On immanants of Jacobi-Trudi matrices and permutations with restricted position
• On the Stanley--Wilf limit of 4231-avoiding permutations and a conjecture of Arratia
• Permutations with forbidden subsequences and a generalized Schröder number
• Postscript: ``Permutations with forbidden subsequences and a generalized Schröder number [Discrete Mathematics 218 (2000) 121--130]
• Restricted permutations
• Simple permutations and pattern restricted permutations
• The permutation classes equinumerous to the smooth class
• Wilf classes of pairs of permutations of length 4

Cited in

(11)

• Enumerating permutations that avoid three term arithmetic progressions
• Structure and enumeration of \((3+1)\)-free posets
• Counting 3-stack-sortable permutations
• Pattern avoidance in poset permutations
• Enumeration of graded (3+1)-avoiding posets
• On weakly graded posets of order-preserving maps under the natural partial order
• Ricci -solitons on 3-dimensional -Einstein almost Kenmotsu manifolds
• An algorithm computing combinatorial specifications of permutation classes
• Enumeration of graded \((3+1)\)-avoiding posets
• The antipode of linearized Hopf monoids
• Combinatorial exploration: an algorithmic framework for enumeration

This page was built for publication: Counting \(\mathbf {(3+1)}\)-avoiding permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q649006)