A293113 Number T(n,k) of sets of nonempty words with a total of n letters over k-ary alphabet containing the k-th letter such that within each prefix of a 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, 1, 0, 2, 3, 1, 0, 2, 8, 4, 1, 0, 3, 20, 16, 5, 1, 0, 4, 47, 53, 25, 6, 1, 0, 5, 106, 173, 102, 36, 7, 1, 0, 6, 237, 532, 410, 172, 49, 8, 1, 0, 8, 522, 1615, 1545, 813, 268, 64, 9, 1, 0, 10, 1146, 4785, 5784, 3576, 1448, 394, 81, 10, 1

Offset

0,8

Links

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

Formula

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

Example

Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,   1;
  0, 2,   3,   1;
  0, 2,   8,   4,   1;
  0, 3,  20,  16,   5,   1;
  0, 4,  47,  53,  25,   6,  1;
  0, 5, 106, 173, 102,  36,  7, 1;
  0, 6, 237, 532, 410, 172, 49, 8, 1;

Maple

h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(l[k]
    <j, 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
g:= proc(n, i, l) option remember;
      `if`(n=0, h(l), `if`(i<1, 0, `if`(i=1, h([l[], 1$n]),
        g(n, i-1, l) +`if`(i>n, 0, g(n-i, i, [l[], i])))))
    end:
b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(b(n-i*j, i-1, k)*binomial(g(i, k, []), j), j=0..n/i)))
    end:
T:= (n, k)-> b(n$2, k)-`if`(k=0, 0, b(n$2, k-1)):
seq(seq(T(n, k), k=0..n), n=0..14);

Mathematica

h[l_] := Function[n, Total[l]!/Product[Product[1 + l[[i]] - j + Sum[If[ l[[k]]<j, 0, 1], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]][ Length[l]];
g[n_, i_, l_] := g[n, i, l] = If[n == 0, h[l], If[i < 1, 0, If[i == 1, h[Join[l, Table[1, n]]], g[n, i - 1, l] + If[i > n, 0, g[n - i, i, Append[l, i]]]]]];
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i<1, 0, Sum[b[n - i*j, i-1, k]*Binomial[g[i, k, {}], j], {j, 0, n/i}]]];
T[n_, k_] := b[n, n, k] - If[k == 0, 0, b[n, n, k - 1]];
Table[T[n, k], {n, 0, 14}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 04 2018, after Alois P. Heinz *)

Crossrefs

Columns k=0-10 give: A000007, A000009 (for n>0), A293883, A293884, A293885, A293886, A293887, A293888, A293889, A293890, A293891.

Row sums give A293114.

T(2n,n) gives A293115.

Cf. A182172, A293109, A293112.

Sequence in context: A372257 A253580 A020921 * A366528 A154720 A355487

Adjacent sequences: A293110 A293111 A293112 * A293114 A293115 A293116

Keyword

nonn,tabl

Author

Alois P. Heinz, Sep 30 2017

Status

approved