A113822 - OEIS

A113822

Number of binary trees of weight n where leaves have positive integer weights, where the order of subtrees is insignificant. Commutative non-associative version of partitions of n.

1, 1, 2, 3, 7, 14, 35, 85, 226, 600, 1658, 4622, 13141, 37699, 109419, 320017, 943329, 2797788, 8346030, 25019401, 75340824, 227777899, 691146578, 2104028507, 6424449318, 19670277332, 60378290912, 185763773723, 572764664975

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

OFFSET

0,3

LINKS

Table of n, a(n) for n=0..28.

Chloe E. Shiff and Noah A. Rosenberg, Enumeration of rooted binary perfect phylogenies, arXiv:2410.14915 [q-bio.PE], 2024. See pp. 5, 9, 17.

FORMULA

a(2n) = 1 + C(a(n)+1, 2) + sum_{k=1}^{n/2-1} a(k)*a(2n-k). a(2n+1) = 1 + sum_{k=1}^{(n-1)/2} a(k)*a(2n+1-k), with a(0)=0.

EXAMPLE

For a(4)=7, we have the following 7 sums: 4, 3+1, 2+2, (2+1)+1, (1+1)+2, ((1+1)+1)+1, (1+1)+(1+1).

CROSSREFS

Cf. A007317, A000041.