|
|
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
a(n) is the number of parking functions of size n-1 avoiding the patterns 123, 132, and 213 . - Lara Pudwell, Apr 10 2023
|
|
LINKS
|
|
|
FORMULA
|
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
|
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[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 *)
|
|
CROSSREFS
|
For exactly one leaf directly under any node we have A006013.
Allowing lone children gives A319378.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|