cp's OEIS Frontend

A014301 Number of internal nodes of even outdegree in all ordered rooted trees with n edges.

%I A014301 #80 Aug 04 2024 06:38:38
%S A014301 0,1,3,11,40,148,553,2083,7896,30086,115126,442118,1703052,6577474,
%T A014301 25461493,98759971,383751472,1493506534,5820778858,22714926826,
%U A014301 88745372992,347087585824,1358789148058,5324148664846,20878676356240,81937643449468,321786401450268
%N A014301 Number of internal nodes of even outdegree in all ordered rooted trees with n edges.
%C A014301 Number of protected vertices in all ordered rooted trees with n edges. A protected vertex in an ordered tree is a vertex at least 2 edges away from its leaf descendants. - _Emeric Deutsch_, Aug 20 2008
%C A014301 1,3,11,... gives the diagonal sums of A111418. Hankel transform of a(n) is A128834. Hankel transform of a(n+1) is A187340. - _Paul Barry_, Mar 08 2011
%C A014301 a(n) = A035317(2*n-1,n-1) for n > 0. - _Reinhard Zumkeller_, Jul 19 2012
%C A014301 Apparently the number of peaks in all Dyck paths of semilength n+1 that are the same height as the preceding peak. - _David Scambler_, Apr 22 2013
%C A014301 Define an infinite triangle by T(n,0)=A001045(n) (the first column) and T(r,c) = Sum_{k=c-1..r} T(k,c-1) (the sum of all the terms in the preceding column down to row r). Then T(n,n)=a(n+1). The triangle is 0; 1,1; 1,2,3; 3,5,8,11; 5,10,18,29,40; 11,21,39,68,108,148;... Example: T(5,2)=39=the sum of the terms in column 1 from T(1,1) to T(5,1), namely, 1+2+5+10+21. - _J. M. Bergot_, May 17 2013
%C A014301 Also for n>=1 the number of unimodal functions f:[n]->[n] with f(1)<>1 and f(i)<>f(i+1). a(4) = 11: [2,3,2,1], [2,3,4,1], [2,3,4,2], [2,3,4,3], [2,4,2,1], [2,4,3,1], [2,4,3,2], [3,4,2,1], [3,4,3,1], [3,4,3,2], [4,3,2,1]. - _Alois P. Heinz_, May 23 2013
%H A014301 G. C. Greubel, <a href="/A014301/b014301.txt">Table of n, a(n) for n = 1..1000</a>
%H A014301 Gi-Sang Cheon and Louis W. Shapiro, <a href="http://dx.doi.org/10.1016/j.aml.2007.07.001">Protected points in ordered trees,</a> Appl. Math. Letters, 21, 2008, 516-520.
%H A014301 Sergi Elizalde, <a href="https://arxiv.org/abs/2008.05669">Symmetric peaks and symmetric valleys in Dyck paths</a>, arXiv:2008.05669 [math.CO], 2020, Corollary 3.4.
%H A014301 Torleiv Kløve, <a href="http://www.ii.uib.no/publikasjoner/texrap/pdf/2008-376.pdf">Spheres of Permutations under the Infinity Norm - Permutations with limited displacement</a>, Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.
%H A014301 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A014301 a(n) = binomial(2*n-1, n)/3 - A000957(n)/3;
%F A014301 a(n) = (1/2)*Sum_{k=0..n} (-1)^(n-k)*binomial(n+k-1, k). - _Vladeta Jovovic_, Aug 28 2002
%F A014301 From _Emeric Deutsch_, Jan 26 2004: (Start)
%F A014301 G.f.: (1-2*z-sqrt(1-4*z))/(3*sqrt(1-4*z)-1+4*z).
%F A014301 a(n) = [A026641(n) - A026641(n-1)]/3 for n>1. (End)
%F A014301 a(n) = (1/2)*Sum_{j=0..floor(n/2)} binomial(2n-2j-2, n-2).
%F A014301 a(n) = Sum_{k=0..n} (-1)^(n-k)*C(n+k,k-1). - _Paul Barry_, Jul 18 2006
%F A014301 D-finite with recurrence: 2*n*a(n) +(-9*n+8)*a(n-1) +(3*n-16)*a(n-2) +2*(2*n-5)*a(n-3)=0. - _R. J. Mathar_, Dec 03 2012
%t A014301 Rest[CoefficientList[Series[(1-2*x-Sqrt[1-4*x])/(3*Sqrt[1-4*x]-1+4*x), {x, 0, 50}], x]] (* _G. C. Greubel_, Jan 15 2018 *)
%o A014301 (PARI) x='x+O('x^30); Vec((1-2*x-sqrt(1-4*x))/(3*sqrt(1-4*x)-1+4*x)) \\ _G. C. Greubel_, Jan 15 2018
%o A014301 (Magma) [(1/2)*(&+[(-1)^(n-k)*Binomial(n+k-1,k): k in [0..n]]): n in [1..30]]; // _G. C. Greubel_, Jan 15 2018
%o A014301 (Python)
%o A014301 from itertools import count, islice
%o A014301 def A014301_gen(): # generator of terms
%o A014301     yield from (0,1)
%o A014301     a, b, c = 0, 3, 1
%o A014301     for n in count(1):
%o A014301         yield ((b:=b*((n<<1)+3<<1)//(n+2))-(a:=(c:=c*((n<<2)+2)//(n+2))-a>>1))//3
%o A014301 A014301_list = list(islice(A014301_gen(),20)) # _Chai Wah Wu_, Apr 27 2023
%Y A014301 Cf. A059481, A026641, A143362, A143363.
%K A014301 nonn
%O A014301 1,3
%A A014301 _Emeric Deutsch_