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.
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.
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
KEYWORD
nonn
AUTHOR
EXTENSIONS
More terms from James A. Sellers, Jul 10 2000
STATUS
approved