Counting \(\mathbf {(3+1)}\)-avoiding permutations (Q649006)

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.