A319495 Number T(n,k) of multisets 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, 2, 2, 0, 3, 5, 6, 0, 5, 20, 18, 24, 0, 7, 46, 86, 84, 120, 0, 11, 137, 347, 456, 480, 720, 0, 15, 313, 1216, 2136, 2940, 3240, 5040, 0, 22, 836, 4253, 11128, 15300, 22200, 25200, 40320, 0, 30, 1908, 15410, 44308, 90024, 127680, 191520, 221760, 362880

Offset

0,5

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) = A292712(n,k) - A292712(n,k-1) for k > 0, T(n,0) = A000007(n).

Example

T(3,1) = 3: {aaa}, {aa,a}, {a,a,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,  2,   2;
  0,  3,   5,    6;
  0,  5,  20,   18,    24;
  0,  7,  46,   86,    84,   120;
  0, 11, 137,  347,   456,   480,   720;
  0, 15, 313, 1216,  2136,  2940,  3240,  5040;
  0, 22, 836, 4253, 11128, 15300, 22200, 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)):
A:= proc(n, k) option remember; `if`(n=0, 1, add(add(d*
      g(d, k), d=numtheory[divisors](j))*A(n-j, k), j=1..n)/n)
    end:
T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, 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]];
A[n_, k_] := A[n, k] = If[n == 0, 1, Sum[Sum[d*
     g[d, k], {d, Divisors[j]}]*A[n - j, k], {j, 1, n}]/n];
T[n_, k_] := A[n, k] - If[k == 0, 0, A[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, A000041 (for n>0).

Row sums give A292713.

Main diagonal gives A000142.

First lower diagonal gives A038720.

Cf. A292712, A319498.

Sequence in context: A201947 A098816 A214639 * A216973 A061314 A366730

Adjacent sequences: A319492 A319493 A319494 * A319496 A319497 A319498

Keyword

nonn,tabl

Author

Alois P. Heinz, Sep 20 2018

Status

approved