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
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 }.
A137738
Coefficients of the polynomial giving the n-th diagonal of A137743 * n!, read as an upper right triangle.
Original entry on oeis.org
1, 0, 1, -2, 3, 1, -24, 14, 9, 1, -288, 54, 95, 18, 1, -4320, -136, 1110, 315, 30, 1, -80640, -12300, 15064, 5775, 775, 45, 1
Offset: 0
We have the following formulas for T(m,n) as given in A137743:
T(n,n) = 1, T(n,n+1) = n, T(n,n+2) = (n+1)(n+2)/2 - 2,
T(n,n+3) = A137742 = (1/6)*(n-1)*(n+6)*(n+4) for n>1, for n=1 this formula gives 0 instead of 1.
T(n,n+4) = A137741 = (1/24)*(n+3)*(n^3+15*n^2+50*n-96) for n>2, for n=2 this gives 15 instead of 16.
T(n,n+5) = A137740 = (1/5!)*(n+4)*(n^2+3*n-8)*(n^2+23*n+150)+4 for n>3, for n=3 this gives 137 instead of 138.
T(n,n+6) = A137739 = (1/6!)*(n+9)*(n^5+36*n^4+451*n^3+1716*n^2-380*n-8880)-1 for n>4, for n=4 this gives 1013 instead of 1014.
They satisfy the following relations:
T(n,n+2) = sum( T(k,k+1), k=0..n+1) - 2
T(n,n+3) = sum( T(k,k+2), k=1..n+1) - 5
T(n,n+4) = sum( T(k,k+3), k=2..n+1) - 12 - n
T(n,n+5) = sum( T(k,k+4), k=3..n+1) - 21 - 7n/2 - n^2/2
T(n,n+6) = sum( T(k,k+5), k=4..n+1) + 49 - 25n/3 - 5n^2/2 - n^3/6
Showing 1-3 of 3 results.
Comments