A168377 -id:A168377 - cp's OEIS frontend

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

Emeric Deutsch

nonn

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

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

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

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

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

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

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

[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

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

Corrected Hankel transform by Paul Barry, Nov 04 2009

A096470 Triangle T(n,k), read by rows, formed by setting all entries in the zeroth column and in the main diagonal ((n,n) entries) to 1 and defining the rest of the entries by the recursion T(n,k) = T(n-1,k) - T(n,k-1).

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, -1, 2, 1, 1, -2, 4, -3, 1, 1, -3, 7, -10, 11, 1, 1, -4, 11, -21, 32, -31, 1, 1, -5, 16, -37, 69, -100, 101, 1, 1, -6, 22, -59, 128, -228, 329, -328, 1, 1, -7, 29, -88, 216, -444, 773, -1101, 1102, 1, 1, -8, 37, -125, 341, -785, 1558, -2659, 3761, -3760, 1, 1, -9, 46, -171, 512, -1297, 2855, -5514, 9275, -13035, 13036, 1

Offset: 0

Gerald McGarvey, Aug 12 2004

If A(x,y) is the bivariate o.g.f. of a triangular array T(n,k) and B(x,y) is the bivariate o.g.f. of its mirror image T(n,n-k), then B(x,y) = A(x*y, y^(-1)) and A(x,y) = B(x*y, y^(-1)). - Petros Hadjicostas, Aug 08 2020

			From _Petros Hadjicostas_, Aug 08 2020: (Start)
Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins:
  1;
  1,  1;
  1,  0,  1;
  1, -1,  2,   1;
  1, -2,  4,  -3,   1;
  1, -3,  7, -10,  11,    1;
  1, -4, 11, -21,  32,  -31,   1;
  1, -5, 16, -37,  69, -100, 101,    1;
  1, -6, 22, -59, 128, -228, 329, -328, 1;
  ... (End)

Cf. A000108, A000124, A032357, A033297, A168377.

T(n, k) = if ((k==0) || (n==k), 1, if ((n<0) || (k<0), 0, if (n>k, T(n-1, k) - T(n, k-1), 0)));
for(n=0, 10, for (k=0, n, print1(T(n, k), ", ")); print); \\ Petros Hadjicostas, Aug 08 2020

T(n,k) = T(n-1,k) - T(n,k-1) for 1 <= k <= n-1 with T(n,0) = 1 = T(n,n) for n >= 0.
The 2nd column is T(n,2) = A000124(n-2) for n >= 2 (Hogben's central polygonal numbers).
The "first subdiagonal" (unsigned) is |T(n,n-1)| = A032357(n-1) for n >= 1 (Convolution of Catalan numbers and powers of -1).
The "2nd subdiagonal" (unsigned) is |T(n,n-2)| = A033297(n) = Sum_{i=0..n-2} (-1)^i*C(n-1-i) for n >= 2, where C(n) are the Catalan numbers (A000108).
From Petros Hadjicostas, Aug 08 2020: (Start)
|T(n,k)| = |A168377(n,n-k)| for 0 <= k <= n.
Bivariate o.g.f.: (1 + y + x*y*c(-x*y))/((1 - x*y)*(1 - x + y)), where c(x) = 2/(1 + sqrt(1 - 4*x)) = o.g.f. of A000108.
Bivariate o.g.f. of |T(n,k)|: (1 - y - x*y*c(x*y))/((1 + x*y)*(1 - x - y)) + 2*x*y/(1 - x^2*y^2).
Bivariate o.g.f. of mirror image T(n,n-k): (1 + y + x*y*c(-x))/((1 - x)*(1 + y - x*y^2)).
Bivariate o.g.f. of |T(n,n-k)|: (1 - y + x*y*c(x))/((1 + x)*(1 - y + x*y^2)) + 2*x/(1 - x^2). (End)

Offset changed to 0 by Petros Hadjicostas, Aug 08 2020

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions