A292796 Number of sets of nonempty words with a total of n letters over n-ary alphabet such that within each word every letter of the alphabet is at least as frequent as the subsequent alphabet letter.

1, 1, 3, 13, 60, 326, 2065, 14508, 116845, 1039459, 10339365, 112376487, 1339665295, 17256611005, 240193792120, 3578746993871, 56986570945387, 963868021665359, 17281651020455445, 327058650473873893, 6519981694119182165, 136489249161324882063

Offset: 0

Author

Alois P. Heinz, Sep 23 2017

Keywords

• nonn

Examples

			a(0) = 1: {}.
a(1) = 1: {a}.
a(2) = 3: {aa}, {ab}, {ba}.
a(3) = 13: {aaa}, {aab}, {aba}, {baa}, {abc}, {acb}, {bac}, {bca}, {cab}, {cba}, {aa,a}, {ab,a}, {ba,a}.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..450

Crossrefs

Main diagonal of A292795.

Row sums of A319498.

Cf. A226873, A292713.

Programs

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:
a:= n-> h(n$3):
seq(a(n), n=0..30);

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}]]];
a[n_] := h[n, n, n];
a /@ Range[0, 30] (* Jean-François Alcover, Jan 02 2021, after Alois P. Heinz *)

Formula

a(n) = [x^n] Product_{j=1..n} (1+x^j)^A226873(j,n).

a(n) = A292795(n,n).

a(n) ~ c * n!, where c = A247551 = 2.529477472079152648... - Vaclav Kotesovec, Sep 28 2017