login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A134457 a(n) = number of length-n binary strings with A006697(n) distinct substrings. 4
1, 2, 2, 6, 8, 4, 18, 38, 48, 40, 16, 80, 210, 402, 644, 852, 928, 912, 704, 256, 1344, 3944, 9276, 19448, 37090, 65602, 107388, 160760, 220200 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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

LINKS

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

Martin Fuller, Algorithm and table of n, c(n) for n = 1..69.

Abraham Flaxman, Aram W. Harrow, Gregory B. Sorkin, Strings with Maximally Many Distinct Subsequences and Substrings, Electronic J. Combinatorics 11 (1) (2004), Paper R8.

Abraham Flaxman, Aram W. Harrow, Gregory B. Sorkin, Comments on the previous paper.

Antal Iványi, On the d-complexity of words, Ann. Univ. Sci. Budapest. Sect. Comput. 8 (1987), 69-90 (1988).

Jeffrey Shallit, On the maximum number of distinct factors in a binary string, Graphs Combin. 9 (1993), no. 2, 197-200.

EXAMPLE

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.

n A006697(n) a(n) c(n)

0 1 1 null

1 2 2 0

2 4 2 01

3 6 6 001

4 9 8 0010

5 13 4 00110

6 17 18 000110

7 22 38 0001011

8 28 48 00010110

9 35 40 000101100

10 43 16 0001011100

11 51 80 00001011100

12 60 210 000010011101

13 70 402 0000100110111

14 81 644 00001001101110

15 93 852 000010011010111

16 106 928 0000100110101110

17 120 912 00001001101011100

18 135 704 000010011010111000

19 151 256 0000100110101111000

20 167 1344 00000100110101111000

21 184 3944 000001000110101111001

22 202 9276 0000010001100101111010

23 221 19448 00000100011001010111101

24 241 37090 000001000110010101111010

25 262 65602 0000010001100101001111011

26 284 107388 00000100011001010011101111

27 307 160760 000001000110010100111011110

28 331 220200 0000010001100101001110101111

For (conjectural?) further values see the Martin Fuller link.

CROSSREFS

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

Sequence in context: A106166 A101343 A284748 * A326479 A306688 A092522

Adjacent sequences:  A134454 A134455 A134456 * A134458 A134459 A134460

KEYWORD

nonn,more

AUTHOR

David W. Wilson, Dec 17 2007

EXTENSIONS

Link to comments on history of the problem added by Jeffrey Shallit, May 08 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 05:39 EDT 2020. Contains 333105 sequences. (Running on oeis4.)