A293114 Number of sets 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, 2, 6, 15, 45, 136, 430, 1415, 4845, 17235, 63509, 242854, 959904, 3926209, 16564083, 72097127, 322898943, 1487602607, 7034420691, 34122991199, 169499127425, 861596397518, 4475340840980, 23738200183570, 128427236055296, 708248486616539, 3977551340260517
Offset: 0
Keywords
Examples
a(0) = 1: {}.
a(1) = 1: {a}.
a(2) = 2: {aa}, {ab}.
a(3) = 6: {a,aa}, {a,ab}, {aaa}, {aab}, {aba}, {abc}.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..800
Crossrefs
Programs
-
Maple
g:= proc(n) option remember; `if`(n<2, 1, g(n-1)+(n-1)*g(n-2)) end: b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, add(b(n-i*j, i-1)*binomial(g(i), j), j=0..n/i))) end: a:= n-> b(n$2): seq(a(n), n=0..35); -
Mathematica
g[n_] := g[n] = If[n < 2, 1, g[n - 1] + (n - 1)*g[n - 2]]; b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[b[n - i*j, i - 1]* Binomial[g[i], j], {j, 0, n/i}]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jun 06 2018, from Maple *)