Generalized pattern avoidance (Q5949033)

A permutation \(\pi=\pi_1\pi_2\dots \pi_n\) is said to avoid the pattern \(\sigma=\sigma_1\sigma_2\dots\sigma_k\) (given by another permutation) if there is no subword \(\pi_{i_1}\pi_{i_2}\dots \pi_{i_k}\) of \(\pi\) in which the letters are in the same relative order as \(\sigma_1\sigma_2\dots\sigma_k\). In a very influential paper [Sémin. Lothar. Comb. 44, B44b (2000; Zbl 0957.05010)], \textit{E. Babson} and \textit{E. Steingrímsson} extended this notion to ``generalized pattern avoidance'' where one also specifies by the (generalized) pattern whether or not letters in the subword must be adjacent. In the paper under review a complete solution is given for the problem of counting all permutations of \(n\) letters which avoid a generalized pattern of length 3 with exactly one adjacent pair of letters. The answers feature the Bell numbers and Catalan numbers. The author also addresses the problem of enumerating all permutations of \(n\) letters which avoid two such patterns of length three. In the cases where he provides solutions, there appear Motzkin numbers, the number of involutions of \(n\) letters, and, most interestingly, Bessel numbers. The proofs are throughout bijective. For example, in the last mentioned case he sets up a bijection between his permutations and non-overlapping (set) partitions, where, as intermediate objects, he has to deal with new combinatorial objects, ``monotone'' partitions. In several cases also refined countings are obtained.