|
%I #74 Apr 27 2023 15:03:05
%S 0,1,3,11,40,148,553,2083,7896,30086,115126,442118,1703052,6577474,
%T 25461493,98759971,383751472,1493506534,5820778858,22714926826,
%U 88745372992,347087585824,1358789148058,5324148664846,20878676356240,81937643449468,321786401450268
%N Number of internal nodes of even outdegree in all ordered rooted trees with n edges.
%C 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 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 a(n) = A035317(2*n-1,n-1) for n > 0. - _Reinhard Zumkeller_, Jul 19 2012
%C 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 Define an infinite triangle by T(n,0)=A001045(n) (the first column) and T(r,c) = sum_{k=c-1, c,..,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 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 G. C. Greubel, <a href="/A014301/b014301.txt">Table of n, a(n) for n = 1..1000</a>
%H 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 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 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 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F a(n) = binomial(2*n-1, n)/3 - A000957(n)/3;
%F a(n) = (1/2)*Sum_{k=0..n} (-1)^(n-k)*binomial(n+k-1, k). - _Vladeta Jovovic_, Aug 28 2002
%F From _Emeric Deutsch_, Jan 26 2004: (Start)
%F G.f.: (1-2*z-sqrt(1-4*z))/(3*sqrt(1-4*z)-1+4*z).
%F a(n) = [A026641(n) - A026641(n-1)]/3 for n>1. (End)
%F a(n) = (1/2)*Sum_{j=0..floor(n/2)} binomial(2n-2j-2, n-2).
%F a(n) = Sum_{k=0..n} (-1)^(n-k)*C(n+k,k-1). - _Paul Barry_, Jul 18 2006
%F 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 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 (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 (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 (Python)
%o from itertools import count, islice
%o def A014301_gen(): # generator of terms
%o yield from (0,1)
%o a, b, c = 0, 3, 1
%o for n in count(1):
%o yield ((b:=b*((n<<1)+3<<1)//(n+2))-(a:=(c:=c*((n<<2)+2)//(n+2))-a>>1))//3
%o A014301_list = list(islice(A014301_gen(),20)) # _Chai Wah Wu_, Apr 27 2023
%Y Cf. A059481, A026641, A143362, A143363.
%K nonn
%O 1,3
%A _Emeric Deutsch_
|
