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

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A135473 a(n) = number of strings of length n that can be obtained by starting with abc and repeatedly doubling any substring in place. 15
 0, 0, 1, 3, 8, 21, 54, 138, 355, 924, 2432, 6461, 17301, 46657, 126656, 345972, 950611, 2626253, 7292268, 20342805, 56993909, 160317859, 452642235, 1282466920, 3645564511, 10395117584, 29727982740, 85251828792, 245120276345, 706529708510, 2041260301955, 5910531770835, 17149854645474, 49859456251401, 145223624492108, 423722038708874, 1238318400527185 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,4 COMMENTS The problem can be restated as follows: look at the language L over {1,2,3}* which contains 123 and is closed under duplication. What is the growth function of L (or its subword complexity function)? It is known that the language L is not regular [Wang] Several generalizations suggest themselves: What if we start with k different letters (here k=3)? What if we start with k different letters and fix the number of duplications d? See A137739, A137740, A137741, A137742, A137743, A137744, A137745, A137746, A137747, A137748. REFERENCES D. P. Bovet and S. Varricchio, On the regularity of languages on a binary alphabet generated by copying systems, Information Processing Letters, 44 (1992), 119-123. Juergen Dassow, Victor Mitrana and Gheorghe Paun: On the Regularity of Duplication Closure. Bulletin of the EATCS 69 (1999), 133-136. Ming-wei Wang, On the Irregularity of the Duplication Closure, Bulletin of the EATCS, Vol. 70, 2000, 162-163. LINKS FORMULA Empirically, grows like 3^n. EXAMPLE n=3: abc n=4: aabc, abbc, abcc n=5: aaabc, abbbc, abccc, aabbc, aabcc, abbcc, ababc, abcbc CROSSREFS Cf. A135017, A135156, A135157, A135475, A135479, A130838. Cf. also A137739, A137740, A137741, A137742, A137743, A137744, A137745, A137746, A137747, A137748. Sequence in context: A094723 A127358 A077849 * A242452 A190139 A005580 Adjacent sequences:  A135470 A135471 A135472 * A135474 A135475 A135476 KEYWORD nonn AUTHOR Max Alekseyev, Jan 07 2008 EXTENSIONS a(19) - a(33) from David Applegate, Feb 12 2008 Extended to 37 terms by David Applegate, Feb 16 2008 Thanks to Robert Mercas and others for comments and references - N. J. A. Sloane, Apr 26 2013 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.

Last modified March 29 20:20 EDT 2020. Contains 333117 sequences. (Running on oeis4.)