A189845 Number of length-n restricted growth strings (RGS) [s(0),s(1),...,s(n-1)] where s(0)=0 and s(k)<=3+max(prefix) for k>=1.

1, 1, 4, 22, 150, 1200, 10922, 110844, 1236326, 14990380, 195895202, 2740062260, 40789039078, 643118787708, 10696195808162, 186993601880756, 3425688601198118, 65586903427253532, 1309155642001921026, 27185548811026532692, 586164185027289760806

Offset: 0

Author

Joerg Arndt, Apr 29 2011

Keywords

• nonn

Examples

			For n=0 there is one empty string; for n=1 there is one string [0]; for n=2 there are 4 strings [00], [01], [02], and [03];
for n=3 there are a(3)=22 strings:
01:  [ 0 0 0 ],
02:  [ 0 0 1 ],
03:  [ 0 0 2 ],
04:  [ 0 0 3 ],
05:  [ 0 1 0 ],
06:  [ 0 1 1 ],
07:  [ 0 1 2 ],
08:  [ 0 1 3 ],
09:  [ 0 1 4 ],
10:  [ 0 2 0 ],
11:  [ 0 2 1 ],
12:  [ 0 2 2 ],
13:  [ 0 2 3 ],
14:  [ 0 2 4 ],
15:  [ 0 2 5 ],
16:  [ 0 3 0 ],
17:  [ 0 3 1 ],
18:  [ 0 3 2 ],
19:  [ 0 3 3 ],
20:  [ 0 3 4 ],
21:  [ 0 3 5 ],
22:  [ 0 3 6 ].
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..481 (first 67 terms from Vincenzo Librandi)
• Joerg Arndt, Matters Computational (The Fxtbook), section 17.3.4, pp. 364-366

Crossrefs

Cf. A080337, A000110, A306027.

Column k=3 of A305962.

Programs

Maple

b:= proc(n, m) option remember; `if`(n=0, 1,
      add(b(n-1, max(m, j)), j=1..m+3))
    end:
a:= n-> b(n, -2):
seq(a(n), n=0..25);  # Alois P. Heinz, Jun 15 2018

Mathematica

b[n_, m_] := b[n, m] = If[n==0, 1, Sum[b[n-1, Max[m, j]], {j, 1, m+3}]];
a[n_] := b[n, -2];
a /@ Range[0, 25] (* Jean-François Alcover, Nov 03 2020, after Alois P. Heinz *)

PARI

x='x+O('x^66);
egf=exp(x+sum(j=1,3, (exp(j*x)-1)/j)); /* (off by one!) */
concat([1], Vec(serlaplace(egf)))

Formula

E.g.f. of sequence starting 1,4,22,.. is exp(x+exp(x)+exp(2*x)/2+exp(3*x)/3-11/6) = exp(x+sum(j=1,3, (exp(j*x)-1)/j)) = 1+4*x+11*x^2+25*x^3+50*x^4+5461/60*x^5 +...