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
Examples
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) ...
Programs
-
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<
A137743(10,d)))
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
Extensions
More terms from Alois P. Heinz, Aug 31 2011
Comments