%I
%S 0,0,1,3,8,21,54,138,355,924,2432,6461,17301,46657,126656,345972,
%T 950611,2626253,7292268,20342805,56993909,160317859,452642235,
%U 1282466920,3645564511,10395117584,29727982740,85251828792,245120276345,706529708510,2041260301955,5910531770835,17149854645474,49859456251401,145223624492108,423722038708874,1238318400527185
%N a(n) = number of strings of length n that can be obtained by starting with abc and repeatedly doubling any substring in place.
%C 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)?
%C It is known that the language L is not regular [Wang]
%C 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.
%D D. P. Bovet and S. Varricchio, On the regularity of languages on a binary alphabet generated by copying systems, Information Processing Letters, 44 (1992), 119123.
%D Juergen Dassow, Victor Mitrana and Gheorghe Paun: On the Regularity of Duplication Closure. Bulletin of the EATCS 69 (1999), 133136.
%D Mingwei Wang, On the Irregularity of the Duplication Closure, Bulletin of the EATCS, Vol. 70, 2000, 162163.
%H <a href="/index/Do#repeat">Index entries for doubling substrings</a>
%F Empirically, grows like 3^n.
%e n=3: abc
%e n=4: aabc, abbc, abcc
%e n=5: aaabc, abbbc, abccc, aabbc, aabcc, abbcc, ababc, abcbc
%Y Cf. A135017, A135156, A135157, A135475, A135479, A130838.
%Y Cf. also A137739, A137740, A137741, A137742, A137743, A137744, A137745, A137746, A137747, A137748.
%K nonn
%O 1,4
%A _Max Alekseyev_, Jan 07 2008
%E a(19)  a(33) from _David Applegate_, Feb 12 2008
%E Extended to 37 terms by _David Applegate_, Feb 16 2008
%E Thanks to Robert Mercas and others for comments and references  _N. J. A. Sloane_, Apr 26 2013
