cp's OEIS Frontend

A134457 a(n) = number of length-n binary strings with A006697(n) distinct substrings.

%I A134457 #18 May 08 2016 22:39:37
%S A134457 1,2,2,6,8,4,18,38,48,40,16,80,210,402,644,852,928,912,704,256,1344,
%T A134457 3944,9276,19448,37090,65602,107388,160760,220200
%N A134457 a(n) = number of length-n binary strings with A006697(n) distinct substrings.
%C A134457 Here by "substring" one means a contiguous block within a string (often called "subword" or "factor").
%H A134457 Martin Fuller, <a href="/A134457/a134457.txt">Algorithm and table of n, c(n) for n = 1..69.</a>
%H A134457 Abraham Flaxman, Aram W. Harrow, Gregory B. Sorkin, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r8">Strings with Maximally Many Distinct Subsequences and Substrings</a>, Electronic J. Combinatorics 11 (1) (2004), Paper R8.
%H A134457 Abraham Flaxman, Aram W. Harrow, Gregory B. Sorkin, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r8/comment">Comments on the previous paper</a>.
%H A134457 Antal Iványi, <a href="http://compalg.inf.elte.hu/~tony/Kutatas/PerfectArrays/On_the_d-complexity.pdf">On the d-complexity of words</a>, Ann. Univ. Sci. Budapest. Sect. Comput. 8 (1987), 69-90 (1988).
%H A134457 Jeffrey Shallit, <a href="https://cs.uwaterloo.ca/~shallit/Papers/m0.ps">On the maximum number of distinct factors in a binary string</a>, Graphs Combin. 9 (1993), no. 2, 197-200.
%e A134457 Table giving n, A006697(n) = maximal number of distinct substrings of a binary string of length n, a(n), c(n) = lexically first length-n binary string with A006697(n) distinct substrings.
%e A134457 n A006697(n) a(n) c(n)
%e A134457 0 1 1 null
%e A134457 1 2 2 0
%e A134457 2 4 2 01
%e A134457 3 6 6 001
%e A134457 4 9 8 0010
%e A134457 5 13 4 00110
%e A134457 6 17 18 000110
%e A134457 7 22 38 0001011
%e A134457 8 28 48 00010110
%e A134457 9 35 40 000101100
%e A134457 10 43 16 0001011100
%e A134457 11 51 80 00001011100
%e A134457 12 60 210 000010011101
%e A134457 13 70 402 0000100110111
%e A134457 14 81 644 00001001101110
%e A134457 15 93 852 000010011010111
%e A134457 16 106 928 0000100110101110
%e A134457 17 120 912 00001001101011100
%e A134457 18 135 704 000010011010111000
%e A134457 19 151 256 0000100110101111000
%e A134457 20 167 1344 00000100110101111000
%e A134457 21 184 3944 000001000110101111001
%e A134457 22 202 9276 0000010001100101111010
%e A134457 23 221 19448 00000100011001010111101
%e A134457 24 241 37090 000001000110010101111010
%e A134457 25 262 65602 0000010001100101001111011
%e A134457 26 284 107388 00000100011001010011101111
%e A134457 27 307 160760 000001000110010100111011110
%e A134457 28 331 220200 0000010001100101001110101111
%e A134457 For (conjectural?) further values see the _Martin Fuller_ link.
%Y A134457 Cf. A006697, A134466(n) = decimal value of c(n) interpreted as a binary number.
%K A134457 nonn,more
%O A134457 0,2
%A A134457 _David W. Wilson_, Dec 17 2007
%E A134457 Link to comments on history of the problem added by _Jeffrey Shallit_, May 08 2016