A385111 Triangle read by rows: T(n,k) is the least cardinality of a set of binary strings of length k such that any binary string of length n contains one of the strings in the set as a substring; 0 <= k <= n.

1, 1, 2, 1, 2, 4, 1, 2, 3, 8, 1, 2, 3, 6, 16, 1, 2, 3, 5, 10, 32, 1, 2, 3, 4, 9, 20, 64, 1, 2, 3, 4, 7, 15

Offset

0,3

Comments

For any binary string s of length k, there is a string of length n such that all its length-k substrings are cyclic shifts of s. (Simply repeat s until the length is n.) This implies that T(n,k) >= A000031(k).

It is clear that T(n,k) is nonincreasing in n for any fixed k, so T(n,k) reaches a limiting value as n increases. Apparently, this limiting value is A000031(k). For 0 <= k <= 4, the smallest values of n for which T(n,k) = A000031(k) are 0, 1, 3, 6, 9, respectively.

Equivalently, for k >= 1, T(n,k) is the least number of edges that must be removed from the binary (k-1)-dimensional de Bruijn graph such that the remaining graph does not contain any walk of length n-k+1. For a fixed k and sufficiently large n, this is the least number of edges that must be removed in order to make the remaining graph acyclic.

Links

Table of n, a(n) for n=0..33.

Formula

T(n,n) = 2^n.

T(n,k) <= T(n-1,k).

T(n,k) >= A000031(k).

Example

Triangle begins:
  n\k| 0  1  2  3  4  5  6   7   8   9
  ---+--------------------------------
  0  | 1
  1  | 1  2
  2  | 1  2  4
  3  | 1  2  3  8
  4  | 1  2  3  6 16
  5  | 1  2  3  5 10 32
  6  | 1  2  3  4  9 20 64
  7  | 1  2  3  4  7 15  ? 128
  8  | 1  2  3  4  7 14  ?   ? 256
  9  | 1  2  3  4  6 12  ?   ?   ? 512
Any binary string of length n >= 3 contains one of the substrings 00, 01, 11 of length k = 2. The length-n strings 00...0, 11...1, and 0101... show that 00, 11, and either 01 or 10 are necessary, so T(n,2) = 3 for n >= 3.

Crossrefs

Cf. A000031.

Main diagonal gives A000079.

Sequence in context: A174843 A253572 A141539 * A340547 A376033 A327844

Adjacent sequences: A385108 A385109 A385110 * A385112 A385113 A385114

Keyword

nonn,tabl,more

Author

Pontus von Brömssen, Oct 21 2025

Status

approved