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,9

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.

Links

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

Formula

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

Example

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.

Prog

(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])) }

Crossrefs

Row sums are A351642.

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

Column k=3 is A351643.

Cf. A111596, A351637, A351640.

Sequence in context: A244372 A370773 A119331 * A291883 A361957 A239145

Adjacent sequences: A351638 A351639 A351640 * A351642 A351643 A351644

Keyword

nonn,tabl

Author

Andrew Howroyd, Feb 15 2022

Status

approved