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

Author

Emeric Deutsch

Keywords

• nonn

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

Examples

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

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

Crossrefs

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

Programs

Magma

[(-1)^(n+1)*(&+[(-1)^j*Catalan(j): j in [1..n-1]]): n in [2..40]]; // G. C. Greubel, May 30 2022

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

PARI

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

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

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

Extensions

Corrected Hankel transform by Paul Barry, Nov 04 2009