A316522 Number of unlabeled rooted trees with n nodes where all terminal rooted subtrees are either constant or strict.

1, 1, 2, 4, 8, 15, 34, 71, 165, 381, 913, 2193, 5389, 13287, 33155, 83196, 210251, 533956, 1363146, 3494266, 8993164, 23225281

Offset

1,3

Links

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

Example

The a(6) = 15 rooted trees:
  (((((o)))))
  ((((oo))))
  (((o(o))))
  (((ooo)))
  ((o((o))))
  ((o(oo)))
  (((o)(o)))
  ((oooo))
  (o(((o))))
  (o((oo)))
  (o(o(o)))
  (o(ooo))
  ((o)((o)))
  ((o)(oo))
  (ooooo)
Missing from this list are:
  ((oo(o)))
  (oo((o)))
  (oo(oo))
  (o(o)(o))
  (ooo(o))

Mathematica

Clear[strut];
strut[n_]:=strut[n]=If[n==1, {{}}, Select[Join@@Function[c, Union[Sort/@Tuples[strut/@c]]]/@IntegerPartitions[n-1], Or[SameQ@@#, UnsameQ@@#]&]];
Table[Length[strut[n]], {n, 15}]

Crossrefs

Cf. A000081, A003238, A004111, A214577, A276625, A316521.

Sequence in context: A061030 A036661 A145671 * A317712 A108693 A371351

Adjacent sequences: A316519 A316520 A316521 * A316523 A316524 A316525

Keyword

nonn,more

Author

Gus Wiseman, Jul 05 2018

Extensions

a(16)-a(22) from Robert Price, Sep 16 2018

Status

approved