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,3

Links

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

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

Example

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}.

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 *)

Crossrefs

Main diagonal of A292795.

Row sums of A319498.

Cf. A226873, A292713.

Sequence in context: A340415 A340416 A340417 * A020007 A112731 A106884

Adjacent sequences: A292793 A292794 A292795 * A292797 A292798 A292799

Keyword

nonn

Author

Alois P. Heinz, Sep 23 2017

Status

approved