A351641 Triangle read by rows: T(n,k) is the number of length n word structures with all distinct runs using exactly k different symbols.

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 5, 3, 1, 0, 1, 8, 12, 4, 1, 0, 1, 17, 28, 22, 5, 1, 0, 1, 26, 81, 68, 35, 6, 1, 0, 1, 45, 177, 251, 135, 51, 7, 1, 0, 1, 76, 410, 704, 610, 236, 70, 8, 1, 0, 1, 121, 906, 2068, 2086, 1266, 378, 92, 9, 1

Offset: 0

Author

Andrew Howroyd, Feb 15 2022

Keywords

• nonn
• tabl

Comments

Permuting the symbols will not change the structure.

Equivalently, T(n,k) is the number of restricted growth strings [s(0), s(1), ..., s(n-1)] where s(0)=0 and s(i) <= 1 + max(prefix) for i >= 1, the maximum value is k and all runs are distinct.

Examples

			Triangle begins:
  1;
  0, 1;
  0, 1,  1;
  0, 1,  2,   1;
  0, 1,  5,   3,   1;
  0, 1,  8,  12,   4,   1;
  0, 1, 17,  28,  22,   5,  1;
  0, 1, 26,  81,  68,  35,  6, 1;
  0, 1, 45, 177, 251, 135, 51, 7, 1;
  ...
The T(4,1) = 1 word is 1111.
The T(4,2) = 5 words are 1112, 1121, 1122, 1211, 1222.
The T(4,3) = 3 words are 1123, 1223, 1233.
The T(4,4) = 1 word is 1234.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Crossrefs

Row sums are A351642.

Partial row sums include A000007, A000012, A351018, A351644.

Column k=3 is A351643.

Cf. A111596, A351637, A351640.

Programs

PARI

\\ here LahI is A111596 as row polynomials.
LahI(n, y)={sum(k=1, n, y^k*(-1)^(n-k)*(n!/k!)*binomial(n-1, k-1))}
S(n)={my(p=prod(k=1, n, 1 + y*x^k + O(x*x^n))); 1 + sum(i=1, (sqrtint(8*n+1)-1)\2, polcoef(p, i, y)*LahI(i, y))}
R(q)={[subst(serlaplace(p), y, 1) | p<-Vec(q)]}
T(n)={my(q=S(n), v=concat([1], sum(k=1, n, R(q^k-1)*sum(r=k, n, y^r*binomial(r, k)*(-1)^(r-k)/r!) ))); [Vecrev(p) | p<-v]}
{ my(A=T(10)); for(n=1, #A, print(A[n])) }

Formula

T(n,k) = A351640(n,k)/k!.