login
A319380
Number of plane trees with n nodes where the sequence of branches directly under any given node is a chain of distinct multisets.
4
1, 1, 1, 2, 3, 5, 9, 17, 30, 53, 94, 169, 303, 543, 968, 1728, 3080, 5491, 9776, 17415, 31008
OFFSET
1,4
EXAMPLE
The a(8) = 17 locally identity chain 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)))
MATHEMATICA
submultisetQ[M_, N_]:=Or[Length[M]==0, MatchQ[{Sort[List@@M], Sort[List@@N]}, {{x_, Z___}, {___, x_, W___}}/; submultisetQ[{Z}, {W}]]];
idchnplane[n_]:=If[n==1, {{}}, Join@@Table[Select[Tuples[idchnplane/@c], And[UnsameQ@@#, And@@submultisetQ@@@Partition[#, 2, 1]]&], {c, Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[idchnplane[n]], {n, 10}]
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Sep 17 2018
STATUS
approved