The permutation classes Av(1234,2341) and Av(1243,2314)

Bevan, David (2016). The permutation classes Av(1234,2341) and Av(1243,2314). Australasian Journal of Combinatorics, 64(1) pp. 3–20.

URL: http://ajc.maths.uq.edu.au/pdf/64/ajc_v64_p003.pdf

Abstract

We investigate the structure of the two permutation classes defined by the sets of forbidden patterns $\{{1234, 2341}\}$ and $\{{1243, 2314}\}$ . By considering how the Hasse graphs of permutations in these classes can be built from a sequence of rooted source graphs, we determine their algebraic generating functions. Our approach is similar to that of “adding a slice”, used previously to enumerate various classes of polyominoes and other combinatorial structures. To solve the relevant functional equations, we make extensive use of the kernel method.