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

%I #18 May 08 2016 22:39:37

%S 1,2,2,6,8,4,18,38,48,40,16,80,210,402,644,852,928,912,704,256,1344,

%T 3944,9276,19448,37090,65602,107388,160760,220200

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

%C Here by "substring" one means a contiguous block within a string (often called "subword" or "factor").

%H Martin Fuller, <a href="/A134457/a134457.txt">Algorithm and table of n, c(n) for n = 1..69.</a>

%H 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 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 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 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 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 n A006697(n) a(n) c(n)

%e 0 1 1 null

%e 1 2 2 0

%e 2 4 2 01

%e 3 6 6 001

%e 4 9 8 0010

%e 5 13 4 00110

%e 6 17 18 000110

%e 7 22 38 0001011

%e 8 28 48 00010110

%e 9 35 40 000101100

%e 10 43 16 0001011100

%e 11 51 80 00001011100

%e 12 60 210 000010011101

%e 13 70 402 0000100110111

%e 14 81 644 00001001101110

%e 15 93 852 000010011010111

%e 16 106 928 0000100110101110

%e 17 120 912 00001001101011100

%e 18 135 704 000010011010111000

%e 19 151 256 0000100110101111000

%e 20 167 1344 00000100110101111000

%e 21 184 3944 000001000110101111001

%e 22 202 9276 0000010001100101111010

%e 23 221 19448 00000100011001010111101

%e 24 241 37090 000001000110010101111010

%e 25 262 65602 0000010001100101001111011

%e 26 284 107388 00000100011001010011101111

%e 27 307 160760 000001000110010100111011110

%e 28 331 220200 0000010001100101001110101111

%e For (conjectural?) further values see the _Martin Fuller_ link.

%Y Cf. A006697, A134466(n) = decimal value of c(n) interpreted as a binary number.

%K nonn,more

%O 0,2

%A _David W. Wilson_, Dec 17 2007

%E Link to comments on history of the problem added by _Jeffrey Shallit_, May 08 2016