login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A004212 Shifts one place left under 3rd-order binomial transform.
(Formerly M3557)
24
1, 1, 4, 19, 109, 742, 5815, 51193, 498118, 5296321, 60987817, 754940848, 9983845261, 140329768789, 2087182244308, 32725315072135, 539118388883449, 9304591246975030, 167804098493079547, 3155000165773280893 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
Equals the eigensequence of triangle A027465, the cube of Pascal's triangle. - Gary W. Adamson, Apr 10 2009
Length-n restricted growth strings (RGS) [s(0),s(1),...,s(n-1)] where s(k)<=F(k)+3 where F(0)=0 and F(k+1)=s(k+1) if s(k+1)-s(k)=3, 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
Joerg Arndt, Matters Computational (The Fxtbook), section 17.3.5, pp. 366-368
I. M. Gessel, Applications of the classical umbral calculus. arXiv:math/0108121v3 [math.CO], 2001.
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_{k=0..n} 3^(n-k)*Stirling2(n, k). - Emeric Deutsch, Feb 11 2002
E.g.f.: exp((exp(3*x)-1)/3).
O.g.f. A(x) satisfies A'(x)/A(x) = e^(3*x).
E.g.f.: exp(int(t=0..x, exp(3*t))). - Joerg Arndt, Apr 30 2011
O.g.f.: Sum_{k>=0} x^k/Product_{j=1..k} (1-3*j*x). - Joerg Arndt, Apr 30 2011
Hankel transform is A000178(n)*3^C(n+1,2). - Paul Barry, Mar 31 2008
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/2)*3^{n-1}*f_n(1/3). - Milan Janjic, May 30 2008
a(n) = the upper left term in M^n, M = the following infinite square production matrix:
1, 3, 0, 0, 0, ...
1, 1, 3, 0, 0, ...
1, 2, 1, 3, 0, ...
1, 3, 3, 1, 3, ...
... (in which a diagonal of (3,3,3,...) is appended to the right of Pascal's triangle). - Gary W. Adamson, Jul 29 2011
G.f. satisfies A(x) = 1+x/(1-3*x)*A(x/(1-3*x)). a(n) = Sum_{k=1..n} 3^(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]
From Peter Bala, May 16 2012: (Start)
Recurrence equation: a(n+1) = Sum_{k = 0..n} 3^(n-k)*C(n,k)*a(k). Written umbrally this is a(n+1) = (a+3)^n (expand the binomial and replace a^k with a(k)). More generally, a*f(a) = f(a+3) holds umbrally for any polynomial f(x). An inductive argument then establishes the umbral recurrence a*(a-3)*(a-6)*...*(a-3*(n-1)) = 1 with a(0) = 1. Compare with the Bell numbers B(n) = A000110(n), which satisfy the umbral recurrence B*(B-1)*...*(B-(n-1)) = 1 with B(0) = 1.
Touchard's congruence holds for prime p not equal to 3: a(p+k) = (a(k) + a(k+1)) (mod p) for k = 0,1,2,... (adapt the proof of Theorem 10.1 in Gessel). In particular, a(p) = 2 (mod p) for prime p <> 3.
(End)
G.f.: (G(0) - 1)/(x-1) where G(k) = 1 - 1/(1-x*3*k)/(1-x/(x-1/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Jan 16 2013
G.f.: T(0)/(1-x), where T(k) = 1 - 3*x^2*(k+1)/( 3*x^2*(k+1) - (1-x-3*x*k)*(1-4*x-3*x*k)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 19 2013
a(n) ~ 3^n * n^n * exp(n/LambertW(3*n) - 1/3 - n) / (sqrt(1 + LambertW(3*n)) * LambertW(3*n)^n). - Vaclav Kotesovec, Jul 15 2021
EXAMPLE
Restricted growth strings: a(0)=1 corresponds to the empty string, a(1)=1 to [0],
a(2)=3 to [00], [01], [02], and [03], a(3) = 19 to
RGS F
01: [ 0 0 0 ] [ 0 0 0 ]
02: [ 0 0 1 ] [ 0 0 0 ]
03: [ 0 0 2 ] [ 0 0 0 ]
04: [ 0 0 3 ] [ 0 0 3 ]
05: [ 0 1 0 ] [ 0 0 0 ]
06: [ 0 1 1 ] [ 0 0 0 ]
07: [ 0 1 2 ] [ 0 0 0 ]
08: [ 0 1 3 ] [ 0 0 3 ]
09: [ 0 2 0 ] [ 0 0 0 ]
10: [ 0 2 1 ] [ 0 0 0 ]
11: [ 0 2 2 ] [ 0 0 0 ]
12: [ 0 2 3 ] [ 0 0 3 ]
13: [ 0 3 0 ] [ 0 3 3 ]
14: [ 0 3 1 ] [ 0 3 3 ]
15: [ 0 3 2 ] [ 0 3 3 ]
16: [ 0 3 3 ] [ 0 3 3 ]
17: [ 0 3 4 ] [ 0 3 3 ]
18: [ 0 3 5 ] [ 0 3 3 ]
19: [ 0 3 6 ] [ 0 3 6 ]
- Joerg Arndt, Apr 30 2011
MATHEMATICA
Table[Sum[StirlingS2[n, k] 3^(-k+n), {k, n}], {n, 20}] (* Vincenzo Librandi, May 21 2012 *)
Table[3^n BellB[n, 1/3], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 20 2015 *)
PROG
(PARI) x='x+O('x^66); /* that many terms */
egf=exp(intformal(exp(3*x))); /* = 1 + x + 2*x^2 + 19/6*x^3 + 109/24*x^4 + ... */
/* egf=exp(1/3*(exp(3*x)-1)) */ /* alternative computation */
Vec(serlaplace(egf)) /* show terms */ /* Joerg Arndt, Apr 30 2011 */
(Maxima)
a(n):=if n=0 then 1 else sum(3^(n-k)*binomial(n-1, k-1)*a(k-1), k, 1, n); /* Vladimir Kruchinin, Nov 28 2011 */
CROSSREFS
Cf. A075498 (row sums).
Cf. A027465. - Gary W. Adamson, Apr 10 2009
Cf. A004211 (RGS where s(k)<=F(k)+2), A004213 (s(k)<=F(k)+4), A005011 (s(k)<=F(k)+5), A000110 (s(k)<=F(k)+1). - Joerg Arndt, Apr 30 2011
Cf. A009235.
Sequence in context: A241840 A199318 A117397 * A243241 A060905 A304473
KEYWORD
nonn,easy,eigen
AUTHOR
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 07:19 EDT 2024. Contains 370954 sequences. (Running on oeis4.)