|
%I #43 Apr 11 2023 08:43:41
%S 1,3,11,41,154,582,2211,8437,32318,124202,478686,1849498,7161556,
%T 27784460,107980515,420300045,1638238710,6393535170,24980504010,
%U 97704407790,382509199020,1498824792660,5877754713870,23067328421826,90590960500524,356002519839652
%N Number of branches in all ordered trees with n edges.
%C Row sums of triangle A136535. - _Gary W. Adamson_, Jan 04 2008
%C The average of the n terms a(1),...,a(n) is C(n) = A000108(n), the n-th Catalan number. - _Franklin T. Adams-Watters_, May 20 2010
%C Binomial transform of A005717. - _Peter Luschny_, Jan 17 2012
%C a(n) is the number of parking functions of size n avoiding the patterns 213, 312, and 321. - _Lara Pudwell_, Apr 10 2023
%H Michael De Vlieger, <a href="/A076540/b076540.txt">Table of n, a(n) for n = 1..1664</a>
%H Ayomikun Adeniran and Lara Pudwell, <a href="https://doi.org/10.54550/ECA2023V3S3R17">Pattern avoidance in parking functions</a>, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
%H J. Riordan, <a href="http://dx.doi.org/10.1016/S0097-3165(75)80010-0">Enumeration of plane trees by branches and endpoints</a>, J. Combinat. Theory, Ser A, 19, 214-222, 1975.
%H Lin Yang and Shengliang Yang, <a href="https://doi.org/10.4208/jms.v56n1.23.01">Protected Branches in Ordered Trees</a>, J. Math. Study (2023) Vol. 56, No. 1, 1-17.
%F a(n) = (3*n^2-2*n+1)*binomial(2*n, n)/(2*(n+1)*(2*n-1)).
%F G.f.: (1-z)*(C-1)/sqrt(1-4*z), where C=(1-sqrt(1-4*z))/(2*z) is the Catalan function.
%F a(n) = binomial(2n-1, n-2) + binomial(2n-2, n-1). - _David Callan_, Nov 06 2003
%F a(n+1) = [x^n](1 + x + x^2)*(1 + x)^(2*n) = binomial(2*n,n) + binomial(2*n,n-1) + binomial(2*n,n-2). - _Peter Bala_, Jun 15 2015
%F D-finite with recurrence (n+1)*a(n) +(-7*n+1)*a(n-1) +2*(7*n-12)*a(n-2) +4*(-2*n+7)*a(n-3)=0. - _R. J. Mathar_, Jul 26 2022
%e a(3)=11 because the five ordered trees with 3 edges have 1+3+2+2+3 = 11 branches altogether.
%t Table[Binomial[2 n, n] + Binomial[2 n, n-1] + Binomial[2 n, n-2], {n, 0, 30}] (* _Vincenzo Librandi_, Jun 17 2015 *)
%o (PARI) vector(30, n, binomial(2*n-1,n-2)+binomial(2*n-2,n-1)) \\ _Michel Marcus_, Jun 17 2015
%o (Magma) [Binomial(2*n,n)+Binomial(2*n,n-1)+Binomial(2*n,n-2): n in [0..30]]; // _Vincenzo Librandi_, Jun 17 2015
%Y First differences of A001791. First differences are in A073663.
%Y Cf. A136535, A005717.
%K nonn,easy
%O 1,2
%A _Emeric Deutsch_, Oct 18 2002
|
