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

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+1).

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

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

Example

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

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

Crossrefs

Cf. A000085, A293808.

Sequence in context: A294010 A294011 A294012 * A307976 A114495 A137398

Adjacent sequences: A293806 A293807 A293808 * A293810 A293811 A293812

Keyword

nonn

Author

Alois P. Heinz, Oct 16 2017

Status

approved