|
| |
|
|
A004212
|
|
Shifts one place left under 3rd-order binomial transform.
(Formerly M3557)
|
|
22
|
|
|
|
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
|
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
|
|
|
|
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
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]
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 ]
|
|
|
MATHEMATICA
|
Table[Sum[StirlingS2[n, k] 3^(-k+n), {k, n}], {n, 20}] (* Vincenzo Librandi, May 21 2012 *)
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,easy,eigen
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
