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.

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

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

D-finite with recurrence n*a(n) = 3*(n-2)*a(n-1) + 2*(2*n-3)*a(n-2). - 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, 40}] (* Alexander Adamchuk, Jul 01 2006 *)
Rest[Rest[CoefficientList[Series[(1-2*x-Sqrt[1-4*x])/(2*(1+x)), {x, 0, 40}], x]]] (* Vaclav Kotesovec, Feb 13 2014 *)
Table[CatalanNumber[n-1] Hypergeometric2F1[1, -n, 3/2-n, -1/4] +(-1)^n 3/2, {n, 2, 40}] (* Peter Luschny, Nov 22 2016 *)

Prog

(PARI) my(x='x+O('x^66)); Vec((1-2*x-sqrt(1-4*x))/(2*(1+x))) /* Joerg Arndt, Apr 07 2013 */
(Magma) [(-1)^(n+1)*(&+[(-1)^j*Catalan(j): j in [1..n-1]]): n in [2..40]]; // G. C. Greubel, May 30 2022
(SageMath) [sum((-1)^j*catalan_number(n-j-1) for j in (0..n-2)) for n in (2..40)] # G. C. Greubel, May 30 2022

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