Dense packing of patterns in a permutation

• We study the length L-k of the shortest permutation containing all patterns of length k. We establish the bounds e(-2)k(2) < L-k <= (2/3 + o(1))k(2). We also prove that as k there are permutations of length (1/4+o(1))k(2) containing almost all patterns of length k.

Subject headings

NATURVETENSKAP  -- Matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics (hsv//eng)

Keyword

pattern containment

permutation statistic

MATHEMATICS

MATEMATIK

TECHNOLOGY

Publication and Content Type

ref (subject category)

art (subject category)