A005554 Sums of successive Motzkin numbers. (Formerly M0801)

1, 2, 3, 6, 13, 30, 72, 178, 450, 1158, 3023, 7986, 21309, 57346, 155469, 424206, 1164039, 3210246, 8893161, 24735666, 69051303, 193399578, 543310782, 1530523638, 4322488212, 12236130298, 34713220977, 98677591278

Offset

1,2

Comments

The Donaghey reference shows that a(n) is the number of n-vertex binary trees such that for each non-root vertex that is incident to exactly two edges, these two edges have opposite slope. It also notes that these trees correspond to Dyck n-paths (A000108) containing no DUDUs and no subpaths of the form UUPDD with P a nonempty Dyck path. For example, a(3)=3 counts UUDUDD, UDUUDD, UUDDUD. - David Callan, Sep 25 2006

Hankel transform of the sequence starting with 2 appears to be 3, 4, 5, 6, 7, ... Gary W. Adamson, May 27 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 = 1..1000

R. Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.

Jocelyn Quaintance and Harris Kwong, A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13 (2013), #A29.

Formula

Inverse binomial transform of A014138: (1, 3, 8, 22, 64, 196, ...). - Gary W. Adamson, Nov 23 2007

D-finite with recurrence (n + 1)*a(n) = 2*n*a(n - 1) + (3*n - 9)*a(n - 2).

G.f.: (x+x^2)*M(x) where M(x)=(1 - x - (1 - 2*x - 3*x^2)^(1/2))/(2*x^2) is the g.f. for the Motzkin numbers A001006. - David Callan, Sep 25 2006

a(n) = (-1)^n*2*hypergeometric([2-n,5/2],[4],4), for n>1. - Peter Luschny, Aug 15 2012

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

a(n) = (2*Sum_{j=0..(n+2)/2} (binomial(n,j)*binomial(n-j+1,n-2*j+2)))/n. - Vladimir Kruchinin, Oct 04 2015

Mathematica

Rest[CoefficientList[Series[(x+x^2)*(1-x-(1-2*x-3*x^2)^(1/2))/(2*x^2), {x, 0, 20}], x]] (* Vaclav Kotesovec, Mar 21 2014 *)

Prog

(Maxima)
a(n):=(2*sum(binomial(n, j)*binomial(n-j+1, n-2*j+2), j, 0, (n+2)/2))/n; /* Vladimir Kruchinin, Oct 04 2015 */
(PARI) a(n) = sum(k=0, (n+2)/2, 2*(binomial(n, k)*binomial(n-k+1, n-2*k+2)/n));
vector(40, n, if(n==1, 1, a(n-1))) \\ Altug Alkan, Oct 04 2015

Crossrefs

Enumerates the branch-reduced trees encoded by A080981. Cf. A001006.

First differences are in A102071.

Cf. A014138.

A diagonal of A059346.

Sequence in context: A280746 A174191 A052937 * A316766 A300660 A077212

Adjacent sequences: A005551 A005552 A005553 * A005555 A005556 A005557

Keyword

nonn

Author

N. J. A. Sloane

Extensions

More terms from James A. Sellers, Jul 10 2000

Status

approved