|
|
A331680
|
|
Number of lone-child-avoiding locally disjoint unlabeled rooted trees with n vertices.
|
|
12
|
|
|
1, 0, 1, 1, 2, 3, 6, 9, 16, 26, 45, 72, 124, 201, 341, 561, 947, 1571, 2651, 4434, 7496, 12631, 21423, 36332, 61910, 105641, 180924, 310548, 534713, 923047
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
COMMENTS
|
A rooted tree is locally disjoint if no child of any vertex has branches overlapping the branches of any other unequal child of the same vertex. Lone-child-avoiding means there are no unary branchings.
|
|
LINKS
|
|
|
EXAMPLE
|
The a(1) = 1 through a(9) = 16 trees (empty column indicated by dot):
o . (oo) (ooo) (oooo) (ooooo) (oooooo) (ooooooo) (oooooooo)
(o(oo)) (o(ooo)) (o(oooo)) (o(ooooo)) (o(oooooo))
(oo(oo)) (oo(ooo)) (oo(oooo)) (oo(ooooo))
(ooo(oo)) (ooo(ooo)) (ooo(oooo))
((oo)(oo)) (oooo(oo)) (oooo(ooo))
(o(o(oo))) (o(o(ooo))) (ooooo(oo))
(o(oo)(oo)) ((ooo)(ooo))
(o(oo(oo))) (o(o(oooo)))
(oo(o(oo))) (o(oo(ooo)))
(o(ooo(oo)))
(oo(o(ooo)))
(oo(oo)(oo))
(oo(oo(oo)))
(ooo(o(oo)))
(o((oo)(oo)))
(o(o(o(oo))))
|
|
MATHEMATICA
|
disjointQ[u_]:=Apply[And, Outer[#1==#2||Intersection[#1, #2]=={}&, u, u, 1], {0, 1}];
strut[n_]:=If[n==1, {{}}, Select[Join@@Function[c, Union[Sort/@Tuples[strut/@c]]]/@Rest[IntegerPartitions[n-1]], disjointQ]];
Table[Length[strut[n]], {n, 10}]
|
|
CROSSREFS
|
The Matula-Goebel numbers of these trees are A331871.
The non-locally disjoint version is A001678.
These trees counted by number of leaves are A316697.
The semi-lone-child-avoiding version is A331872.
Cf. A000081, A000669, A005804, A060356, A141268, A300660, A316471, A316473, A316694, A316495, A319312, A330465, A331679, A331681, A331683.
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|