cp's OEIS Frontend

A137748 Number of different strings of length n obtained from "abcdefgh" by iteratively duplicating any substring.

%I A137748 #22 Jun 08 2025 13:43:19
%S A137748 0,0,0,0,0,0,0,0,1,8,43,196,814,3188,12018,44178,159660,570262,
%T A137748 2019964,7112774,24940259,87191430,304203350,1059928798,3690123329,
%U A137748 12841859908,44685411866,155506929954,541315997526,1885045535888,6567524381098,22893857129004,79853551127325
%N A137748 Number of different strings of length n obtained from "abcdefgh" by iteratively duplicating any substring.
%C A137748 See A137743 for more comments.
%H A137748 <a href="/index/Do#repeat">Index entries for doubling substrings</a>
%e A137748 a(k) = 0 for k<8, since no shorter string can be obtained by duplication of substrings.
%e A137748 a(8) = 1 = # { abcdefgh }.
%e A137748 a(9) = 8 = # { aabcdefgh, abbcdefgh, abccdefgh, abcddefgh, abcdeefgh, abcdeffgh, abcdefggh, abcdefghh }.
%e A137748 a(10) = (8+1)*(8+2)/2-2 = 43:
%e A137748 for each letter we have one string of the form aaabcdefgh;
%e A137748 for each 2-element subset {a,b}, {a,c}, ... we have the string with each of these two letters duplicated (i.e., aabbcdefgh, aabccdefgh, ...),
%e A137748 and for each of ab,bc,cd,...,gh we have the string with this substring duplicated (ababcdefgh,...,abcdefghgh).
%o A137748 (PARI) A135473(14,8) /* function defined in A137743 */
%Y A137748 Cf. A137740-A137743, A135473, A137744-A137747.
%K A137748 nonn
%O A137748 0,10
%A A137748 _M. F. Hasler_, Feb 10 2008
%E A137748 a(15)-a(17) from _Alois P. Heinz_, Sep 01 2011
%E A137748 a(18)-a(20) from _Lars Blomberg_, Jan 12 2013
%E A137748 a(21)-a(22) from _Bert Dobbelaere_, Dec 30 2018
%E A137748 a(23)-a(32) from _Martin Fuller_, Jun 08 2025