A319380 Number of plane trees with n nodes where the sequence of branches directly under any given node is a chain of distinct multisets.

1, 1, 1, 2, 3, 5, 9, 17, 30, 53, 94, 169, 303, 543, 968, 1728, 3080, 5491, 9776, 17415, 31008

Offset

1,4

Links

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

Gus Wiseman, The a(12) = 169 identity chain trees.

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

Crossrefs

Cf. A000081, A000108, A001003, A005043, A007562, A118376, A316470, A319122, A319379, A319381.

Sequence in context: A339512 A326023 A326117 * A213709 A054187 A014743

Adjacent sequences: A319377 A319378 A319379 * A319381 A319382 A319383

Keyword

nonn,more

Author

Gus Wiseman, Sep 17 2018

Status

approved