Forbidden subsequences (Q1336669)

A permutation \(\tau\) of length \(k\) is denoted by \((a_ 1,a_ 2,\dots, a_ k)\) so that \(\tau(i)= a_ i\), \(i=1,2,3,\dots, k\). Consider two permutations \(\tau\) and \(\pi\) of lengths \(k\) and \(n\) respectively. \(\pi\) is said to be \(\tau\)-avoiding if no subsequence \(i_{\tau(1)},i_{\tau(2)},\dots, i_{\tau(k)}\) of \([n]= \{1,2,\dots,n\}\) exists such that \(\pi(i_ 1)< \pi(i_ 2)<\cdots< \pi(i_ k)\). In case there is such a subsequence, we say that the subsequence \(\pi(i_{\tau(1)}),\dots,\pi(i_{\tau(k)})\) is of type \(\tau\). Let \(S_ n(\tau)\) denote the set of \(\tau\)-avoiding permutations in \(S_ n\), the symmetric group on \([n]\). The general question addressed here refers to the number of permutations of a certain length avoiding a given permutation of length 4. In this paper it is shown that \(| S_ n(4132)|= | S_ n(3142)|\) by proving the stronger theorem for the corresponding permutation trees: \(T(4132)\cong T(3142)\). A new proof of the so-called Schröder result is given, and some conjectures concerning the sort of permutations \(\tau\) and \(\sigma\) for which \(| S_ n(\tau)|= | S_ n(\sigma)|\) for all \(n\in N\) are given.