cp's OEIS Frontend

A026641 Number of nodes of even outdegree (including leaves) in all ordered trees with n edges.

%I A026641 #173 Mar 21 2024 08:37:04
%S A026641 1,1,4,13,46,166,610,2269,8518,32206,122464,467842,1794196,6903352,
%T A026641 26635774,103020253,399300166,1550554582,6031074184,23493410758,
%U A026641 91638191236,357874310212,1399137067684,5475504511858,21447950506396
%N A026641 Number of nodes of even outdegree (including leaves) in all ordered trees with n edges.
%C A026641 Number of lattice paths from (0,0) to (n,n) using steps (1,0),(0,2),(1,1). - _Joerg Arndt_, Jun 30 2011
%C A026641 From _Emeric Deutsch_, Jan 25 2004: (Start)
%C A026641 Let B = 1/sqrt(1-4*z) = g.f. for central binomial coeffs (A000984); F = (1-sqrt(1-4*z))/(z*(3-sqrt(1-4*z))) = g.f. for (A000957).
%C A026641 B = 1 + 2*z + 6*z^2 + 20*z^3 + ... gives the number of nodes in all ordered trees with 0,1,2,3,... edges. On p. 288 of the Deutsch-Shapiro paper one finds that z*B*F = z + 2*z^2 + 7*z^3 + 24*z^4 + ... gives the number of nodes of odd outdegree in all ordered trees with 1,2,3,... edges (cf. A014300).
%C A026641 Consequently, B - z*B*F = 2/(3*sqrt(1-4*z)-1+4*z) = 1 + z + 4*z^2 + 13*z^3 + 46*z^4 + ... gives the total number of nodes of even degree in all ordered trees with 0,1,2,3,4,... edges.  (End)
%C A026641 Main diagonal of the following array: first column is filled with 1's, first row is filled alternatively with 1's or 0's: m(i,j) = m(i-1,j) + m(i,j-1): 1 0 1 0 1 ... / 1 1 2 2 3 ... / 1 2 4 6 9 ... / 1 3 7 13 22 ... / 1 4 11 24 46 ... - _Benoit Cloitre_, Aug 05 2002
%C A026641 The Hankel transform of [1,1,4,13,46,166,610,2269,...] is 3^n. - _Philippe Deléham_, Mar 08 2007
%C A026641 Second binomial transform of A127361. - _Philippe Deléham_, Mar 14 2007
%C A026641 Starting with offset 1, generated from iterates of M * [1,1,1,...]; where M = a tridiagonal matrix with (0,2,2,2,...) in the main diagonal and (1,1,1,...) in the super and subdiagonals. - _Gary W. Adamson_, Jan 04 2009
%C A026641 Equals left border of triangle A158815. - _Gary W. Adamson_, Mar 27 2009
%C A026641 Equals the INVERTi transform of A101850: (1, 2, 7, 26, 100, ...). - _Gary W. Adamson_, Jan 10 2012
%C A026641 Diagonal of rational function 1/(1 - (x + x*y + y^2)). - _Gheorghe Coserea_, Aug 06 2018
%C A026641 Let A(i, j) denote the infinite array such that the i-th row of this array is the sequence obtained by applying the partial sum operator i times to the function (-1)^(n+1) for n > 0. Then A(n, n) equals a(n-1) for all n > 0. - _John M. Campbell_, Jan 20 2019
%C A026641 These numbers have the same parity as the Catalan numbers A000108; that is, a(n) is odd if and only if n = 2^k - 1 for some nonnegative integer k. It appears that if a(n) is odd then a(n) == 1 (mod 4). - _Peter Bala_, Feb 07 2024
%C A026641 The number a(n)/(n+1) is the coefficient of x^(n+1) in log(1+(1-sqrt(1-4*x))/2), the generating series of the Sabinin operad. - _F. Chapoton_, Mar 14 2024
%H A026641 Vincenzo Librandi, <a href="/A026641/b026641.txt">Table of n, a(n) for n = 0..1000</a>
%H A026641 Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Barry/barry84.html">A Catalan Transform and Related Transformations on Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
%H A026641 Isaac DeJager, Madeleine Naquin, and Frank Seidl, <a href="https://www.valpo.edu/mathematics-statistics/files/2019/08/Drube2019.pdf">Colored Motzkin Paths of Higher Order</a>, VERUM 2019.
%H A026641 Emeric Deutsch and L. Shapiro, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00121-2">A survey of the Fine numbers</a>, Discrete Math., 241 (2001), 241-265.
%H A026641 Karl Dilcher and Maciej Ulas, <a href="https://arxiv.org/abs/1909.11222">Arithmetic properties of polynomial solutions of the Diophantine equation P(x)x^(n+1)+Q(x)(x+1)^(n+1) = 1</a>, arXiv:1909.11222 [math.NT], 2019.
%H A026641 Filippo Disanto, Andrea Frosini and Simone Rinaldi, Renzo Pinzani, <a href="http://www.seams-bull-math.ynu.edu.cn/downloadfile.jsp?filemenu=_200805&amp;filename=The%20Combinatorics%20of%20Convex%20Permutominoes.pdf">The Combinatorics of Convex Permutominoes</a>, Southeast Asian Bulletin of Mathematics (2008) 32: 883-912.
%F A026641 G.f. is logarithmic derivative of the generating function for the Catalan numbers A000108. So this sequence might be called the "log-Catalan" numbers. - _Murray R. Bremner_, Jan 25 2004
%F A026641 a(n) = Sum_{k=0..floor(n/2)} binomial(k+n, n-k)*binomial(n-k, k). - Detlef Pauly (dettodet(AT)yahoo.de), Nov 15 2001
%F A026641 G.f.: 2/(3*sqrt(1-4*z)-1+4*z). - _Emeric Deutsch_, Jul 09 2002
%F A026641 a(n) = (-1)^n*Sum_{k=0..n} (-1)^k*C(n+k, k). - _Benoit Cloitre_, Aug 20 2002
%F A026641 a(n) = Sum_{j=0..floor(n/2)} binomial(2*n-2*j-1, n-1). - _Emeric Deutsch_, Jan 28 2004
%F A026641 From _Paul Barry_, Dec 18 2004: (Start)
%F A026641 A Catalan transform of the Jacobsthal numbers A001045(n+1) under the mapping G(x)-> G(xc(x)), c(x) the g.f. of A000108. The inverse mapping is H(x)->H(x(1-x)).
%F A026641 a(n) = Sum_{k=0..n} (k/(2*n-k))*binomial(2*n-k, n-k)*A001045(k+1). (End)
%F A026641 a(n) = Sum_{k=0..n} binomial(2*n-k, k)*binomial(k, n-k). - _Paul Barry_, Jul 25 2005
%F A026641 a(n) = Sum_{k=0..n-1} A126093(n,k). - _Philippe Deléham_, Mar 08 2007
%F A026641 a(n) = (-1/2)^(n+2) + (2/3)*Sum_{k=0..n} ( (4^n-k)*binomial(2*k,k)*(1/(1-2*k))*(1-(-1/8)^(n-k+1)) ). - _Yalcin Aktar_, Jul 06 2007
%F A026641 a(n) = (-1/2)^(n+2) + (3/4)*Sum_{k=0..n} (-1/2)^(n-k)*binomial(2*k,k). - _Yalcin Aktar_, Jul 06 2007
%F A026641 From _Richard Choulet_, Jan 22 2010: (Start)
%F A026641 a(n) = (3*binomial(2*n-1,n-1) - d(n-1))/2, where d(n) = Sum_{k=floor(n/2)..n} binomial(2*n-k, k)*binomial(k, n-k).
%F A026641 a(n) = a(n-1) + (3/2)*Sum_{k=2..n} (1/(2*k-1))*binomial(2*k,k)*a(n-k).
%F A026641 a(n) = (2/3)*binomial(2*n,n) + (2/9)*((-2)^n/n!)*Sum_{k>=0} ( Product_{p=0..n-1} (k-2*p) /3^k).
%F A026641 a(n) = Sum_{k=0..n} (-1)^k*binomial(2*n-k,n).
%F A026641 a(n) = ( Sum_{k=0..n} (1/2)^(n-k+1)*binomial(n+k,k) )^2*(-1/2)^(n+2). (End)
%F A026641 From _Gary W. Adamson_, Nov 22 2011: (Start)
%F A026641 a(n) is the upper left term of M^n, M = an infinite square production matrix as follows:
%F A026641   1, 3, 0, 0, 0, ...
%F A026641   1, 1, 1, 0, 0, ...
%F A026641   1, 1, 1, 1, 0, ...
%F A026641   1, 1, 1, 1, 1, ...
%F A026641   ...
%F A026641 Also, a(n+1) is the sum of top row terms of M^n; e.g. top row of M^3 = (13, 21, 9, 3), sum = 46 = a(4), a(3) = 13. (End)
%F A026641 D-finite with recurrence: 2n*a(n) + (4-7n)*a(n-1) + 2*(1-2n)*a(n-2) = 0. - _R. J. Mathar_, Dec 17 2011 [The recurrence is proved with the Wilf-Zeilberger (WZ) method applied to Sum_{k=0..floor(n/2)} binomial(k+n, n-k)*binomial(n-k, k). - _T. Amdeberhan_, Jul 23 2012]
%F A026641 a(n) = A035317(2*n-1,n) for n > 0. - _Reinhard Zumkeller_, Jul 19 2012
%F A026641 a(n) ~ 2^(2*n+1) / (3*sqrt(Pi*n)). - _Vaclav Kotesovec_, Feb 12 2014
%F A026641 a(n) = binomial(2*n,n)*hypergeom([1, -n], [-2*n], -1). - _Peter Luschny_, May 22 2014
%F A026641 G.f. is the derivative of the logarithm of the g.f. for A120588. - _Michael Somos_, May 18 2015
%F A026641 a(n) = [x^n] 1/((1 - x^2)*(1 - x)^n). - _Ilya Gutkovskiy_, Oct 25 2017
%F A026641 From _Peter Bala_, Feb 25 2019: (Start)
%F A026641 a(n) = Sum_{k = 0..n} binomial(2*n + 1, n + k + 1)*(-2)^k.
%F A026641 a(n-1) = (1/2)*binomial(2*n,n)*( 1 - 2*(n-1)/(n+1) + 4*(n-1)*(n-2)/((n+1)*(n+2)) - 8*(n-1)*(n-2)*(n-3)/((n+1)*(n+2)*(n+3)) + ...) = (1/2)*binomial(2*n,n)*hypergeom([1 - n, 1], [n + 1], 2). (End)
%F A026641 a(0)=1, a(1)=1, and a(n) = (2 - 1/n)*a(n-2) + (7/2 - 2/n)*a(n-1) for n > 1. - _Reginald Robson_, Nov 01 2022
%e A026641 From _Joerg Arndt_, Jul 01 2011: (Start)
%e A026641 The triangle of number of lattice paths from (0,0) to (n,k) using steps (1,0),(0,2),(1,1) begins
%e A026641   1;
%e A026641   1, 1;
%e A026641   1, 2,  4;
%e A026641   1, 3,  7, 13;
%e A026641   1, 4, 11, 24,  46;
%e A026641   1, 5, 16, 40,  86, 166;
%e A026641   1, 6, 22, 62, 148, 314,  610;
%e A026641   1, 7, 29, 91, 239, 553, 1163, 2269;
%e A026641 This sequence is the diagonal. (End)
%e A026641 G.f. = 1 + x + 4*x^2 + 13*x^3 + 46*x^4 + 166*x^5 + 610*x^6 + 2269*x^7 + ...
%p A026641 seq(add((binomial(k+n, n-k)*binomial(n-k, k)),k=0..floor(n/2)),n=0..30);
%p A026641 # From _Richard Choulet_, Jan 22 2010: (Start)
%p A026641 a:= n -> add(binomial(2*n-k, k)*binomial(k, n-k), k=floor(n/2)..n):
%p A026641 a:= n -> `if`(n<2, 1, (3/(2))*binomial(2*n-1, n-1)-(1/2)*a(n-1)):
%p A026641 a:= n -> (-1/2)^(n+2)+(2/3)*add(4^(n-k)*(binomial(2*k, k)*(1/(1-2*k))
%p A026641         *(1-(-1/8)^(n-k+1))), k=0..n):
%p A026641 a:= n -> (-1/2)^(n+2)+(3/4)*add(((-1/2)^(n-k))*(binomial(2*k, k)), k=0..n):
%p A026641 seq(a(n), n=0..30); # (End)
%p A026641 gf := log(1 + (1 - sqrt(1 - 4*x))/2) / x: ser := series(gf, x, 30):
%p A026641 seq((n + 1)*coeff(ser, x, n), n = 0..24);  # _Peter Luschny_, Mar 16 2024
%t A026641 f[n_]:= Sum[ Binomial[n+k, k]*Cos[Pi*(n+k)], {k, 0, n}]; Array[f, 25, 0] (* _Robert G. Wilson v_, Apr 02 2012 *)
%t A026641 CoefficientList[Series[2/(3*Sqrt[1-4*x]-1+4*x), {x, 0, 20}], x] (* _Vaclav Kotesovec_, Feb 12 2014 *)
%t A026641 a[ n_]:= SeriesCoefficient[ D[ Log[1+(1-Sqrt[1-4x])/2], x], {x, 0, n}]; (* _Michael Somos_, May 18 2015 *)
%o A026641 (PARI) a(n)=(-1)^n*sum(k=0,n,(-1)^k*binomial(n+k,k))
%o A026641 (PARI) /* same as in A092566 but use */
%o A026641 steps=[[1,0], [0,2], [1,1]]; /* _Joerg Arndt_, Jun 30 2011 */
%o A026641 (GAP) List([0..25],n->(-1)^n*Sum([0..n],k->(-1)^k*Binomial(n+k,k))); # _Muniru A Asiru_, Aug 06 2018
%o A026641 (Magma) [(-1)^n*(&+[(-1)^k*Binomial(n+k, k): k in [0..n]]): n in [0..30]]; // _G. C. Greubel_, Feb 12 2019
%o A026641 (Sage) [(-1)^n*sum((-1)^k*binomial(n+k, k) for k in (0..n)) for n in (0..30)] # _G. C. Greubel_, Feb 12 2019
%Y A026641 Cf. A101850, A120588, A158815.
%Y A026641 Cf. A091526 (k=-2), A072547 (k=-1), this sequence (k=0), A014300 (k=1), A014301 (k=2), A172025 (k=3), A172061 (k=4), A172062 (k=5), A172063 (k=6), A172064 (k=7), A172065 (k=8), A172066 (k=9), A172067 (k=10).
%K A026641 nonn,easy
%O A026641 0,3
%A A026641 _Clark Kimberling_