|
|
A348574
|
|
Length of the shortest string over the alphabet {1,...,n} such that every subset of {1,...,n} appears as a substring (in some order).
|
|
1
|
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
a(7) = 40 by computer search.
a(8) >= 73 by formula (1) of Lipski.
a(8) <= 76 using 12345671825473861253846275138427163587...
...26341568237415876412573641823178456231.
a(9) >= 130 by formula (1) of Lipski.
a(9) <= 149 using 1234567891245739681253946175283419726538...
...4926137845926374159837241856931728643...
...1597246159283674981635781642391874562...
...89751384973251697248567213864957684.
|
|
REFERENCES
|
I. Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, pp. 39-40.
|
|
LINKS
|
|
|
FORMULA
|
a(n) >= binomial(n, ceiling(n/2)) + ceiling(n/2) - 1. [Lipski, formula (1)]
a(n) >= n * ceiling(binomial(n, floor(n/2)) / n). [Lipski, formula (3)]
|
|
EXAMPLE
|
a(4) = 8 because the string 12342413 contains every subset of {1,2,3,4} as a substring -- e.g., {1,3,4} can be found in the last three symbols ('413') -- and it can be shown that no string of length 7 has this property (see, e.g., Lipski 1978).
Examples of optimal strings for n <= 7:
1: 1
2: 12
3: 1231
4: 12342413
5: 1234512413524
6: 123415643641253624531625
7: 1234567214573126431523674256147325716357
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|