A189845 - OEIS

%I #35 Nov 04 2020 05:57:01

%S 1,1,4,22,150,1200,10922,110844,1236326,14990380,195895202,2740062260,

%T 40789039078,643118787708,10696195808162,186993601880756,

%U 3425688601198118,65586903427253532,1309155642001921026,27185548811026532692,586164185027289760806

%N 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.

%H Alois P. Heinz, <a href="/A189845/b189845.txt">Table of n, a(n) for n = 0..481</a> (first 67 terms from Vincenzo Librandi)

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 17.3.4, pp. 364-366

%F 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 +...

%e 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];

%e for n=3 there are a(3)=22 strings:

%e 01:  [ 0 0 0 ],

%e 02:  [ 0 0 1 ],

%e 03:  [ 0 0 2 ],

%e 04:  [ 0 0 3 ],

%e 05:  [ 0 1 0 ],

%e 06:  [ 0 1 1 ],

%e 07:  [ 0 1 2 ],

%e 08:  [ 0 1 3 ],

%e 09:  [ 0 1 4 ],

%e 10:  [ 0 2 0 ],

%e 11:  [ 0 2 1 ],

%e 12:  [ 0 2 2 ],

%e 13:  [ 0 2 3 ],

%e 14:  [ 0 2 4 ],

%e 15:  [ 0 2 5 ],

%e 16:  [ 0 3 0 ],

%e 17:  [ 0 3 1 ],

%e 18:  [ 0 3 2 ],

%e 19:  [ 0 3 3 ],

%e 20:  [ 0 3 4 ],

%e 21:  [ 0 3 5 ],

%e 22:  [ 0 3 6 ].

%p b:= proc(n, m) option remember; `if`(n=0, 1,

%p       add(b(n-1, max(m, j)), j=1..m+3))

%p     end:

%p a:= n-> b(n, -2):

%p seq(a(n), n=0..25);  # _Alois P. Heinz_, Jun 15 2018

%t b[n_, m_] := b[n, m] = If[n==0, 1, Sum[b[n-1, Max[m, j]], {j, 1, m+3}]];

%t a[n_] := b[n, -2];

%t a /@ Range[0, 25] (* _Jean-François Alcover_, Nov 03 2020, after _Alois P. Heinz_ *)

%o (PARI) x='x+O('x^66);

%o egf=exp(x+sum(j=1,3, (exp(j*x)-1)/j)); /* (off by one!) */

%o concat([1], Vec(serlaplace(egf)))

%Y Cf. A080337, A000110, A306027.

%Y Column k=3 of A305962.

%K nonn

%O 0,3

%A _Joerg Arndt_, Apr 29 2011