%I #34 Apr 11 2023 07:20:34
%S 1,1,1,3,6,17,43,123,343,1004,2938,8791,26456,80597,247091,763507,
%T 2372334,7413119,23271657,73376140,232238350,737638868,2350318688,
%U 7510620143,24064672921,77294975952,248832007318,802737926643
%N 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.
%C 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
%C 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
%C a(n) is the number of parking functions of size n-1 avoiding the patterns 123, 132, and 213 . - _Lara Pudwell_, Apr 10 2023
%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 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 Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, MSc Thesis, Reykjavik Univ., May 2016.
%F a(n) = A143362(n,0) for n>=1.
%F G.f.: G=G(z) satisfies z^2*G^3-2z(1+z)G^2+(1+3z+z^2)G-(1+2z)=0.
%F 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
%F 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
%e From _Gus Wiseman_, Nov 19 2022: (Start)
%e The a(0) = 1 through a(4) = 6 trees with at least one leaf directly under any non-leaf node:
%e o (o) (oo) (ooo) (oooo)
%e ((o)o) ((o)oo)
%e (o(o)) ((oo)o)
%e (o(o)o)
%e (o(oo))
%e (oo(o))
%e The a(0) = 1 through a(4) = 6 trees with at most one leaf directly under any node:
%e o (o) ((o)) ((o)o) (((o))o)
%e (o(o)) (((o)o))
%e (((o))) ((o)(o))
%e ((o(o)))
%e (o((o)))
%e ((((o))))
%e (End)
%p 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);
%t 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 *)
%t 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 *)
%t ait[n_]:=ait[n]=If[n==1,{{}},Join@@Table[Select[Tuples[ait/@c],MemberQ[#,{}]&],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
%t Table[Length[ait[n]],{n,15}] (* _Gus Wiseman_, Nov 19 2022 *)
%Y Cf. A143362.
%Y For exactly one leaf directly under any node we have A006013.
%Y The unordered version is A007562, ranked by A316470.
%Y Allowing lone children gives A319378.
%Y A000108 counts ordered rooted trees, unordered A000081.
%Y A358453 counts transitive ordered trees, unordered A290689.
%Y A358460 counts locally disjoint ordered trees, unordered A316473.
%Y Cf. A318185, A324756, A324767, A324840, A324844.
%K nonn
%O 0,4
%A _Emeric Deutsch_, Aug 20 2008