A293815 Number T(n,k) of sets of exactly k nonempty words with a total of n letters over n-ary alphabet 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, read by rows.

1, 0, 1, 0, 2, 0, 4, 2, 0, 10, 5, 0, 26, 18, 1, 0, 76, 52, 8, 0, 232, 168, 30, 0, 764, 533, 114, 4, 0, 2620, 1792, 411, 22, 0, 9496, 6161, 1462, 116, 0, 35696, 22088, 5237, 482, 6, 0, 140152, 81690, 18998, 1966, 48, 0, 568504, 313224, 70220, 7682, 274

Offset

0,5

Comments

The smallest nonzero term in column k is A291057(k).

Links

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

Formula

G.f.: Product_{j>=1} (1+y*x^j)^A000085(j).

Example

T(0,0) = 1: {}.
T(3,1) = 4: {aaa}, {aab}, {aba}, {abc}.
T(3,2) = 2: {a,aa}, {a,ab}.
T(4,2) = 5: {a,aaa}, {a,aab}, {a,aba}, {a,abc}, {aa,ab}.
T(5,3) = 1: {a,aa,ab}.
Triangle T(n,k) begins:
  1;
  0,      1;
  0,      2;
  0,      4,     2;
  0,     10,     5;
  0,     26,    18,     1;
  0,     76,    52,     8;
  0,    232,   168,    30;
  0,    764,   533,   114,    4;
  0,   2620,  1792,   411,   22;
  0,   9496,  6161,  1462,  116;
  0,  35696, 22088,  5237,  482,  6;
  0, 140152, 81690, 18998, 1966, 48;
  ...

Maple

g:= proc(n) option remember; `if`(n<2, 1, g(n-1)+(n-1)*g(n-2)) end:
b:= proc(n, i) option remember; expand(`if`(n=0, 1, `if`(i<1, 0,
      add(b(n-i*j, i-1)*binomial(g(i), j)*x^j, j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n$2)):
seq(T(n), n=0..15);

Mathematica

g[n_] := g[n] = If[n < 2, 1, g[n - 1] + (n - 1)*g[n - 2]];
b[n_, i_] := b[n, i] = Expand[If[n == 0, 1, If[i<1, 0, Sum[b[n - i*j, i-1]* Binomial[g[i], j]*x^j, {j, 0, n/i}]]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, n]];
Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, Jun 04 2018, from Maple *)

Crossrefs

Columns k=0-10 give: A000007, A000085 (for n>0), A293964, A293965, A293966, A293967, A293968, A293969, A293970, A293971, A293972.

Row sums give A293114.

Cf. A208741, A293808, A291057, A294129.

Sequence in context: A356918 A081880 A144289 * A339941 A211318 A324239

Adjacent sequences: A293812 A293813 A293814 * A293816 A293817 A293818

Keyword

nonn,tabf

Author

Alois P. Heinz, Oct 16 2017

Status

approved