×

zbMATH — the first resource for mathematics

Bounds of the length of a universal sequence for permutations. (Russian) Zbl 0995.05003
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.

MSC:
05A05 Permutations, words, matrices
68R15 Combinatorics on words
PDF BibTeX XML Cite