A137748 Number of different strings of length n obtained from "abcdefgh" by iteratively duplicating any substring.
0, 0, 0, 0, 0, 0, 0, 0, 1, 8, 43, 196, 814, 3188, 12018, 44178, 159660, 570262, 2019964, 7112774, 24940259, 87191430, 304203350, 1059928798, 3690123329, 12841859908, 44685411866, 155506929954, 541315997526, 1885045535888, 6567524381098, 22893857129004, 79853551127325
Offset: 0
Keywords
Examples
a(k) = 0 for k<8, since no shorter string can be obtained by duplication of substrings.
a(8) = 1 = # { abcdefgh }.
a(9) = 8 = # { aabcdefgh, abbcdefgh, abccdefgh, abcddefgh, abcdeefgh, abcdeffgh, abcdefggh, abcdefghh }.
a(10) = (8+1)*(8+2)/2-2 = 43:
for each letter we have one string of the form aaabcdefgh;
for each 2-element subset {a,b}, {a,c}, ... we have the string with each of these two letters duplicated (i.e., aabbcdefgh, aabccdefgh, ...),
and for each of ab,bc,cd,...,gh we have the string with this substring duplicated (ababcdefgh,...,abcdefghgh).
Extensions
a(15)-a(17) from Alois P. Heinz, Sep 01 2011
a(18)-a(20) from Lars Blomberg, Jan 12 2013
a(21)-a(22) from Bert Dobbelaere, Dec 30 2018
a(23)-a(32) from Martin Fuller, Jun 08 2025
Comments