A292805 Number of sets of nonempty words with a total of n letters over n-ary alphabet.

1, 1, 5, 55, 729, 12376, 250735, 5904746, 158210353, 4747112731, 157545928646, 5726207734545, 226093266070501, 9632339536696943, 440262935648935344, 21482974431740480311, 1114363790702406540897, 61219233429920494716931, 3550130647865299090804375

Offset

0,3

Links

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

Formula

a(n) = [x^n] Product_{j=1..n} (1+x^j)^(n^j).

a(n) ~ n^(n - 3/4) * exp(2*sqrt(n) - 1/2) / (2*sqrt(Pi)). - Vaclav Kotesovec, Aug 26 2019

Example

a(0) = 1: {}.
a(1) = 1: {a}.
a(2) = 5: {aa}, {ab}, {ba}, {bb}, {a,b}.

Maple

h:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(h(n-i*j, i-1, k)*binomial(k^i, j), j=0..n/i)))
    end:
a:= n-> h(n$3):
seq(a(n), n=0..20);

Mathematica

h[n_, i_, k_] := h[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[h[n - i*j, i - 1, k]*Binomial[k^i, j], {j, 0, n/i}]]];
a[n_] := h[n, n, n];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jun 04 2018, from Maple *)

Crossrefs

Main diagonal of A292804.

Cf. A252654, A292845.

Sequence in context: A038261 A246153 A358955 * A112019 A131846 A144577

Adjacent sequences: A292802 A292803 A292804 * A292806 A292807 A292808

Keyword

nonn

Author

Alois P. Heinz, Sep 23 2017

Status

approved