No label defined (Q3148507)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1811347
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1811347 |
Statements
6 October 2002
0 references
permutation
0 references
universal sequence
0 references
set of words
0 references
0.8130844235420227
0 references
0.8036676049232483
0 references
0.7983128428459167
0 references
0.7926446199417114
0 references
0.7679553627967834
0 references
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.
0 references
