|
| |
|
|
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.
|
|
12
| |
|
|
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
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,5
|
|
|
COMMENTS
| The sequence T(m,m+3) = 1,8,21,40,66,100,143,196,260,... = A137742.
|
|
|
LINKS
| 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.
|
|
|
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: A091186 A138155 A055587 * A099239 A167630 A009998
Adjacent sequences: A137740 A137741 A137742 * A137744 A137745 A137746
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| M. F. Hasler (www.univ-ag.fr/~mhasler), Feb 10 2008
|
|
|
EXTENSIONS
| More terms from Alois P. Heinz (heinz(AT)hs-heilbronn.de), Aug 31 2011
|
| |
|
|
