# 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
##### Keywords:
permutation; universal sequence; set of words