A319498 Number T(n,k) of sets of nonempty words with a total of n letters over k-ary alphabet such that for k>0 the k-th letter occurs at least once and within each word every letter of the alphabet is at least as frequent as the subsequent alphabet letter; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 2, 0, 2, 5, 6, 0, 2, 16, 18, 24, 0, 3, 39, 80, 84, 120, 0, 4, 106, 323, 432, 480, 720, 0, 5, 245, 1106, 2052, 2820, 3240, 5040, 0, 6, 621, 3822, 10576, 14820, 21480, 25200, 40320, 0, 8, 1431, 13840, 41896, 86724, 124440, 186480, 221760, 362880

Offset

0,6

Comments

T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k <= n. T(n,k) = 0 for k > n.

Links

Alois P. Heinz, Rows n = 0..140, flattened

Formula

T(n,k) = A292795(n,k) - A292795(n,k-1) for k > 0, T(n,0) = A000007(n).

Example

T(3,1) = 2: {aaa}, {aa,a}.
T(3,2) = 5: {aab}, {aba}, {baa}, {ab,a}, {ba,a}.
T(3,3) = 6: {abc}, {acb}, {bac}, {bca}, {cab}, {cba}.
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,    2;
  0, 2,    5,     6;
  0, 2,   16,    18,    24;
  0, 3,   39,    80,    84,   120;
  0, 4,  106,   323,   432,   480,    720;
  0, 5,  245,  1106,  2052,  2820,   3240,   5040;
  0, 6,  621,  3822, 10576, 14820,  21480,  25200,  40320;
  ...

Maple

b:= proc(n, i, t) option remember; `if`(t=1, 1/n!,
      add(b(n-j, j, t-1)/j!, j=i..n/t))
    end:
g:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0), n!*b(n, 0, k)):
h:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(h(n-i*j, i-1, k)*binomial(g(i, k), j), j=0..n/i)))
    end:
T:= (n, k)-> h(n$2, k) -`if`(k=0, 0, h(n$2, k-1)):
seq(seq(T(n, k), k=0..n), n=0..12);

Mathematica

b[n_, i_, t_] := b[n, i, t] = If[t == 1, 1/n!,
     Sum[b[n - j, j, t - 1]/j!, {j, i, n/t}]];
g[n_, k_] := If[k == 0, If[n == 0, 1, 0], n!*b[n, 0, k]];
h[n_, i_, k_] := h[n, i, k] = If[n == 0, 1, If[i < 1, 0,
     Sum[h[n - i*j, i - 1, k]*Binomial[g[i, k], j], {j, 0, n/i}]]];
T[n_, k_] := h[n, n, k] - If[k == 0, 0, h[n, n, k - 1]];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Feb 09 2021, after Alois P. Heinz *)

Crossrefs

Columns k=0-1 give: A000007, A000009 (for n>0).

Row sums give A292796.

Main diagonal gives A000142.

First lower diagonal gives A038720 (for n>1).

Cf. A292795, A319495.

Sequence in context: A094721 A301951 A144529 * A349782 A011297 A110282

Adjacent sequences: A319495 A319496 A319497 * A319499 A319500 A319501

Keyword

nonn,tabl

Author

Alois P. Heinz, Sep 20 2018

Status

approved