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
W. Lipski, Jr., On strings containing all subsets as substrings, Discrete Mathematics 21, 1978, pp. 253-259.
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
Alexander D. Healy, Oct 23 2021
STATUS
approved