Restricted permutations (Q5916426): Difference between revisions

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.