A301344 - OEIS

A301344

Regular triangle where T(n,k) is the number of semi-binary rooted trees with n nodes and k leaves.

1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 4, 1, 0, 0, 1, 6, 4, 0, 0, 0, 1, 9, 11, 2, 0, 0, 0, 1, 12, 24, 9, 0, 0, 0, 0, 1, 16, 46, 32, 3, 0, 0, 0, 0, 1, 20, 80, 86, 20, 0, 0, 0, 0, 0, 1, 25, 130, 203, 86, 6, 0, 0, 0, 0, 0, 1, 30, 200, 423, 283, 46, 0, 0, 0, 0, 0, 0, 1, 36, 295, 816, 786, 234, 11, 0, 0, 0, 0

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,8

COMMENTS

A rooted tree is semi-binary if all outdegrees are <= 2. The number of semi-binary trees with n nodes is equal to the number of binary trees with n+1 leaves; see A001190.

LINKS

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

EXAMPLE

Triangle begins:

1 0

1 1 0

1 2 0 0

1 4 1 0 0

1 6 4 0 0 0

1 9 11 2 0 0 0

1 12 24 9 0 0 0 0

1 16 46 32 3 0 0 0 0

1 20 80 86 20 0 0 0 0 0

1 25 130 203 86 6 0 0 0 0 0

The T(6,3) = 4 semi-binary rooted trees: ((o(oo))), (o((oo))), (o(o(o))), ((o)(oo)).

MATHEMATICA

rbt[n_]:=rbt[n]=If[n===1, {{}}, Join@@Function[c, Union[Sort/@Tuples[rbt/@c]]]/@Select[IntegerPartitions[n-1], Length[#]<=2&]];

Table[Length[Select[rbt[n], Count[#, {}, {-2}]===k&]], {n, 15}, {k, n}]

CROSSREFS

Cf. A000081, A000598, A001190, A001678, A003238, A004111, A055277, A111299, A273873, A290689, A291636, A292050, A298118, A298204, A298422, A298426, A301342, A301343, A301345.

Sequence in context: A309023 A353429 A137585 * A301579 A072458 A256282

Adjacent sequences: A301341 A301342 A301343 * A301345 A301346 A301347

KEYWORD

nonn,tabl

AUTHOR

Gus Wiseman, Mar 19 2018

STATUS

approved