|
%I #71 Jul 26 2022 16:28:32
%S 1,1,4,10,32,100,329,1101,3761,13035,45751,162261,580639,2093801,
%T 7601044,27756626,101888164,375750536,1391512654,5172607766,
%U 19293659254,72188904386,270870709264,1019033438060,3842912963392
%N 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.
%C Sums of two consecutive terms are the Catalan numbers.
%C 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
%C Hankel transform of 1, 1, 4, ... is A167477.
%C Hankel transform of a(n+1) (starts 0, 1, 1, 4, ...) is -F(2*n), where F = A000045. - _Paul Barry_, Dec 16 2008
%C 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
%H Vincenzo Librandi, <a href="/A033297/b033297.txt">Table of n, a(n) for n = 2..1000</a>
%H Juan B. Gil and Jordan O. Tirrell, <a href="https://arxiv.org/abs/1806.09065">A simple bijection for classical and enhanced k-noncrossing partitions</a>, arXiv:1806.09065 [math.CO], 2018.
%H Juan B. Gil and Jordan O. Tirrell, <a href="https://doi.org/10.1016/j.disc.2019.111705">A simple bijection for classical and enhanced k-noncrossing partitions</a>, Discrete Mathematics 343(6) (2019), Article 111705.
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F a(n) = Sum_{i=0..n-2} (-1)^i*C(n-1-i), where C(n) are the Catalan numbers A000108.
%F G.f.: (1 - 2*z - sqrt(1 - 4*z)) / (2*(1 + z)).
%F 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
%F 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
%F 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
%F a(n) = A168377(n,2). - _Philippe Deléham_, Feb 09 2014
%F a(n) ~ 4^n/(5*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Feb 13 2014
%e G.f. = x^2 + x^3 + 4*x^4 + 10*x^5 + 32*x^6 + 100*x^7 + 329*x^8 + 1101*x^9 + ...
%t Table[Sum[(-1)^(n+k)*(2k)!/k!/(k+1)!,{k,1,n}],{n,1,40}] (* _Alexander Adamchuk_, Jul 01 2006 *)
%t Rest[Rest[CoefficientList[Series[(1-2*x-Sqrt[1-4*x])/(2*(1+x)), {x, 0, 40}], x]]] (* _Vaclav Kotesovec_, Feb 13 2014 *)
%t Table[CatalanNumber[n-1] Hypergeometric2F1[1,-n,3/2-n,-1/4] +(-1)^n 3/2, {n,2,40}] (* _Peter Luschny_, Nov 22 2016 *)
%o (PARI) my(x='x+O('x^66)); Vec((1-2*x-sqrt(1-4*x))/(2*(1+x))) /* _Joerg Arndt_, Apr 07 2013 */
%o (Magma) [(-1)^(n+1)*(&+[(-1)^j*Catalan(j): j in [1..n-1]]): n in [2..40]]; // _G. C. Greubel_, May 30 2022
%o (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
%Y Cf. A000045, A000108, A038872, A167477, A168377.
%K nonn
%O 2,3
%A _Emeric Deutsch_
%E Corrected Hankel transform by _Paul Barry_, Nov 04 2009
| 