|
| |
|
|
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
|
Table of n, a(n) for n=0..27.
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[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
|
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
|
| |
|
|
