A316473 Number of locally disjoint rooted trees with n nodes, meaning no branch overlaps any other (unequal) branch of the same root.
1, 1, 2, 4, 9, 19, 44, 99, 233, 554, 1346, 3300, 8219, 20635, 52300, 133488, 343033, 886360, 2302133, 6005835
Offset: 1
Examples
The a(5) = 9 locally disjoint rooted trees: ((((o)))) (((oo))) ((o(o))) ((ooo)) (o((o))) (o(oo)) ((o)(o)) (oo(o)) (oooo)
Links
- Gus Wiseman, The a(6) = 19 locally disjoint rooted trees.
Programs
-
Mathematica
strut[n_]:=strut[n]=If[n===1,{{}},Select[Join@@Function[c,Union[Sort/@Tuples[strut/@c]]]/@IntegerPartitions[n-1],Select[Tuples[#,2],UnsameQ@@#&&(Intersection@@#=!={})&]=={}&]]; Table[Length[strut[n]],{n,15}]
Extensions
a(20) from Jinyuan Wang, Jun 20 2020