A137748 -id:A137748 - cp's OEIS frontend

A135473 a(n) = number of strings of length n that can be obtained by starting with abc and repeatedly doubling any substring in place.

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

Max Alekseyev, Jan 07 2008

nonn

The problem can be restated as follows: look at the language L over {1,2,3}* which contains 123 and is closed under duplication. What is the growth function of L (or its subword complexity function)?
It is known that the language L is not regular [Wang]
Several generalizations suggest themselves: What if we start with k different letters (here k=3)? What if we start with k different letters and fix the number of duplications d? See A137739, A137740, A137741, A137742, A137743, A137744, A137745, A137746, A137747, A137748.

			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.

Martin Fuller, Table of n, a(n) for n = 1..44
Index entries for doubling substrings

Cf. A135017, A135156, A135157, A135475, A135479, A130838.

Cf. also A137739, A137740, A137741, A137742, A137743, A137744, A137745, A137746, A137747, A137748.

Binomial transform of A135017. - Martin Fuller, Jun 06 2025

Empirically, grows like 3^n.

a(19) - a(33) from David Applegate, Feb 12 2008
Extended to 37 terms by David Applegate, Feb 16 2008
Thanks to Robert Mercas and others for comments and references - N. J. A. Sloane, Apr 26 2013

A137740 Number of different strings of length n+5 obtained from "123...n" by iteratively duplicating any substring.

Original entry on oeis.org

1, 32, 138, 348, 700, 1246, 2050, 3188, 4749, 6836, 9567, 13076, 17514, 23050, 29872, 38188, 48227, 60240, 74501, 91308, 110984, 133878, 160366, 190852, 225769, 265580, 310779, 361892, 419478, 484130, 556476, 637180, 726943, 826504, 936641, 1058172, 1191956

Offset: 1

M. F. Hasler, Feb 10 2008

See A137743 for comments and examples.

Index entries for doubling substrings
Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

Cf. A137739-A137743, A135473, A137744-A137748.

LinearRecurrence[{6,-15,20,-15,6,-1},{1,32,138,348,700,1246,2050,3188,4749},40] (* Harvey P. Dale, Oct 18 2020 *)

A137740(n)=if(n<2,1,n=A135473(n+5,n);n[ #n]) /* function A135473 defined in A137743 */

A137740(n)=if(n>4,n*(n*(n*(n*(n+30)+315)+1110)-136)/5!-36,[1,32,138,348][n])

a(n) = (n+4)(n^2+3n-8)(n^2+23n+150)/5!+4 for n>4.

G.f.: x*(x^8+2*x^7-7*x^6-20*x^5+57*x^4-20*x^3-39*x^2+26*x+1) / (x-1)^6. - Colin Barker, Nov 04 2013

More terms from Colin Barker, Nov 04 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

M. F. Hasler, Feb 10 2008

The sequence T(m,m+3) = 1,8,21,40,66,100,143,196,260,... = A137742.

			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)
...

Index entries for doubling substrings

Cf. A135473, A137740-A137742, A137744-A137748.

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)))

T(m,n)=0 for n < m, T(m,m)=T(1,n)=1, T(m,m+1)=m, T(m,m+2)=C(m+2,2)-2 = A034856(m); T(2,2+n)=2^n.

For m > 3, T(m,m+2) = T(m-1,m+1) + T(m,m+1) + T(m+1,m+1). - Thomas Anton, Nov 05 2018

More terms from Alois P. Heinz, Aug 31 2011

A137744 Number of different strings of length n obtained from "abcd" by iteratively duplicating any substring.

Original entry on oeis.org

0, 0, 0, 0, 1, 4, 13, 40, 119, 348, 1014, 2966, 8726, 25820, 76823, 229814, 691186, 2089850, 6351448, 19398726, 59525641, 183462778, 567794458, 1764118964, 5501252365, 17214902088, 54047671324, 170218070930, 537678825668, 1703200355646, 5409721322664, 17226400794280

Offset: 0

M. F. Hasler, Feb 10 2008

nonn

See A137743 for more comments.

			a(4) = # { abcd },
a(5) = # { aabcd, abbcd, abccd, abcdd },
a(6) = # { aaabcd, aabbcd, aabccd, aabcdd, ababcd, abbbcd, abbccd, abbcdd, abcbcd, abcccd, abccdd, abcdcd, abcddd }

Martin Fuller, Table of n, a(n) for n = 0..34
Index entries for doubling substrings

