A137744 Number of different strings of length n obtained from "abcd" by iteratively duplicating any substring.

0, 0, 0, 0, 1, 4, 13, 40, 119, 348, 1014, 2966, 8726, 25820, 76823, 229814, 691186, 2089850, 6351448, 19398726, 59525641, 183462778, 567794458, 1764118964, 5501252365, 17214902088, 54047671324, 170218070930, 537678825668, 1703200355646, 5409721322664, 17226400794280

Offset: 0

Author

M. F. Hasler, Feb 10 2008

Keywords

• nonn

Comments

See A137743 for more comments.

Examples

			a(4) = # { abcd },
a(5) = # { aabcd, abbcd, abccd, abcdd },
a(6) = # { aaabcd, aabbcd, aabccd, aabcdd, ababcd, abbbcd, abbccd, abbcdd, abcbcd, abcccd, abccdd, abcdcd, abcddd }
		

Links

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

Crossrefs

Cf. A137740-A137743, A135473, A137745-A137748.

Programs

PARI

A135473(12,4)

Python

def process(s,n,catalog,cache):
    l=len(s)
    if l==n:
        catalog.add(s)
        return
    if s in cache:
        return
    cache.add(s)
    for x in range(l):
        for y in range(x+1,min(x+n-l,l)+1):
            process(s[:y]+s[x:],n,catalog,cache)
def A137744(n):
    catalog=set()
    cache=set()
    process("abcd",n,catalog,cache)
    return len(catalog)
# Bert Dobbelaere, Nov 01 2018

Extensions

a(13)-a(19) from Lars Blomberg, Jan 12 2013

a(20)-a(21) from Bert Dobbelaere, Nov 01 2018

a(22)-a(23) from Bert Dobbelaere, Jun 10 2024

a(24) onwards from Martin Fuller, Jun 07 2025