A137747 - OEIS

%I #22 Jun 11 2024 12:04:36

%S 0,0,0,0,0,0,0,1,7,34,143,555,2050,7343,25809,89642,308986,1059786,

%T 3623524,12365973,42160774,143701920,489891138,1670965268

%N Number of different strings of length n obtained from "abcdefg" by iteratively duplicating any substring.

%C See A137743 for more comments.

%H <a href="/index/Do#repeat">Index entries for doubling substrings</a>

%e a(k) = 0 for k<7, since no shorter string can be obtained by duplication of substrings.

%e a(7) = 1 = #{abcdefg},

%e a(8) = 7 = #{aabcdefg, abbcdefg, abccdefg, abcddefg, abcdeefg, abcdeffg, abcdefgg},

%e a(9) = 8*(8+1)/2-2 = 34:

%e for each letter we have one string of the form aaabcdefg;

%e for each 2-element subset {a,b}, {a,c}, ... we have the string with each of these two letters duplicated (i.e., aabbcdefg, aabccdefg, ...);

%e and for each of ab,bc,cd,...,fg we have the string with this substring duplicated (ababcdefg,...,abcdefgfg).

%e (See A137746 for the pattern.)

%o (PARI) A135473(14,7) /* function defined in A137743 */

%Y Cf. A137740-A137743, A135473, A137744-A137748.

%K more,nonn

%O 0,9

%A _M. F. Hasler_, Feb 10 2008

%E a(15)-a(20) from _Lars Blomberg_, Jan 12 2013

%E a(21) from _Michael S. Branicky_, Jan 07 2021

%E a(22)-a(23) from _Bert Dobbelaere_, Jun 11 2024