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

Author

Alois P. Heinz, Sep 30 2017

Keywords

• nonn

Examples

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

Links

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

Crossrefs

Main diagonal of A293108.

Row sums of A293109 and of A293808.

Cf. A000085, A182172, A293114.

Programs

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

Formula

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