A135473 - OEIS

%I #21 Nov 01 2018 21:45:12

%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), 119-123.

%D Juergen Dassow, Victor Mitrana and Gheorghe Paun: On the Regularity of Duplication Closure. Bulletin of the EATCS 69 (1999), 133-136.

%D Ming-wei Wang, On the Irregularity of the Duplication Closure, Bulletin of the EATCS, Vol. 70, 2000, 162-163.

%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