A137747 Number of different strings of length n obtained from "abcdefg" by iteratively duplicating any substring.
0, 0, 0, 0, 0, 0, 0, 1, 7, 34, 143, 555, 2050, 7343, 25809, 89642, 308986, 1059786, 3623524, 12365973, 42160774, 143701920, 489891138, 1670965268, 5703849531, 19488123707, 66652727622, 228212500386, 782258463295, 2684464903407, 9222805414564, 31722184749945, 109232421818064
Offset: 0
Keywords
Examples
a(k) = 0 for k<7, since no shorter string can be obtained by duplication of substrings.
a(7) = 1 = #{abcdefg},
a(8) = 7 = #{aabcdefg, abbcdefg, abccdefg, abcddefg, abcdeefg, abcdeffg, abcdefgg},
a(9) = 8*(8+1)/2-2 = 34:
for each letter we have one string of the form aaabcdefg;
for each 2-element subset {a,b}, {a,c}, ... we have the string with each of these two letters duplicated (i.e., aabbcdefg, aabccdefg, ...);
and for each of ab,bc,cd,...,fg we have the string with this substring duplicated (ababcdefg,...,abcdefgfg).
(See A137746 for the pattern.)
Extensions
a(15)-a(20) from Lars Blomberg, Jan 12 2013
a(21) from Michael S. Branicky, Jan 07 2021
a(22)-a(23) from Bert Dobbelaere, Jun 11 2024
a(24)-a(32) from Martin Fuller, Jun 08 2025
Comments