Permutations avoiding a pair of patterns of type (1,2) or (2,1)
Anders Claesson, Toufik Mansour · 2002
In [1] Babson and Steingr'imsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. Claesson [2] presented a complete solution for the number of permutations avoiding any single (generalized) pattern of type (1; 2) or (2; 1). For eight of these twelve patterns the answer is given by the Bell numbers. For the remaining four the answer is given by the Catalan numbers. In the present