A306025 Number of length-n restricted growth strings (RGS) with growth <= n and first element in [n].

1, 1, 7, 95, 2096, 67354, 2943277, 166862583, 11858631472, 1029154793775, 106837050484924, 13046411412001307, 1848336205780389404, 300289842081446066173, 55393980428260038660617, 11503469972529028999979343, 2669299049110696359069533376

Offset

0,3

Links

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

Formula

a(n) = n! * [x^n] exp(Sum_{j=1..n} (exp(j*x)-1)/j).

a(n) = A306024(n,n).

Example

a(0) = 1: the empty string.
a(1) = 1: 1.
a(2) = 7: 11, 12, 13, 21, 22, 23, 24.

Maple

b:= proc(n, k, m) option remember; `if`(n=0, 1,
      add(b(n-1, k, max(m, j)), j=1..m+k))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..20);
# second Maple program:
a:= n-> n!*coeff(series(exp(add((exp(j*x)-1)/j, j=1..n)), x, n+1), x, n):
seq(a(n), n=0..20);

Mathematica

b[n_, k_, m_] := b[n, k, m] = If[n == 0, 1,
   Sum[b[n - 1, k, Max[m, j]], {j, 1, m + k}]];
a[n_] := b[n, n, 0];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Sep 07 2022, after Alois P. Heinz *)

Crossrefs

Main diagonal of A306024.

Cf. A305963.

Sequence in context: A244856 A367159 A201990 * A130183 A156961 A239999

Adjacent sequences: A306022 A306023 A306024 * A306026 A306027 A306028

Keyword

nonn

Author

Alois P. Heinz, Jun 17 2018

Status

approved