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

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