cp's OEIS Frontend

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

%I A348574 #36 Jan 01 2022 21:21:21
%S A348574 1,2,4,8,13,24,40
%N 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).
%C A348574 a(7) = 40 by computer search.
%C A348574 a(8) >= 73 by formula (1) of Lipski.
%C A348574 a(8) <= 76 using 12345671825473861253846275138427163587...
%C A348574                  ...26341568237415876412573641823178456231.
%C A348574 a(9) >= 130 by formula (1) of Lipski.
%C A348574 a(9) <= 149 using 1234567891245739681253946175283419726538...
%C A348574                   ...4926137845926374159837241856931728643...
%C A348574                   ...1597246159283674981635781642391874562...
%C A348574                   ...89751384973251697248567213864957684.
%D A348574 I. Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, pp. 39-40.
%H A348574 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 A348574 a(n) >= binomial(n, ceiling(n/2)) + ceiling(n/2) - 1.  [Lipski, formula (1)]
%F A348574 a(n) >= n * ceiling(binomial(n, floor(n/2)) / n).      [Lipski, formula (3)]
%e A348574 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 A348574 Examples of optimal strings for n <= 7:
%e A348574 1: 1
%e A348574 2: 12
%e A348574 3: 1231
%e A348574 4: 12342413
%e A348574 5: 1234512413524
%e A348574 6: 123415643641253624531625
%e A348574 7: 1234567214573126431523674256147325716357
%Y A348574 Cf. A062714.
%K A348574 nonn,hard,more
%O A348574 1,2
%A A348574 _Alexander D. Healy_, Oct 23 2021