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