Wilf classes of pairs of permutations of length 4 (Q2571265): Difference between revisions

We say that a permutation \(\sigma \in S_n\) contains another permutation \(\pi \in S_m\), \(m\leq n\), if there exist \(i_1 < i_2 <\dots < i_m\) such that \(\sigma(i_k)< \sigma(i_l)\) if and only if \(\pi(k)< \pi(l)\), for all \(k\) and \(l\). If \(\sigma\) contains no occurrences of \(\pi\), we say that \(\sigma\) avoids \(\pi\). By \(S_n(\pi_1,\pi_2,\dots,\pi_r)\) we denote the set of permutations that avoid \(\pi_1,\pi_2,\dots ,\pi_r\). The problem of determining \(| S_n(\pi_1,\pi_2,\dots,\pi_r)| \) for various sets of permutations is well studied. We say that two sets of permutations \(\{\pi_1,\pi_2,\dots ,\pi_r\}\) and \(\{\tau_1,\tau_2,\dots ,\tau_s\}\) are Wilf-equivalent if \(| S_n(\pi_1,\pi_2,\dots,\pi_r)| =| S_n(\tau_1,\tau_2,\dots ,\tau_s)| \). In this paper it is shown that \(| S_n(1342,2143)| = | S_n(3142,2341)| \) and \(| S_n(1342,3124)| = | S_n(1243,2134)| \). These two results complete the classification of Wilf-equivalence classes for pairs of permutations of length four, as for all other pairs relations were previously known.