A135473
a(n) = number of strings of length n that can be obtained by starting with abc and repeatedly doubling any substring in place.
Original entry on oeis.org
0, 0, 1, 3, 8, 21, 54, 138, 355, 924, 2432, 6461, 17301, 46657, 126656, 345972, 950611, 2626253, 7292268, 20342805, 56993909, 160317859, 452642235, 1282466920, 3645564511, 10395117584, 29727982740, 85251828792, 245120276345, 706529708510, 2041260301955, 5910531770835, 17149854645474, 49859456251401, 145223624492108, 423722038708874, 1238318400527185
Offset: 1
n=3: abc
n=4: aabc, abbc, abcc
n=5: aaabc, abbbc, abccc, aabbc, aabcc, abbcc, ababc, abcbc
- D. P. Bovet and S. Varricchio, On the regularity of languages on a binary alphabet generated by copying systems, Information Processing Letters, 44 (1992), 119-123.
- Juergen Dassow, Victor Mitrana and Gheorghe Paun: On the Regularity of Duplication Closure. Bulletin of the EATCS 69 (1999), 133-136.
- Ming-wei Wang, On the Irregularity of the Duplication Closure, Bulletin of the EATCS, Vol. 70, 2000, 162-163.
Thanks to Robert Mercas and others for comments and references -
N. J. A. Sloane, Apr 26 2013
A137743
Number T(m,n) of different strings of length n obtained from "123...m" by iteratively duplicating any substring; formatted as upper right triangle.
Original entry on oeis.org
1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 8, 8, 4, 1, 1, 16, 21, 13, 5, 1, 1, 32, 54, 40, 19, 6, 1, 1, 64, 138, 119, 66, 26, 7, 1, 1, 128, 355, 348, 218, 100, 34, 8, 1, 1, 256, 924, 1014, 700, 360, 143, 43, 9, 1, 1, 512, 2432, 2966, 2218, 1246, 555, 196, 53, 10, 1
Offset: 1
The full matrix is:
[ 1, 1, 1, 1, 1, 1, 1,_ 1,_ 1,__ 1,__ 1,...] (= A000012)
[[], 1, 2, 4, 8,16,32, 64,128, 256, 512,...] (= A000079)
[[],[], 1, 3, 8,21,54,138,355, 924,2432,...] (= A135473)
[[],[],[], 1, 4,13,40,119,348,1014,2966,...] (= A137744)
[[],[],[],[], 1, 5,19, 66,218, 700,2218,...] (= A137745)
[[],[],[],[],[], 1, 6, 26,100, 360,1246,...] (= A137746)
[[],[],[],[],[],[], 1,_ 7, 34, 143, 555,...] (= A137747)
...
-
A135473(Nmax,d=3 /* # digits in the initial string = row of the triangular matrix */)={ local( t,tt,ee,lsb, L=vector(Nmax,i,[]) /*store separately words of given length*/, w=log(d-.5)\log(2)+1/* bits required to code d distinct digits*/); L[d]=Set(sum(i=1,d-1,i<<(w*i))); for( i=d,Nmax-1, for( j=1, #t=eval(L[i]), forstep( ee=w,w*i,w, /*upper cutting point*/ forstep( len=w, min(ee,w*(Nmax-i)),w, /* length of substring */ lsb = bitand( tt=t[j], 1<A137743(10,d)))
A137748
Number of different strings of length n obtained from "abcdefgh" by iteratively duplicating any substring.
Original entry on oeis.org
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
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).
A137746
Number of different strings of length n obtained from "abcdef" by iteratively duplicating any substring.
Original entry on oeis.org
0, 0, 0, 0, 0, 0, 1, 6, 26, 100, 360, 1246, 4217, 14102, 46861, 155212, 513336, 1697264, 5614670, 18594258, 61671770, 204907302, 682110940, 2275141754, 7603690251, 25462152854, 85428752530, 287163766530, 967046587261, 3262356284310, 11024401089607, 37315689561280, 126506891234231
Offset: 0
a(k) = 0 for k<6, since no shorter string can be obtained by duplication
a(6) = 1 = # { abcdef },
a(7) = 6 = # { aabcdef, abbcdef, abccdef, abcddef, abcdeef, abcdeff },
a(8) = 26 = # { aaabcdef, aabbcdef, aabccdef, aabcddef, aabcdeef, aabcdeff, ababcdef, abbbcdef, abbccdef, abbcddef, abbcdeef, abbcdeff, abcbcdef, abcccdef, abccddef, abccdeef, abccdeff, abcdcdef, abcdddef, abcddeef, abcddeff, abcdedef, abcdeeef, abcdeeff, abcdefef, abcdefff }.
Showing 1-4 of 4 results.
Comments