Cf. A137740-A137743, A135473, A137745-A137748.

PARI
```
A135473(12,4)
```

def process(s,n,catalog,cache):
    l=len(s)
    if l==n:
        catalog.add(s)
        return
    if s in cache:
        return
    cache.add(s)
    for x in range(l):
        for y in range(x+1,min(x+n-l,l)+1):
            process(s[:y]+s[x:],n,catalog,cache)
def A137744(n):
    catalog=set()
    cache=set()
    process("abcd",n,catalog,cache)
    return len(catalog)
# Bert Dobbelaere, Nov 01 2018

a(13)-a(19) from Lars Blomberg, Jan 12 2013
a(20)-a(21) from Bert Dobbelaere, Nov 01 2018
a(22)-a(23) from Bert Dobbelaere, Jun 10 2024
a(24) onwards from Martin Fuller, Jun 07 2025

A137742 a(n) = (n-1)(n+4)(n+6)/6 for n > 1, a(1)=1.

Original entry on oeis.org

1, 8, 21, 40, 66, 100, 143, 196, 260, 336, 425, 528, 646, 780, 931, 1100, 1288, 1496, 1725, 1976, 2250, 2548, 2871, 3220, 3596, 4000, 4433, 4896, 5390, 5916, 6475, 7068, 7696, 8360, 9061, 9800, 10578, 11396, 12255, 13156, 14100, 15088, 16121, 17200, 18326, 19500

Offset: 1

M. F. Hasler, Feb 10 2008

Also the number of different strings of length n+3 obtained from "123...n" by iteratively duplicating any substring (see A137743 for comments and examples). This is the principal (although not simplest) definition of this sequence and explains why a(1)=1 and not 0.

