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.

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}}}

Links

Table of n, a(n) for n=1..20.

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}]

Crossrefs

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

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

Sequence in context: A169949 A261984 A100321 * A219751 A121133 A011952

Adjacent sequences: A324836 A324837 A324838 * A324840 A324841 A324842

Keyword

nonn,more

Author

Gus Wiseman, Mar 18 2019

Status

approved