login
A324839
Number of unlabeled rooted identity trees with n nodes where the branches of no branch of the root form a subset of the branches of the root.
4
1, 0, 1, 1, 2, 3, 8, 16, 35, 74, 166, 367, 831, 1878, 4299, 9857, 22775, 52777, 122957, 287337
OFFSET
1,5
COMMENTS
An unlabeled rooted tree is an identity tree if there are no repeated branches directly under the same root.
Also the number of finitary sets with n brackets where no element is also a subset. For example, the a(7) = 8 sets are (o = {}):
{{{{{{o}}}}}}
{{{{o,{o}}}}}
{{{o,{{o}}}}}
{{o,{{{o}}}}}
{{o,{o,{o}}}}
{{{o},{{o}}}}
{{o},{{{o}}}}
{{o},{o,{o}}}
EXAMPLE
The a(1) = 1 through a(8) = 16 rooted identity trees:
o ((o)) (((o))) ((o(o))) (((o(o)))) ((o)(o(o))) (((o))(o(o)))
((((o)))) ((o((o)))) ((o(o(o)))) (((o)(o(o))))
(((((o))))) ((((o(o))))) (((o(o(o)))))
(((o)((o)))) ((o)((o(o))))
(((o((o))))) ((o)(o((o))))
((o)(((o)))) ((o((o(o)))))
((o(((o))))) ((o(o)((o))))
((((((o)))))) ((o(o((o)))))
(((((o(o))))))
((((o)((o)))))
((((o((o))))))
(((o)(((o)))))
(((o(((o))))))
((o)((((o)))))
((o((((o))))))
(((((((o)))))))
MATHEMATICA
idall[n_]:=If[n==1, {{}}, Select[Union[Sort/@Join@@(Tuples[idall/@#]&/@IntegerPartitions[n-1])], UnsameQ@@#&]];
Table[Length[Select[idall[n], And@@Table[!SubsetQ[#, b], {b, #}]&]], {n, 10}]
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Mar 18 2019
STATUS
approved