A143362 -id:A143362 - cp's OEIS frontend

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

Emeric Deutsch

nonn

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

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

Cf. A059481, A026641, A143362, A143363.

[(1/2)*(&+[(-1)^(n-k)*Binomial(n+k-1,k): k in [0..n]]): n in [1..30]]; // G. C. Greubel, Jan 15 2018

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

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

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

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

A143363 Number of ordered trees with n edges and having no protected vertices. A protected vertex in an ordered tree is a vertex at least 2 edges away from its leaf descendants.

Original entry on oeis.org

1, 1, 1, 3, 6, 17, 43, 123, 343, 1004, 2938, 8791, 26456, 80597, 247091, 763507, 2372334, 7413119, 23271657, 73376140, 232238350, 737638868, 2350318688, 7510620143, 24064672921, 77294975952, 248832007318, 802737926643

Offset: 0

Emeric Deutsch, Aug 20 2008

nonn

The "no protected vertices" condition can be rephrased as "every non-leaf vertex has at least one leaf child". But a(n) is also the number of ordered trees with n edges in which every non-leaf vertex has at most one leaf child. - David Callan, Aug 22 2014
Also the number of locally non-intersecting ordered rooted trees with n edges, meaning every non-leaf subtree has empty intersection. The unordered version is A007562. - Gus Wiseman, Nov 19 2022
a(n) is the number of parking functions of size n-1 avoiding the patterns 123, 132, and 213 . - Lara Pudwell, Apr 10 2023
For n>0, a(n) is the number of ways to place non-intersecting diagonals in convex n+3-gon so as to create no triangles such that none of the dividing diagonals passes through a chosen vertex. (empirical observation) - Muhammed Sefa Saydam, Feb 14 2025 and Aug 05 2025

			From _Gus Wiseman_, Nov 19 2022: (Start)
The a(0) = 1 through a(4) = 6 trees with at least one leaf directly under any non-leaf node:
  o  (o)  (oo)  (ooo)   (oooo)
                ((o)o)  ((o)oo)
                (o(o))  ((oo)o)
                        (o(o)o)
                        (o(oo))
                        (oo(o))
The a(0) = 1 through a(4) = 6 trees with at most one leaf directly under any node:
  o  (o)  ((o))  ((o)o)   (((o))o)
                 (o(o))   (((o)o))
                 (((o)))  ((o)(o))
                          ((o(o)))
                          (o((o)))
                          ((((o))))
(End)

Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
Gi-Sang Cheon and Louis W. Shapiro, Protected points in ordered trees, Appl. Math. Letters, 21, 2008, 516-520.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.

Cf. A143362.
For exactly one leaf directly under any node we have A006013.
The unordered version is A007562, ranked by A316470.
Allowing lone children gives A319378.
A000108 counts ordered rooted trees, unordered A000081.
A358453 counts transitive ordered trees, unordered A290689.
A358460 counts locally disjoint ordered trees, unordered A316473.
Cf. A318185, A324756, A324767, A324840, A324844.

p:=z^2*G^3-2*z*G^2-2*z^2*G^2+3*z*G+G+z^2*G-1-2*z=0: G:=RootOf(p,G): Gser:= series(G,z=0,33): seq(coeff(Gser,z,n),n=0..28);

a[n_Integer] := a[n] = Round[SeriesCoefficient[2 (x + 1 - Sqrt[x^2 - x + 1] Cos[ArcTan[(3 x Sqrt[12 x^3 - 96 x^2 - 24 x + 15])/(2 x^3 - 30 x^2 - 3 x + 2)]/3])/(3 x), {x, 0, n}]]; Table[a[n], {n, 0, 20}] (* Vladimir Reshetnikov, Apr 10 2022 *)
RecurrenceTable[{25 (n + 5) (n + 6) a[n + 5] - 10 (n + 5) (5 n + 21) a[n + 4] - 2 (77 n^2 + 613 n + 1185) a[n + 3] + 2 (50 n^2 + 253 n + 312) a[n + 2] + 4 (2 n + 1) (7 n + 9) a[n + 1] - 4 n (2 n + 1) a[n] == 0, a[0] == 1, a[1] == 1, a[2] == 1, a[3] == 3, a[4] == 6}, a[n], {n, 0, 27}] (* Vladimir Reshetnikov, Apr 11 2022 *)
ait[n_]:=ait[n]=If[n==1,{{}},Join@@Table[Select[Tuples[ait/@c],MemberQ[#,{}]&],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[ait[n]],{n,15}] (* Gus Wiseman, Nov 19 2022 *)

a(n) = A143362(n,0) for n>=1.
G.f.: G=G(z) satisfies z^2*G^3-2z(1+z)G^2+(1+3z+z^2)G-(1+2z)=0.
G.f.: (x+1-sqrt(x^2-x+1)*cos(arctan((3*x*sqrt(12*x^3-96*x^2-24*x+15))/(2*x^3-30*x^2-3*x+2))/3))*2/(3*x). - Vladimir Reshetnikov, Apr 10 2022
Recurrence: 25*(n+5)*(n+6)*a(n+5) - 10*(n+5)*(5*n+21)*a(n+4) - 2*(77*n^2+613*n+1185)*a(n+3) + 2*(50*n^2+253*n+312)*a(n+2) + 4*(2*n+1)*(7*n+9)*a(n+1) - 4*n*(2*n+1)*a(n) = 0. - Vladimir Reshetnikov, Apr 11 2022
From Muhammed Sefa Saydam, Jul 12 2025: (Start)
a(n) =  Sum_{k=2..n+2} A046736(k) * A046736(n-k+3) , for n >= 0 and A046736(1) = 1.
a(n) = A049125(n) + Sum_{k=1..n-2} A049125(k) * A046736(n-k+2), for n >= 3.
a(n) = A049125(n) + Sum_{k=1..n-2} a(k) * a(n-k-1), for n >= 3. (End)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Formula