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.

Ämnesord

NATURVETENSKAP  -- Matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics (hsv//eng)

Nyckelord

pattern containment

permutation statistic

MATHEMATICS

MATEMATIK

TECHNOLOGY

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)