A293809 Number of multisets of exactly n nonempty words with a total of 2n letters over 2n-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, 2, 7, 22, 73, 240, 818, 2824, 10004, 36252, 134594, 512632, 2002797, 8037634, 33122211, 140287074, 610344666, 2728599114, 12524559427, 59014996342, 285169596358, 1412357461074, 7161541766341, 37150562120334, 196945057245451, 1066104659977212

Offset: 0

Author

Alois P. Heinz, Oct 16 2017

Keywords

• nonn

Examples

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

Links

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

Crossrefs

Cf. A000085, A293808.

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(d*
      g(d+1), d=numtheory[divisors](j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..30);

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[d*g[d+1], {d, Divisors[j]}]*a[n-j], {j, 1, n}]/n];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 23 2023, after Alois P. Heinz *)

Formula

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

Euler transform of j-> A000085(j+1).

a(n) = A293808(2n,n).