%I #27 Nov 10 2018 02:49:47
%S 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,
%T 138,119,66,26,7,1,1,128,355,348,218,100,34,8,1,1,256,924,1014,700,
%U 360,143,43,9,1,1,512,2432,2966,2218,1246,555,196,53,10,1
%N Number T(m,n) of different strings of length n obtained from "123...m" by iteratively duplicating any substring; formatted as upper right triangle.
%C The sequence T(m,m+3) = 1,8,21,40,66,100,143,196,260,... = A137742.
%H <a href="/index/Do#repeat">Index entries for doubling substrings</a>
%F 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.
%F 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
%e The full matrix is:
%e [ 1, 1, 1, 1, 1, 1, 1,_ 1,_ 1,__ 1,__ 1,...] (= A000012)
%e [[], 1, 2, 4, 8,16,32, 64,128, 256, 512,...] (= A000079)
%e [[],[], 1, 3, 8,21,54,138,355, 924,2432,...] (= A135473)
%e [[],[],[], 1, 4,13,40,119,348,1014,2966,...] (= A137744)
%e [[],[],[],[], 1, 5,19, 66,218, 700,2218,...] (= A137745)
%e [[],[],[],[],[], 1, 6, 26,100, 360,1246,...] (= A137746)
%e [[],[],[],[],[],[], 1,_ 7, 34, 143, 555,...] (= A137747)
%e ...
%o (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])}
%o for(d=2,7,print(A137743(10,d)))
%Y Cf. A135473, A137740-A137742, A137744-A137748.
%K nonn,tabl
%O 1,5
%A _M. F. Hasler_, Feb 10 2008
%E More terms from _Alois P. Heinz_, Aug 31 2011