OFFSET
0,3
COMMENTS
Length-n restricted growth strings (RGS) [s(0),s(1),...,s(n-1)] where s(k)<=F(k)+4 where F(0)=0 and F(k+1)=s(k+1) if s(k+1)-s(k)=4, otherwise F(k+1)=F(k); see example and Fxtbook link. - Joerg Arndt, Apr 30 2011
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..66
Joerg Arndt, Matters Computational (The Fxtbook), section 17.3.5, pp. 366-368
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version]
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
Adalbert Kerber, A matrix of combinatorial numbers related to the symmetric groups, Discrete Math., 21 (1978), 319-321.
A. Kerber, A matrix of combinatorial numbers related to the symmetric groups<, Discrete Math., 21 (1978), 319-321. [Annotated scanned copy]
N. J. A. Sloane, Transforms
FORMULA
a(n) = Sum_{m=0..n} 4^(n-m)*Stirling2(n, m).
E.g.f.: exp((exp(4*x)-1)/4).
O.g.f. A(x) satisfies A'(x)/A(x) = e^(4x).
E.g.f.: exp(Integral_{t = 0..x} exp(4*t)). - Joerg Arndt, Apr 30 2011
O.g.f.: Sum_{k>=0} x^k/Product_{j=1..k} (1-4*j*x). - Joerg Arndt, Apr 30 2011
Define f_1(x), f_2(x), ... such that f_1(x) = e^x, f_{n+1}(x) = (d/dx)(x*f_n(x)), for n = 2, 3, .... Then a(n) = e^(-1/4)*4^{n-1}*f_n(1/4). - Milan Janjic, May 30 2008
a(n) = upper left term in M^n, M = an infinite square production matrix in which a diagonal of (4,4,4,...) is appended to the right of Pascal's triangle:
1, 4, 0, 0, 0, ...
1, 1, 4, 0, 0, ...
1, 2, 1, 4, 0, ...
1, 3, 3, 1, 4, ...
... - Gary W. Adamson, Jul 29 2011
G.f. satisfies A(x) = 1 + x/(1 - 4*x)*A(x/(1 - 4*x)). a(n) = Sum_{k = 1..n} 4^(n-k)*binomial(n-1,k-1)*a(k-1), n > 0, a(0) = 1. - Vladimir Kruchinin, Nov 28 2011 [corrected by Ilya Gutkovskiy, May 02 2019]
G.f.: (G(0) - 1)/(x-1) where G(k) = 1 - 1/(1-4*k*x)/(1-x/(x-1/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Jan 24 2013
G.f.: (G(0) - 1)/(1+x) where G(k) = 1 + 1/(1-4*k*x)/(1-x/(x+1/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Jan 31 2013
G.f.: T(0)/(1-x), where T(k) = 1 - 4*x^2*(k+1)/( 4*x^2*(k+1) - (1-x-4*x*k)*(1-5*x-4*x*k)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 19 2013
a(n) = exp(-1/4) * Sum_{k>=0} 4^(n-k) * k^n / k!. - Vaclav Kotesovec, Jul 15 2021
a(n) ~ 4^n * n^n * exp(n/LambertW(4*n) - 1/4 - n) / (sqrt(1 + LambertW(4*n)) * LambertW(4*n)^n). - Vaclav Kotesovec, Jul 15 2021
From Peter Bala, Jun 29 2024: (Start)
a(n) = exp(-1/4)*Sum_{n >= 0} (4*n)^k/(n!*4^n).
Touchard's congruence holds: for odd prime p, a(p+k) == (a(k) + a(k+1)) (mod p) for k = 0,1,2,.... In particular, a(p) == 2 (mod p) for odd prime p. See A004211. (End)
EXAMPLE
Restricted growth strings: a(0)=1 corresponds to the empty string, a(1)=1 to [0],
a(2)=3 to [00], [01], [02], [03], and [04], a(3) = 29 to
RGS F
.1: [ 0 0 0 ] [ 0 0 0 ]
.2: [ 0 0 1 ] [ 0 0 0 ]
.3: [ 0 0 2 ] [ 0 0 0 ]
.4: [ 0 0 3 ] [ 0 0 0 ]
.5: [ 0 0 4 ] [ 0 0 4 ]
.6: [ 0 1 0 ] [ 0 0 0 ]
.7: [ 0 1 1 ] [ 0 0 0 ]
.8: [ 0 1 2 ] [ 0 0 0 ]
.9: [ 0 1 3 ] [ 0 0 0 ]
10: [ 0 1 4 ] [ 0 0 4 ]
11: [ 0 2 0 ] [ 0 0 0 ]
12: [ 0 2 1 ] [ 0 0 0 ]
13: [ 0 2 2 ] [ 0 0 0 ]
14: [ 0 2 3 ] [ 0 0 0 ]
15: [ 0 2 4 ] [ 0 0 4 ]
16: [ 0 3 0 ] [ 0 0 0 ]
17: [ 0 3 1 ] [ 0 0 0 ]
18: [ 0 3 2 ] [ 0 0 0 ]
19: [ 0 3 3 ] [ 0 0 0 ]
20: [ 0 3 4 ] [ 0 0 4 ]
21: [ 0 4 0 ] [ 0 4 4 ]
22: [ 0 4 1 ] [ 0 4 4 ]
23: [ 0 4 2 ] [ 0 4 4 ]
24: [ 0 4 3 ] [ 0 4 4 ]
25: [ 0 4 4 ] [ 0 4 4 ]
26: [ 0 4 5 ] [ 0 4 4 ]
27: [ 0 4 6 ] [ 0 4 4 ]
28: [ 0 4 7 ] [ 0 4 4 ]
29: [ 0 4 8 ] [ 0 4 8 ]
[Joerg Arndt, Apr 30 2011]
MAPLE
A004213 := proc(n)
add(4^(n-m)*combinat[stirling2](n, m), m=0..n) ;
end proc:
seq(A004213(n), n=0..30) ; # R. J. Mathar, Aug 20 2022
MATHEMATICA
Table[4^n BellB[n, 1/4], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 20 2015 *)
PROG
(PARI) x='x+O('x^66);
egf=exp(intformal(exp(4*x))); /* = 1 + x + 5/2*x^2 + 29/6*x^3 + 67/8*x^4 + ... */
/* egf=exp(1/4*(exp(4*x)-1)) */ /* alternative computation */
Vec(serlaplace(egf)) /* Joerg Arndt, Apr 30 2011 */
(Maxima)
a(n):=if n=0 then 1 else sum(4^(n-k)*binomial(n-1, k-1)*a(k-1), k, 1, n); \\ Vladimir Kruchinin, Nov 28 2011
CROSSREFS
KEYWORD
nonn,easy,eigen
AUTHOR
STATUS
approved