A305963 Number of length-n restricted growth strings (RGS) with growth <= n and fixed first element.

1, 1, 3, 22, 305, 6756, 216552, 9416240, 530764089, 37498693555, 3235722405487, 334075729235172, 40587204883652869, 5722676826879812177, 925590727478445526747, 170032646641380554970304, 35173161711207720944899921, 8132124409499796317194563900

Offset

0,3

Links

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

Formula

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

a(n) = A305962(n,n).

Example

a(2) = 3: 11, 12, 13.
a(3) = 22: 111, 112, 113, 114, 121, 122, 123, 124, 125, 131, 132, 133, 134, 135, 136, 141, 142, 143, 144, 145, 146, 147.

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, 1-n):
seq(a(n), n=0..20);
# second Maple program:
a:= n-> `if`(n=0, 1, (n-1)!*coeff(series(exp(x+add(
           (exp(j*x)-1)/j, j=1..n)), x, n), x, n-1)):
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, 1 - n];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 21 2022, after Alois P. Heinz *)

Crossrefs

Main diagonal of A305962.

Cf. A306025.

Sequence in context: A119390 A271848 A144681 * A366204 A261280 A124567

Adjacent sequences: A305960 A305961 A305962 * A305964 A305965 A305966

Keyword

nonn

Author

Alois P. Heinz, Jun 15 2018

Status

approved