×

Permutations containing many patterns. (English) Zbl 1140.05002

Summary: It is shown that the maximum number of patterns that can occur in a permutation of length \(n\) is asymptotically \(2^{n}\). This significantly improves a previous result of M. Coleman [Electron. J. Comb. 11, No. 1, Research paper N8 (2004; Zbl 1053.05002)].

MSC:

05A05 Permutations, words, matrices
05A16 Asymptotic enumeration
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)

Citations:

Zbl 1053.05002
PDFBibTeX XMLCite
Full Text: DOI arXiv