scientific article; zbMATH DE number 1811347

MaRDI QIDQ3148507zbMATH OpenFDO

Authors V. Nyu, Dmitry G. Fon-Der-Flaass

Publication date 6 October 2002

zbMATH Keywords

permutationset of wordsuniversal sequence

Mathematics Subject Classification ID

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

Review text

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.

Recommendations

• Universal cycles for permutations
• A new universal cycle for permutations
• Shortened universal cycles for permutations
• On shortening u-cycles and u-words for permutations
• Universal layered permutations

Cited in

(8)

• Universal layered permutations
• On shortening u-cycles and u-words for permutations
• A construction of short sequences containing all permutations of a set as subsequences
• Lower bounds for superpatterns and universal sequences
• Universal limits of substitution-closed permutation classes
• Length lower bounds for reflecting sequences and universal traversal sequences
• A note on universal and canonically coloured sequences
• The maximal length of a k-separator permutation

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3148507)