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.

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,5

Comments

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

Links

Table of n, a(n) for n=1..66.

Index entries for doubling substrings

Formula

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

Example

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

Prog

(PARI) 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<<ee - 1); /* substring + tail */ forstep( ii=i+len/w, Nmax, len/w, setsearch( L[ii], tt = bitand( tt<<len, -1<<ee)+lsb) & next; L[ii] = setunion( L[ii], tt )); ) ) ) ) ); vector(Nmax, i, #L[i])}
for(d=2, 7, print(A137743(10, d)))

Crossrefs

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

Sequence in context: A218664 A247286 A055587 * A099239 A167630 A322264

Adjacent sequences: A137740 A137741 A137742 * A137744 A137745 A137746

Keyword

nonn,tabl

Author

M. F. Hasler, Feb 10 2008

Extensions

More terms from Alois P. Heinz, Aug 31 2011

Status

approved