login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #4 Mar 19 2019 07:14:41

%S 1,0,1,1,2,3,8,16,35,74,166,367,831,1878,4299,9857,22775,52777,122957,

%T 287337

%N 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.

%C An unlabeled rooted tree is an identity tree if there are no repeated branches directly under the same root.

%C 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 = {}):

%C {{{{{{o}}}}}}

%C {{{{o,{o}}}}}

%C {{{o,{{o}}}}}

%C {{o,{{{o}}}}}

%C {{o,{o,{o}}}}

%C {{{o},{{o}}}}

%C {{o},{{{o}}}}

%C {{o},{o,{o}}}

%e The a(1) = 1 through a(8) = 16 rooted identity trees:

%e o ((o)) (((o))) ((o(o))) (((o(o)))) ((o)(o(o))) (((o))(o(o)))

%e ((((o)))) ((o((o)))) ((o(o(o)))) (((o)(o(o))))

%e (((((o))))) ((((o(o))))) (((o(o(o)))))

%e (((o)((o)))) ((o)((o(o))))

%e (((o((o))))) ((o)(o((o))))

%e ((o)(((o)))) ((o((o(o)))))

%e ((o(((o))))) ((o(o)((o))))

%e ((((((o)))))) ((o(o((o)))))

%e (((((o(o))))))

%e ((((o)((o)))))

%e ((((o((o))))))

%e (((o)(((o)))))

%e (((o(((o))))))

%e ((o)((((o)))))

%e ((o((((o))))))

%e (((((((o)))))))

%t idall[n_]:=If[n==1,{{}},Select[Union[Sort/@Join@@(Tuples[idall/@#]&/@IntegerPartitions[n-1])],UnsameQ@@#&]];

%t Table[Length[Select[idall[n],And@@Table[!SubsetQ[#,b],{b,#}]&]],{n,10}]

%Y Cf. A000081, A290760, A304360, A306844, A317787.

%Y Cf. A324694, A324696, A324704, A324738, A324744, A324758, A324759, A324767, A324770, A324771, A324838, A324840, A324844, A324846.

%K nonn,more

%O 1,5

%A _Gus Wiseman_, Mar 18 2019