login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A033297 Number of ordered rooted trees with n edges such that the rightmost leaf of each subtree is at even level. Equivalently, number of Dyck paths of semilength n with no return descents of odd length. 8
1, 1, 4, 10, 32, 100, 329, 1101, 3761, 13035, 45751, 162261, 580639, 2093801, 7601044, 27756626, 101888164, 375750536, 1391512654, 5172607766, 19293659254, 72188904386, 270870709264, 1019033438060, 3842912963392 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,3

COMMENTS

Sums of two consecutive terms are the Catalan numbers.

Prime p divides a(p-1) and a(p+1) for odd primes where 5 is a square mod p (A038872). - Alexander Adamchuk, Jul 01 2006

Hankel transform of 1, 1, 4, ... is A167477.

Hankel transform of a(n+1) (starts 0, 1, 1, 4, ...) is -F(2*n), where F = A000045. - Paul Barry, Dec 16 2008

We could extend the sequence with a(0) = 1, a(1) = 0 so that a(n) + a(n+1) = Catalan(n) for all n >= 0. - Michael Somos, Nov 22 2016

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 2..1000

Juan B. Gil and Jordan O. Tirrell, A simple bijection for classical and enhanced k-noncrossing partitions, arXiv:1806.09065 [math.CO], 2018.

Juan B. Gil and Jordan O. Tirrell, A simple bijection for classical and enhanced k-noncrossing partitions, Discrete Mathematics 343(6) (2019), Article 111705.

Index entries for sequences related to rooted trees

FORMULA

a(n) = Sum_{i=0..n-2} (-1)^i*C(n-1-i), where C(n) are the Catalan numbers A000108.

G.f.: (1 - 2*z - sqrt(1 - 4*z)) / (2*(1 + z)).

a(n) = Catalan(n-1)*hypergeom([1, -n], [3/2 - n], -1/4) + (-1)^n*3/2. - Erroneous formula replaced by Peter Luschny, Nov 22 2016

Conjecture: n*a(n) + 3*(-n+2)*a(n-1) + 2*(-2*n+3)*a(n-2) = 0. - R. J. Mathar, Nov 30 2012

G.f.: 2/(G(0) - 2*x)/(1 + x), where G(k) = k*(4*x + 1) + 2*x + 2 - x*(2*k + 3)*(2*k + 4)/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Apr 06 2013

a(n) = A168377(n,2). - Philippe Deléham, Feb 09 2014

a(n) ~ 4^n/(5*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Feb 13 2014

EXAMPLE

G.f. = x^2 + x^3 + 4*x^4 + 10*x^5 + 32*x^6 + 100*x^7 + 329*x^8 + 1101*x^9 + ...

MATHEMATICA

Table[Sum[(-1)^(n+k)*(2k)!/k!/(k+1)!, {k, 1, n}], {n, 1, 72}] - Alexander Adamchuk, Jul 01 2006

Rest[Rest[CoefficientList[Series[(1-2*x-Sqrt[1-4*x])/(2*(1+x)), {x, 0, 20}], x]]] (* Vaclav Kotesovec, Feb 13 2014 *)

Table[CatalanNumber[n-1] Hypergeometric2F1[1, -n, 3/2-n, -1/4] + (-1)^n 3/2, {n, 2, 26}] (* Peter Luschny, Nov 22 2016 *)

PROG

(PARI) x='x+O('x^66); Vec((1-2*x-sqrt(1-4*x))/(2*(1+x))) /* Joerg Arndt, Apr 07 2013 */

CROSSREFS

Cf. A000045, A000108, A038872, A167477, A168377.

Sequence in context: A295404 A001673 A017936 * A129880 A303832 A316103

Adjacent sequences:  A033294 A033295 A033296 * A033298 A033299 A033300

KEYWORD

nonn

AUTHOR

Emeric Deutsch

EXTENSIONS

Corrected Hankel transform by Paul Barry, Nov 04 2009

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 17 22:15 EDT 2021. Contains 343992 sequences. (Running on oeis4.)