Counting (3+1)-avoiding permutations


European Journal of Combinatorics, 33 (2012), 49–61.

With Mike Atkinson and Bruce Sagan.

A poset is (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 π where i<j in P if and only if i<j as integers and i comes before j in the one-line notation of π. So we say that a permutation π is (3+1)-free or (3+1)-avoiding if its poset is (3+1)-free. This is equivalent to π 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.

The sequence found in the paper is A165531 in the OEIS.

Download the paper: