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

0, 1, 3, 11, 40, 148, 553, 2083, 7896, 30086, 115126, 442118, 1703052, 6577474, 25461493, 98759971, 383751472, 1493506534, 5820778858, 22714926826, 88745372992, 347087585824, 1358789148058, 5324148664846, 20878676356240, 81937643449468, 321786401450268

Offset: 1

Author

Emeric Deutsch

Keywords

• nonn

Comments

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

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

a(n) = A035317(2*n-1,n-1) for n > 0. - Reinhard Zumkeller, Jul 19 2012

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

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

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

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• Gi-Sang Cheon and Louis W. Shapiro, Protected points in ordered trees, Appl. Math. Letters, 21, 2008, 516-520.
• Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020, Corollary 3.4.
• Torleiv Kløve, Spheres of Permutations under the Infinity Norm - Permutations with limited displacement, Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A059481, A026641, A143362, A143363.

Programs

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

Mathematica

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 *)

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

Python

from itertools import count, islice
def A014301_gen(): # generator of terms
    yield from (0,1)
    a, b, c = 0, 3, 1
    for n in count(1):
        yield ((b:=b*((n<<1)+3<<1)//(n+2))-(a:=(c:=c*((n<<2)+2)//(n+2))-a>>1))//3
A014301_list = list(islice(A014301_gen(),20)) # Chai Wah Wu, Apr 27 2023

Formula

a(n) = binomial(2*n-1, n)/3 - A000957(n)/3;

a(n) = (1/2)*Sum_{k=0..n} (-1)^(n-k)*binomial(n+k-1, k). - Vladeta Jovovic, Aug 28 2002

From Emeric Deutsch, Jan 26 2004: (Start)

G.f.: (1-2*z-sqrt(1-4*z))/(3*sqrt(1-4*z)-1+4*z).

a(n) = [A026641(n) - A026641(n-1)]/3 for n>1. (End)

a(n) = (1/2)*Sum_{j=0..floor(n/2)} binomial(2n-2j-2, n-2).

a(n) = Sum_{k=0..n} (-1)^(n-k)*C(n+k,k-1). - Paul Barry, Jul 18 2006

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