|
Search: id:A005774
|
|
|
| A005774 |
|
Number of directed animals of size n (k=1 column of A038622); number of (s(0), s(1), ..., s(n)) such that s(i) is a nonnegative integer and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, where s(0) = 2; also sum of row n+1 of array T in A026323.
(Formerly M2804)
|
|
+0
8
|
|
| 0, 1, 3, 9, 26, 75, 216, 623, 1800, 5211, 15115, 43923, 127854, 372749, 1088283, 3181545, 9312312, 27287091, 80038449, 234988827, 690513030, 2030695569, 5976418602, 17601021837, 51869858544, 152951628725, 451271872701, 1332147482253
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
Number of ordered trees with n+1 edges, having root degree at least 2 and nonroot outdegrees at most 2. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Aug 02 2002
Herbert S. Wilf (wilf(AT)math.upenn.edu): From Petkovsek's algorithm, this recurrence does not have any closed form solutions. So there is no hypergeometric closed form for a(n).
Sum of two consecutive trinomial coefficients starting two positions before central one. Example: a(4)=10+16 and (1+x+x^2)^4=...+10x^2+16x^3+19x^4+... - David Callan (callan(AT)stat.wisc.edu), Feb 07 2004
Image of n (A001477) under the Motzkin related matrix A107131. Binomial transform of A037952. - Paul Barry (pbarry(AT)wit.ie), May 12 2005
a(n) = total number of ascents (maximal runs of consecutive upsteps) in all Motzkin (n+1)-paths. For example, the 9 Motzkin 4-paths are FFFF, FFUD, FUDF, FUFD, UDFF, UDUD, UFDF, UFFD, UUDD and they contain a total of 9 ascents and so a(3)=9 (U=upstep, D=downstep, F=flatstep). - David Callan (callan(AT)stat.wisc.edu), Aug 16 2006
Image of the sequence (0,1,2,3,3,3,...) under the array A122896. - Paul Barry (pbarry(AT)wit.ie), Sep 18 2006
This is some kind of Motzkin transform of A079978 because the substitution x->x*A001006(x) in the independent variable of the g.f. A079978(x) yields 1,0 followed by this sequence here. [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Nov 08 2008]
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
D. Gouyou-Beauchamps; G. Viennot, Equivalence of the two-dimensional directed animal problem to a one-dimensional path problem, Adv. in Appl. Math. 9 (1988), no. 3, 334-357.
|
|
FORMULA
|
Inverse binomial transform of [ 0, 1, 5, 21, 84, ... ] (A002054) - John Layman (layman(AT)calvin.math.vt.edu).
(n+2)(n-1)a(n) = 2n(n+1)a(n-1) + 3n(n-1)a(n-2).
E.g.f.: exp(x)*(BesselI(1, 2*x)+BesselI(2, 2*x)). - Vladeta Jovovic (vladeta(AT)eunet.rs), Jan 01 2004
G.f.: (1-x-sqrt(1-2x-3x^2))/(x(1-3x+sqrt(1-2x-3x^2))); a(n)=sum{k=0..n, C(k+1, n-k+1)*C(n, k)*k/(k+1)}; a(n)=sum{k=0..n, C(n, k)*C(k, floor((k-1)/2))}; - Paul Barry (pbarry(AT)wit.ie), May 12 2005
Starting (1, 3, 9, 26,...) = binomial transform of A026010: (1, 2, 4, 7, 14, 25, 50, 91,...). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 22 2007
|
|
MAPLE
|
seq( sum('binomial(i, k+1)*binomial(i-k, k)', 'k'=0..floor(i/2)), i=0..30 ); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001
|
|
PROGRAM
|
(PARI) s=[0, 1]; {A005774(n)=k=(2*(n+2)*(n+1)*s[2]+3*(n+1)*n*s[1])/((n+3)*n); s[1]=s[2]; s[2]=k; k}
(PARI) a(n)=if(n<2, n>0, (2*(n+1)*n*a(n-1)+3*(n-1)*n*a(n-2))/(n+2)/(n-1))
|
|
CROSSREFS
|
Cf. A038622, A098494, A026010.
Sequence in context: A076264 A123941 A018919 this_sequence A101169 A119826 A027915
Adjacent sequences: A005771 A005772 A005773 this_sequence A005775 A005776 A005777
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
Simon Plouffe (simon.plouffe(AT)gmail.com)
|
|
EXTENSIONS
|
Further descriptions from Clark Kimberling (ck6(AT)evansville.edu)
|
|
|
Search completed in 0.003 seconds
|
