×

zbMATH — the first resource for mathematics

Generalized pattern avoidance. (English) Zbl 0994.05004
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)], E. Babson and 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.

MSC:
05A15 Exact enumeration problems, generating functions
05A05 Permutations, words, matrices
05A18 Partitions of sets
Software:
OEIS
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Babson, E.; Steingrı́msson, E., Generalized permutation patterns and a classification of the Mahonian statistics, Sémin. lotharingien comb., B44b, 18, (2000)
[2] Deutsch, E., Dyck path enumeration, Discrete math., 204, 167-202, (1999) · Zbl 0932.05006
[3] Flajolet, P.; Schott, R., Non-overlapping partitions, continued fractions, Bessel functions and a divergent series, Europ. J. combinatorics, 11, 421-432, (1990) · Zbl 0733.05007
[4] Knuth, D.E., The art of computer programming, (1973), Addison-Wesley Reading · Zbl 0191.17903
[5] Simion, R.; Schmidt, F.W., Restricted permutations, Europ. J. combinatorics, 6, 383-406, (1985) · Zbl 0615.05002
[6] Sloane, N.J.A.; Plouffe, S., The encyclopedia of integer sequences, (1995 http://www.research.att.com/ njas/sequences/), Academic Press San Diego
[7] Stanley, R.P., Enumerative combinatorics, (1997), Cambridge University Press Cambridge · Zbl 0889.05001
[8] West, J., Generating trees and the Catalan and Schröder numbers, Discrete math., 146, 247-262, (1995) · Zbl 0841.05002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.