A005554 Sums of successive Motzkin numbers.

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

Author

N. J. A. Sloane

Keywords

• nonn

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
• Robert Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.
• Rosa Orellana, Nancy Wallace, and Mike Zabrocki, Quasipartition and planar quasipartition algebras, Sém. Lotharingien Comb., Proc. 36th Conf. Formal Power Series Alg. Comb. (2024) Vol. 91B, Art. No. 50. See p. 11.
• Jocelyn Quaintance and Harris Kwong, A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13 (2013), #A29.
• Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 99.

Crossrefs

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

First differences are in A102071.

Cf. A014138.

A diagonal of A059346.

Programs

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 *)

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

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

Extensions

More terms from James Sellers, Jul 10 2000