A293110 Number of multisets of 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.

1, 1, 3, 7, 20, 54, 164, 500, 1630, 5472, 19257, 70133, 265858, 1042346, 4235031, 17760943, 76913277, 342919431, 1573637985, 7415371293, 35860511131, 177641956111, 900782461170, 4668600610346, 24714284921937, 133467868645017, 734844788634269, 4120752558254581

Offset

0,3

Links

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

Formula

G.f.: Product_{j>=1} 1/(1-x^j)^A000085(j).

Example

a(0) = 1: {}.
a(1) = 1: {a}
a(2) = 3: {a,a}, {aa}, {ab}.
a(3) = 7: {a,a,a}, {a,aa}, {a,ab}, {aaa}, {aab}, {aba}, {abc}.

Maple

g:= proc(n) option remember;
      `if`(n<2, 1, g(n-1)+(n-1)*g(n-2))
    end:
a:= proc(n) option remember; `if`(n=0, 1, add(add(g(d)
      *d, d=numtheory[divisors](j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..40);

Mathematica

g[n_] := g[n] = If[n < 2, 1, g[n - 1] + (n - 1)*g[n - 2]];
a[n_] := a[n] = If[n == 0, 1, Sum[Sum[g[d]*d, {d, Divisors[j]}]*a[n - j], {j, 1, n}]/n];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Jun 07 2018, from Maple *)

Crossrefs

Main diagonal of A293108.

Row sums of A293109 and of A293808.

Cf. A000085, A182172, A293114.

Sequence in context: A293738 A293739 A293740 * A322204 A000227 A327993

Adjacent sequences: A293107 A293108 A293109 * A293111 A293112 A293113

Keyword

nonn

Author

Alois P. Heinz, Sep 30 2017

Status

approved