A135473 -id:A135473 - cp's OEIS frontend

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

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

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

M. F. Hasler, Feb 10 2008

nonn

See A137743 for more comments.

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

Index entries for doubling substrings

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

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

a(15)-a(17) from Alois P. Heinz, Sep 01 2011
a(18)-a(20) from Lars Blomberg, Jan 12 2013
a(21)-a(22) from Bert Dobbelaere, Dec 30 2018
a(23)-a(32) from Martin Fuller, Jun 08 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

A135017 a(n) is number of strings of length n that can be obtained by starting with abc and repeatedly doubling any substring in place and then discarding any string that contains two successive equal letters.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 3, 5, 7, 15, 20, 48, 60, 156, 205, 489, 761, 1572, 2796, 5357, 10174, 19021, 37272, 69375, 137759, 258444, 513696, 976890, 1934900, 3727164, 7358675, 14316861, 28217028, 55288907, 108942267, 214462953, 422973649, 835145308, 1649638479, 3263689911, 6457465848, 12795025182, 25355766038, 50304700910

Offset: 1

David Applegate and N. J. A. Sloane, Feb 12 2008

nonn

These strings may be regarded as the "primitive" strings among those enumerated by A135473.

Equals the inverse binomial transform of A135473.

			n=3: abc
n=4: -
n=5: ababc, abcbc
n=6: abcabc
n=7: abababc, ababcbc, abcbcbc

Index entries for doubling substrings

Cf. A135473.

Empirically, grows like 2^n.

Extended to 37 terms by David Applegate, Feb 16 2008

a(38)-a(44) by Martin Fuller, Jun 06 2025

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

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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

A135017 a(n) is number of strings of length n that can be obtained by starting with abc and repeatedly doubling any substring in place and then discarding any string that contains two successive equal letters.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

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