
COMMENTS

It would be more natural to include the empty substring, which would result in the sequence b(n)=a(n)+1; all values computed so far confirm the conjecture that a(n)+1 = A006697(n).  M. F. Hasler, Dec 17 2007
In addition to the example given, computation finds 17 other binary strings of length 6 which contain the maximal number a(6)=16 of distinct substrings. Interestingly, each of the 18 such instances gives the same numbers of substrings of each possible length, in this case 2,4,4,3,2,1 substrings of lengths 1 through 6, respectively.
Calculations suggest that, for any n>0, binary strings of length n exist such that the number of distinct substrings of length k, 1<=k<=n, is as large as possible consistent with basic counting principles, i.e., nk+1 substrings of length k starting at each of the nk+1 possible starting positions, subject to the condition, however, that there cannot be more than 2^k distinct binary strings of length k. This suggests the following conjecture. Conjecture: The maximum number a(n) of distinct substrings of a binary string of length n is given by a(n) = Sum_{k=1..n} t(k) where t(k) is the smaller of 2^k and nk+1.
Conjecture: a(n) = A006697(n)1.  Vladeta Jovovic, Sep 19 2005
Conjecture: a(n) = 2^(m+1)2 + (nm)(nm+1)/2, where m = floor(n+1LambertW( 2^(n+1) * log(2) ) / log(2) ) = integer part of the solution to 2^x = n+1x. This is based on the reasoning that you can construct the word of length n so that it contains the maximal possible number, max( nk+1, 2^k ), of different substrings of length k.  M. F. Hasler, Dec 17 2007
From Peter Pein (petsie(AT)dordos.net), Jan 18 2008: (Start)
The following heuristic seems to work for computing the maximal number of distinct substrings of a binary string of length n.
Start with the empty list and at each step try to insert a zero or a one at each possible position. Then pick the first list with the maximal number of sublists and start over.
Say we have had {0,0,1,1,0} as one of the lists with the maximal number of sublists. Then my candidates for the next test are:
With[{lastbest = {0, 0, 1, 1, 0}}, Union[Flatten[ Outer[Insert[lastbest, #2, #1] &, Range[1 + Length[lastbest]], {0, 1}, 1], 1]]]
{{0, 0, 0, 1, 1, 0}, {0, 0, 1, 0, 1, 0}, {0, 0, 1, 1, 0, 0}, {0, 0, 1, 1, 0, 1}, {0, 0, 1, 1, 1, 0}, {0, 1, 0, 1, 1, 0}, {1, 0, 0, 1, 1, 0}}
See http://freenethomepage.de/Peter_Berlin/Mathe/heuristicA094913.nb for the Mathematica notebook with the complete (simple) algorithm. There's a screenshot too (same URL but with .png instead of .nb).
If this works correctly, the first 100 values of A094913 are calculated in 30 secs.
(End) [See also the remarks in the Fuller link in A134457.]
From Jon Perry, Nov 16 2010: (Start)
Conjecture: column sums of:
1 3 5 7 9 11 13 ...
1 3 5 7 ...
1 ...
....................

1 3 5 8 12 16 21 ... (End)
