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

Offset

0,3

Links

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

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.

Sequence in context: A367387 A185089 A180564 * A036250 A191491 A210345

Adjacent sequences: A113819 A113820 A113821 * A113823 A113824 A113825

Keyword

easy,nonn

Author

Franklin T. Adams-Watters, Jan 23 2006

Status

approved