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, 2, 4, 8, 13, 24, 40

Offset: 1

Author

Alexander D. Healy, Oct 23 2021

Keywords

• nonn
• hard
• more

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.

Examples

			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
		

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.

Crossrefs

Cf. A062714.

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)]