Permutations avoiding two patterns of length three (Q1856068)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Permutations avoiding two patterns of length three
scientific article

    Statements

    Permutations avoiding two patterns of length three (English)
    0 references
    0 references
    13 May 2003
    0 references
    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.
    0 references
    restricted permutation
    0 references
    forbidden subsequence
    0 references
    generating tree
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references