login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)
10
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; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Number of ordered trees with n+1 edges, having root degree at least 2 and nonroot outdegrees at most 2. - Emeric Deutsch, Aug 02 2002

From Petkovsek's algorithm, this recurrence does not have any closed form solutions. So there is no hypergeometric closed form for a(n). - Herbert S. Wilf

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, Feb 07 2004

Image of n (A001477) under the Motzkin related matrix A107131. Binomial transform of A037952. - Paul Barry, 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, Aug 16 2006

Image of the sequence (0,1,2,3,3,3,...) under the array A122896. - Paul Barry, 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. - R. J. Mathar, Nov 08 2008

REFERENCES

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

P. Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.

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.

Christian Krattenthaler, Daniel Yaqubi, Some determinants of path generating functions, II, arXiv:1802.05990 [math.CO], 2018.

Simon Plouffe, Approximations de Séries Génératrices et Quelques Conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, Une méthode pour obtenir la fonction génératrice d'une série, FPSAC 1993, Florence. Formal Power Series and Algebraic Combinatorics.

FORMULA

Inverse binomial transform of [ 0, 1, 5, 21, 84, ... ] (A002054). - John W. Layman.

(n+2)*(n-1)*a(n) = 2*n*(n+1)*a(n-1) + 3*n*(n-1)*a(n-2) for all n in Z. - Michael Somos, May 01 2003

E.g.f.: exp(x)*(BesselI(1, 2*x)+BesselI(2, 2*x)). - Vladeta Jovovic, 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, May 12 2005

Starting (1, 3, 9, 26,...) = binomial transform of A026010: (1, 2, 4, 7, 14, 25, 50, 91,...). - Gary W. Adamson, Oct 22 2007

a(n)*(2 +n) = (4+4*n)*a(n-1) - n*a(n-2) + (12-6*n)*a(n-3). - Simon Plouffe, Feb 09 2012

a(n) ~ 3^(n+1/2) / sqrt(Pi*n). - Vaclav Kotesovec, Mar 10 2014

0 = a(n)*(+36*a(n+1) + 18*a(n+2) - 96*a(n+3) + 30*a(n+4)) + a(n+1)*(-6*a(n+1) + 49*a(n+2) - 26*a(n+3) + 3*a(n+4)) + a(n+2)*(+15*a(n+3) - 8*a(n+4)) + a(n+3)*(a(n+4)) if n>=0. - Michael Somos, Aug 06 2014

a(n) = GegenbauerC(n-2,-n,-1/2) + GegenbauerC(n-1,-n,-1/2). - Peter Luschny, May 12 2016

EXAMPLE

G.f.: x + 3*x^2 + 9*x^3 + 26*x^4 + 75*x^5 + 216*x^6 + 623*x^7 + ...

MAPLE

seq( add(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

seq(simplify(GegenbauerC(n-2, -n, -1/2) + GegenbauerC(n-1, -n, -1/2)), n=0..27); # Peter Luschny, May 12 2016

MATHEMATICA

CoefficientList[Series[(1-x-Sqrt[1-2x-3x^2])/(x(1-3x+Sqrt[1-2x-3x^2])), {x, 0, 30}], x] (* Harvey P. Dale, Sep 20 2011 *)

RecurrenceTable[{a[0]==0, a[1]==1, a[n]==(2n(n+1)a[n-1]+3n(n-1)a[n-2])/ ((n+2)(n-1))}, a, {n, 30}] (* Harvey P. Dale, Nov 09 2012 *)

PROG

(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))}; /* Michael Somos, May 01 2003 */

(Haskell)

a005774 0 = 0

a005774 n = a038622 n 1 -- Reinhard Zumkeller, Feb 26 2013

CROSSREFS

Cf. A038622, A098494, A026010, A005773, A005775, A066822.

Sequence in context: A076264 A018919 A123941 * A273343 A101169 A119826

Adjacent sequences:  A005771 A005772 A005773 * A005775 A005776 A005777

KEYWORD

nonn,easy,nice

AUTHOR

Simon Plouffe

EXTENSIONS

Further descriptions from Clark Kimberling

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 21 21:42 EDT 2018. Contains 313957 sequences. (Running on oeis4.)