Restricted permutations

Let \(S_n\) be the symmetric group on \(\{1,2,\ldots,n\}\). A permutation \(\sigma \in S_n\) is said to avoid the 3-letter word 132 iff there is no triple \(1\leq i<j<k\leq n\) such that \(\sigma (i)<\sigma (k)<\sigma (j)\). Similarly one defines \(\tau\)-avoiding permutations for every \(\tau \in S_3\). More generally, if \(R\subseteq S_3\), let \(S_n(R)\) be the set of all permutations in \(S_n\) which avoid every 3-letter word contained in \(R\). \textit{D. E. Knuth} [The art of computer programming, Vol. 3 (1974; Zbl 0302.68010)] proved that \[ | S_n(R)| =\frac{1}{n+1}\binom{2n}{n}\text{ (= \(n\)th Catalan number)} \] for each \(R\) of cardinality one. In the first section of the paper under review, the authors obtain more detailed results concerning the number of even (resp. odd) permutations in \(S_n\) which avoid a restriction \(R\), \(| R| =1\). In sections 3, 4 and 5 the numbers \(| S_n(R)|\) are determined, for \(| R| =2,3\) and \(4,5\), respectively. In the last section the authors present, for each \(n\geq 1\) and \(R\subset S_3\), a construction of lattices \(L_n(R)\) with the properties: (a) there exists a poset embedding of \(L_n(R)\) into \(L_m(R')\) if \(n\leq m\), \(R\supseteq R'\); (b) \(L_n(R)\) is minimal with respect to cardinality.

Recommendations

Cites work

Cited in

(only showing first 100 items - show all)

This page was built for publication: Restricted permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5916426)