Bounds of the length of a universal sequence for permutations. (Russian) Zbl 0995.05003

Nyu, V.; Fon-Der-Flaass, D.

Diskretn. Anal. Issled. Oper., Ser. 1 7, No. 2, 65-70 (2000).

A sequence \(W\) is called universal for a set \(S\) of words if every word \(s\in S\) appears in \(W\) as a subword, i.e., \(W=W_1sW_2\). A universal sequence of minimal length is called minimal. Let \(P(n)\) be the set of all permutations of length \(n\) and let \(L(n)\) be the length of a minimal universal sequence for \(P(n)\).
It is shown that \[ n!+(n-1)!+ \frac{n-1}{2n-3} (n-2)! + n - 3 \leq L(n) \leq n!+(n-1)!+ \dots +1!. \] Two constructions of a universal sequence of length \(n!+(n-1)!+ \dots +1!\) are also presented.

Reviewer: F.I.Solov’eva (Novosibirsk)

MSC:

05A05	Permutations, words, matrices
68R15	Combinatorics on words

Keywords:

permutation; universal sequence; set of words