New topic: duplication of substrings

[Maximilian Hasler]

I don't know if I'll have the time to look further into these sequences,
so here is a summary of my results and some conjectures, concerning :

T(m,n) = number of different strings of length n obtained from
"123...m" by iteratively duplicating any substring (A137743)

T(m,n)=0 for m>n ,  T(n,n)=T(1,n) = 1 ,  T(2,n)=2^(n-2),

T(3,n) = A135473, T(4..8,n) = A137744..8   (no formulas known for any
of these or beyond)

T(n,n+1) = n ,  T(n,n+2) = (n+1)(n+2)/2 - 2 ,

T(n,n+3) = A137742 = 1/6*(n-1)*(n+6)*(n+4)  for n>1, for n=1 this
gives 0 instead of 1.

T(n,n+4) = A137741 = 1/24*(n+3)*(n^3+15*n^2+50*n-96)  for n>2,
 for n=2 this formula gives 15 instead of 16

T(n,n+5) = A137740 = 1/5!*(n+4)*(n^2+3*n-8)*(n^2+23*n+150)+4  for n>3,
 for n=3 this formula gives 137 instead of 138

T(n,n+6) = A137739 =
1/6!*(n+9)*(n^5+36*n^4+451*n^3+1716*n^2-380*n-8880)-1  for n>4,
 for n=4 this formula gives 1013 instead of 1014

One can observe that taking successive differences,
sooner or later one gets back a preceding sequence (from a certain term on).
E.g., taking 4-th differences of T(n,n+6), one gets back T(n,n+1)
(from the term a(n)=103 on);
here, the last term which does not concide is one too much (90 in the
seq of differences, 89 in seq. T(n,n+1)).

More precisely (from the above mentioned rank on):
T(n,n+2) = sum( T(k,k+1), k=0..n+1) - 2
T(n,n+3) = sum( T(k,k+2), k=1..n+1) - 5
T(n,n+4) = sum( T(k,k+3), k=2..n+1) - 12 - n
T(n,n+5) = sum( T(k,k+4), k=3..n+1) - 21 - 7n/2 - n^2/2
T(n,n+6) = sum( T(k,k+5), k=4..n+1) + 49 - 25n/3 - 5n^2/2 - n^3/6

So far the difference is always a polynomial of degree less than deg(
l.h.s) - 2.
I conjecture that this will always hold true (according to the way the
strings are produced).
This would imply that  T(n,n+k) = (1/k!) (n^k + lower powers),
and also that the next-to-leading term in the parentheses will always
be + 3k(k+1)/2 * n^(k-1).

I was about submitting the coefficients of these polynomials (x k! of
course) as an upper right triangular array of numbers, when I noticed
that this property should be proved first in order to make sure the
sequence is well defined.

Maximilian