login
Number of unlabeled rooted trees with n nodes where the branches of no non-leaf branch of any terminal subtree form a submultiset of the branches of the same subtree.
17

%I #5 Mar 19 2019 07:15:13

%S 1,1,2,3,7,13,32,71,170,406,1002,2469,6204,15644,39871,102116,263325,

%T 682079,1775600,4640220

%N Number of unlabeled rooted trees with n nodes where the branches of no non-leaf branch of any terminal subtree form a submultiset of the branches of the same subtree.

%e The a(1) = 1 through a(6) = 13 rooted trees:

%e o (o) (oo) (ooo) (oooo) (ooooo)

%e ((o)) ((oo)) ((ooo)) ((oooo))

%e (((o))) (o(oo)) (o(ooo))

%e (((oo))) (((ooo)))

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

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

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

%e (oo((o)))

%e ((((oo))))

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

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

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

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

%t submultQ[cap_,fat_]:=And@@Function[i,Count[fat,i]>=Count[cap,i]]/@Union[List@@cap];

%t rallt[n_]:=Select[Union[Sort/@Join@@(Tuples[rallt/@#]&/@IntegerPartitions[n-1])],And@@Table[!submultQ[b,#],{b,DeleteCases[#,{}]}]&];

%t Table[Length[rallt[n]],{n,10}]

%Y The Matula-Goebel numbers of these trees are given by A324845.

%Y Cf. A000081, A290689, A306844, A318185.

%Y Cf. A324694, A324738, A324744, A324749, A324754, A324759, A324765, A324768, A324838, A324843, A324846, A324847, A324848, A324849.

%K nonn

%O 1,3

%A _Gus Wiseman_, Mar 18 2019