For n >= 3, sequence appears (not yet proved by induction) to give the number of multiplications between two nonzero matrix elements in calculating the product of two n X n Hessenberg matrices (square matrices which have 0's below the subdiagonal, other elements being in general nonzero). - John M. Coffey, Jun 21 2016

			a(5) = (5-1)*(5+4)*(5+6)/6 = 4*9*11/6 = 66. - _Michael B. Porter_, Jul 02 2016

Vincenzo Librandi, Table of n, a(n) for n = 1..10000
Index entries for doubling substrings
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

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

See A275874 for another version.

[1] cat [(n^3+9*n^2+14*n-24)/6: n in [2..46]];  // Bruno Berselli, Aug 23 2011

Join[{1},Table[Binomial[n,3]-2*n,{n,6,60}]] (*or*) Join[{1},Table[(n-1)(n+4)(n+6)/6,{n,2,56}]] (* Vladimir Joseph Stephan Orlovsky, Apr 22 2011 *)

A137742(n)=if(n<2,1,n=A135473(n+3,n);n[ #n]) /* function A135473 defined in A137743 */

A137742(n)=if(n<2,1,(n - 1)*(n + 4)*(n + 6)/6)

From Bruno Berselli, Aug 23 2011: (Start)
G.f.: x*(1+4*x-5*x^2+x^4)/(1-x)^4.
a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4).
a(-n-7) = -A000297(n).  (End)
From Ilya Gutkovskiy, Jul 01 2016: (Start)
E.g.f.: 4 + x + (-24 + 24*x + 12*x^2 + x^3)*exp(x)/6.
Sum_{n>=1} 1/a(n) = 1542/1225. (End)
a(n) = binomial(n+4,3) - 2*(n+4) for n > 1. - Michael Chu, Dec 09 2021

A137739 Number of different strings of length n+6 obtained from "123...n" by iteratively duplicating any substring.

Original entry on oeis.org

1, 64, 355, 1014, 2218, 4217, 7343, 12018, 18767, 28233, 41193, 58575, 81476, 111181, 149183, 197204, 257217, 331469, 422505, 533193, 666750, 826769, 1017247, 1242614, 1507763, 1818081, 2179481, 2598435, 3082008, 3637893, 4274447, 5000728, 5826533, 6762437

Offset: 1

M. F. Hasler, Feb 10 2008

See A137743 for comments and examples.

Index entries for doubling substrings
Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

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

A137739(n)=if(n<2,1,n=A135473(n+6,n);n[ #n]) /* function A135473 defined in A137743 */

A137739(n)=if(n>4,n*(n*(n*(n*(n*(n+45)+775)+5775)+15064)-12300)/6!-112,[1,64,355,1014][n])

a(n) = 1/720*(n+9)*(n^5+36*n^4+451*n^3+1716*n^2-380*n-8880)-1 for n>4.

G.f.: x*(x^10+3*x^9-6*x^8-26*x^7+221*x^5-370*x^4+162*x^3+72*x^2-57*x-1) / (x-1)^7. - Colin Barker, Nov 04 2013

More terms from Colin Barker, Nov 04 2013

A137741 Number of different strings of length n+4 obtained from "123...n" by iteratively duplicating any substring.

Original entry on oeis.org

1, 16, 54, 119, 218, 360, 555, 814, 1149, 1573, 2100, 2745, 3524, 4454, 5553, 6840, 8335, 10059, 12034, 14283, 16830, 19700, 22919, 26514, 30513, 34945, 39840, 45229, 51144, 57618, 64685, 72380, 80739, 89799, 99598, 110175, 121570, 133824, 146979, 161078

Offset: 1

M. F. Hasler, Feb 10 2008

See A137743 for comments and examples.

Index entries for doubling substrings

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

A137741(n)=if(n<2,1,n=A135473(n+4,n);n[ #n]) /* function A135473 defined in A137743 */

a(n) = n^4 for n=1,2; a(n) = 1/24*(n+3)*(n^3+15*n^2+50*n-96) for n>2 (conjectured).

G.f.: x*(x^6+x^5-8*x^4+x^3+16*x^2-11*x-1) / (x-1)^5 (conjectured). - Colin Barker, Nov 04 2013

More terms from Colin Barker, Nov 04 2013

A137745 Number of different strings of length n obtained from "abcde" by iteratively duplicating any substring.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 5, 19, 66, 218, 700, 2218, 6997, 22064, 69662, 220395, 699090, 2224114, 7098773, 22733498, 73048903, 235504760, 761689193, 2471105355, 8040439771, 26235143469, 85831045851, 281519068056, 925596771195, 3050264328190, 10074150332305, 33341934697311, 110571437129989

Offset: 0

M. F. Hasler, Feb 10 2008

nonn

See A137743 for more comments.

			a(k) = 0 for k<5, since no shorter string can be obtained by duplicating a substring.
a(5) = # { abcde },
a(6) = # { aabcde, abbcde, abccde, abcdde, abcdee },
a(7) = # { aaabcde, aabbcde, aabccde, aabcdde, aabcdee, ababcde, abbbcde, abbccde, abbcdde, abbcdee, abcbcde, abcccde, abccdde, abccdee, abcdcde, abcddde, abcddee, abcdede, abcdeee }

Index entries for doubling substrings

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

A135473(13,5) /* function defined in A137743...*/

a(14)-a(19) from Lars Blomberg, Jan 12 2013
a(20)-a(21) from Michael S. Branicky, Jan 05 2021
a(22)-a(23) from Bert Dobbelaere, Jun 10 2024
a(24)-a(32) from Martin Fuller, Jun 07 2025

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

M. F. Hasler, Feb 10 2008

nonn

See A137743 for more comments.

			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 }.

Index entries for doubling substrings

Cf. A137740, A137741, A137742, A137743, A135473, A137744, A137745, A137746, A137747, A137748.

A135473(14,6) /* function defined in A137743 ... */

a(15)-a(16) from Alois P. Heinz, Aug 31 2011
a(17)-a(19) from Lars Blomberg, Jan 12 2013
a(20)-a(21) from Michael S. Branicky, Jan 06 2021
a(22)-a(23) from Bert Dobbelaere, Jun 11 2024
a(24)-a(32) from Martin Fuller, Jun 07 2025

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

Original entry on oeis.org

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

M. F. Hasler, Feb 10 2008

nonn

See A137743 for more comments.

			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.)

Index entries for doubling substrings

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

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

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

cp's OEIS Frontend

A135473 a(n) = number of strings of length n that can be obtained by starting with abc and repeatedly doubling any substring in place.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A137740 Number of different strings of length n+5 obtained from "123...n" by iteratively duplicating any substring.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A137744 Number of different strings of length n obtained from "abcd" by iteratively duplicating any substring.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Extensions

A137742 a(n) = (n-1)*(n+4)*(n+6)/6 for n > 1, a(1)=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

A137739 Number of different strings of length n+6 obtained from "123...n" by iteratively duplicating any substring.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A137741 Number of different strings of length n+4 obtained from "123...n" by iteratively duplicating any substring.

Views

Author

Keywords

Comments

A137742 a(n) = (n-1)(n+4)(n+6)/6 for n > 1, a(1)=1.