A135473 a(n) = number of strings of length n that can be obtained by starting with abc and repeatedly doubling any substring in place.

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

Offset: 1

Author

Max Alekseyev, Jan 07 2008

Keywords

• nonn

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.

Examples

			n=3: abc
n=4: aabc, abbc, abcc
n=5: aaabc, abbbc, abccc, aabbc, aabcc, abbcc, ababc, abcbc
		

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

• Martin Fuller, Table of n, a(n) for n = 1..44
• Index entries for doubling substrings

Crossrefs

Cf. A135017, A135156, A135157, A135475, A135479, A130838.

Cf. also A137739, A137740, A137741, A137742, A137743, A137744, A137745, A137746, A137747, A137748.

Formula

Binomial transform of A135017. - Martin Fuller, Jun 06 2025

Empirically, grows like 3^n.

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