The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 7
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS 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 LINKS 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. FORMULA 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 EXAMPLE 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) MAPLE 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); MATHEMATICA 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 == 1, a == 1, a == 1, a == 3, a == 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 *) CROSSREFS 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. Sequence in context: A238428 A232771 A129905 * A216878 A237670 A321227 Adjacent sequences: A143360 A143361 A143362 * A143364 A143365 A143366 KEYWORD nonn AUTHOR Emeric Deutsch, Aug 20 2008 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified March 29 15:46 EDT 2023. Contains 361599 sequences. (Running on oeis4.)