Permutations avoiding two patterns of length three
type: Item
instance of: scholarly article
title: Permutations avoiding two patterns of length three
zbMATH Open document ID: 1024.05005
author: Vincent Vatter
published in: The Electronic Journal of Combinatorics
publication date: 2003-05-13T00:00:00Z
full work available at URL: https://eudml.org/doc/122989
full work available at URL: v9i2r6.html
review text: 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.
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 1861458
zbMATH Keywords: restricted permutation
zbMATH Keywords: forbidden subsequence
zbMATH Keywords: generating tree
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1861458