Permutations avoiding two patterns of length three
For \(q\), a permutation in the symmetric group \(S_k\), \(k< n\), let \(S_n(q)\) denote the set of all permutations in \(S_n\) that avoid the pattern of \(q\). Let \(S_n(Q)= \bigcap_{q\in Q} S_n(q)\). The author shows how to use generating trees to routinely find \(|S_n(Q)|\) for all sets \(Q\) of permutations with \(|Q\cap S_3|\geq 2\). Using ideas of \textit{M. D. Atkinson} [Discrete Math. 195, 27-38 (1999; Zbl 0932.05002)], the author then shows how this yields an algorithm to find the number of permutations in \(S_n\) which avoid two patterns of length three and contain a finite set of other patterns a prescribed number of times. He also studies when the level sums of a generating tree agree with a polynomial.
scientific article; zbMATH DE number 1861458