A348574 - OEIS

%I #36 Jan 01 2022 21:21:21

%S 1,2,4,8,13,24,40

%N Length of the shortest string over the alphabet {1,...,n} such that every subset of {1,...,n} appears as a substring (in some order).

%C a(7) = 40 by computer search.

%C a(8) >= 73 by formula (1) of Lipski.

%C a(8) <= 76 using 12345671825473861253846275138427163587...

%C                  ...26341568237415876412573641823178456231.

%C a(9) >= 130 by formula (1) of Lipski.

%C a(9) <= 149 using 1234567891245739681253946175283419726538...

%C                   ...4926137845926374159837241856931728643...

%C                   ...1597246159283674981635781642391874562...

%C                   ...89751384973251697248567213864957684.

%D I. Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, pp. 39-40.

%H W. Lipski, Jr., <a href="https://doi.org/10.1016/0012-365X(78)90157-7">On strings containing all subsets as substrings</a>, Discrete Mathematics 21, 1978, pp. 253-259.

%F a(n) >= binomial(n, ceiling(n/2)) + ceiling(n/2) - 1.  [Lipski, formula (1)]

%F a(n) >= n * ceiling(binomial(n, floor(n/2)) / n).      [Lipski, formula (3)]

%e 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).

%e Examples of optimal strings for n <= 7:

%e 1: 1

%e 2: 12

%e 3: 1231

%e 4: 12342413

%e 5: 1234512413524

%e 6: 123415643641253624531625

%e 7: 1234567214573126431523674256147325716357

%Y Cf. A062714.

%K nonn,hard,more

%O 1,2

%A _Alexander D. Healy_, Oct 23 2021