|
%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
| 