Classification of forbidden subsequences of length 4 (Q1922878)

This paper deals with the classification of forbidden subsequences of length 4, and here `sequence' (or subsequence of a permutation) refers to a sequence of distinct positive integers \((b_1,b_2,\dots,b_k)\). A permutation \(\pi\) is said to avoid a permutation \(\gamma\) if \(\pi\) has no subsequence of type \(\gamma\). The set of \(\gamma\)-avoiding permutations in \(s_n\) is denoted by \(s_n(\gamma)\), and we call \(\gamma\) a forbidden subsequence of \(s_n(\gamma)\). In order to show that \(|s_n(1,2,3,4)|=|s_n(4,1,2,3)|\) for all \(n\in \mathbb{N}\), specific switching operations on \(s_n(1,2,3)\) are constructed resulting in partitioning its elements into equivalence classes. This together with the fact that the tree \(T(1,2,3)\) can be embedded in \(T(1,2,3,4)\) and \(T(4,1,2,3)\) lead us to prove \(|s_n(1,2,3,4)|=|s_n(4,1,2,3)|\) for all \(n\in\mathbb{N}\).