<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 11 Issue 3-4" %>
Permutations Containing Many Patterns
M.H. Albert1, Micah Coleman2, Ryan Flynn2, and Imre Leader3
1Department of Computer Science, University of Otago, PO Box 56, Dunedin, New Zealand
malbert@cs.otago.ac.nz
2Department of Mathematics, University of Florida, Gainesville, FL 32611, USA
mcoleman@math.ufl.edu, ryflynn@ufl.edu
3Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge, CB2 1TN, U.K.
leader@dpmms.cam.ac.uk
Annals of Combinatorics 11 (3-4) p.265-270 September, 2007
AMS Subject Classification: 05A05, 05A16, 05D40
Abstract:
It is shown that the maximum number of patterns that can occur in a permutation of length n is asymptotically 2n. This significantly improves a previous result of Coleman.
Keywords: permutation patterns, probabilistic counting

References:

1. M. Coleman, An answer to a question by Wilf on packing distinct patterns in a permutation, Electron. J. Combin. 11 (1) (2004) #N8.

2. H. Eriksson, K. Eriksson, S. Linusson, and J. W¨astlund, Dense packing of patterns in a permutation, Ann. Combin., to appear, http://www.i3s.unice.fr/fpsac/FPSAC02/articles.html.