<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 11 Issue 3-4" %>
Dense Packing of Patterns in a Permutation
Henrik Eriksson1, Kimmo Eriksson2, Svante Linusson3, and Johan Wästlund4
1NADA, KTH, SE-100 44 Stockholm, Sweden
2IMA, Mälardalens högskola, SE-721 23 Västerås, Sweden
3Department of Mathematics, KTH, SE-100 44 Stockholm, Sweden
4MaI, Linköpings universitet, SE-581 83 Linköping, Sweden
Annals of Combinatorics 11 (3-4) p.459-470 September, 2007
AMS Subject Classification:05A05, 05D40
We study the length Lk of the shortest permutation containing all patterns of length k. We establish the bounds e-2k2< Lk ≤(2⁄3+o(1))k2. We also prove that as k →∞, there are permutations of length (1⁄4+o(1))k2 containing almost all patterns of length k.
Keywords: pattern containment, permutation statistic


1. M.H. Albert, M. Coleman, R. Flynn, and I. Leader, Permutations containing many patterns, Ann. Combin., to appear.

2. N. Alon and J. Spencer, The Probabilistic Method, John Wiley & Sons, New York, 2000.

3. R. Arratia, On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern, Electron. J. Combin. 6 (1999) #N1.

4. F. Chung, P. Diaconis, and R. Graham, Universal cycles for combinatorial structures, Discrete Math. 110 (1-3) (1992) 43--59.

5. K. Eriksson, Strong convergence and a game of numbers, Europ. J. Combin. 17 (4) (1996) 379--390.

6. R. Simion and F.W. Schmidt, Restricted permutations, Europ. J. Combin. 6 (4) (1985) 383-- 406.