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

1, 1, 2, 4, 9, 19, 43, 93, 207, 452, 997, 2176, 4776, 10418, 22781, 49674, 108421

Offset

1,3

Links

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

Gus Wiseman, The a(9) = 207 chain trees.

Example

The a(6) = 19 chain trees:
  (((((o)))))  ((((oo))))  (((ooo)))  ((oooo))  (ooooo)
               (((o)(o)))  ((o)(oo))  (o(ooo))
               (((o(o))))  ((o(oo)))  (oo(oo))
               ((o((o))))  ((oo(o)))  (ooo(o))
               (o(((o))))  (o((oo)))
                           (o(o)(o))
                           (o(o(o)))
                           (oo((o)))

Mathematica

submultisetQ[M_, N_]:=Or[Length[M]==0, MatchQ[{Sort[List@@M], Sort[List@@N]}, {{x_, Z___}, {___, x_, W___}}/; submultisetQ[{Z}, {W}]]];
chnplane[n_]:=If[n==1, {{}}, Join@@Table[Select[Tuples[chnplane/@c], And@@submultisetQ@@@Partition[#, 2, 1]&], {c, Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[chnplane[n]], {n, 10}]

Crossrefs

Cf. A000081, A000108, A001003, A005043, A007562, A118376, A143363, A316470, A319122, A319378, A319380, A319381.

Sequence in context: A301706 A289845 A101463 * A347011 A206301 A026776

Adjacent sequences: A319376 A319377 A319378 * A319380 A319381 A319382

Keyword

nonn,more

Author

Gus Wiseman, Sep 17 2018

Status

approved