|
|
A317787
|
|
Number of locally nonintersecting rooted trees with n nodes.
|
|
6
|
|
|
1, 1, 2, 4, 8, 18, 40, 95, 227, 557, 1382, 3485, 8865, 22790, 59022, 153972, 404066, 1066236, 2826885, 7527411, 20121154
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
An unlabeled rooted tree is locally nonintersecting if there is no common subbranch to all branches directly under any given node.
|
|
LINKS
|
|
|
EXAMPLE
|
The a(6) = 18 locally nonintersecting rooted trees:
(((((o)))))
((((oo))))
(((o(o))))
((o((o))))
(o(((o))))
((o)((o)))
(((ooo)))
((o(oo)))
((oo(o)))
(o((oo)))
(o(o(o)))
(oo((o)))
(o(o)(o))
((oooo))
(o(ooo))
(oo(oo))
(ooo(o))
(ooooo)
Missing from this list are (((o)(o))) and ((o)(oo)).
|
|
MATHEMATICA
|
rurt[n_]:=If[n==1, {{}}, Join@@Table[Select[Union[Sort/@Tuples[rurt/@ptn]], Or[Length[#]==1, Intersection@@#=={}]&], {ptn, IntegerPartitions[n-1]}]];
Table[Length[rurt[n]], {n, 10}]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|