Counting nested integer partitions

Question

One partition of 8 is 5 + 3, but if we then partition each of the 5 and 3 we could get (3+2) + (2+1), and then partition again to get ((2+1)+(1+1)) + ((1+1)+1) and finally (((1+1)+1)+(1+1)) + ((1+1)+1). 5+3 could also be expanded as (4+1)+(2+1), then ((2+2)+1)+((1+1)+1), then (((1+1)+(1+1))+1)+((1+1)+1).

This question is about viewing "+" as a binary operation , so 1+1+1+1 would have to written as either (1+1)+(1+1) or ((1+1)+1)+1.

Every partition can be written as a such nested partition of 1s. It is still order independent, but associative dependent.

For a given number $n$, how many associative dependent binary-operation nested partitions of 1s are there of $n$ ?

What is known about this function ?

Answer 1

Every nested partition defines a full binary tree (all nodes have degree 0 or 2) with $n$ leaves (the 1s) and $n-1$ internal nodes (the binary operators). The number of different full binary trees with $n+1$ leaves is related to the $n$-th Catalan Number. This is

$C_n = \frac{1}{n+1} {2n \choose n}$.

The Catalan Numbers occur in many counting problems (see the wikipedia article for more details).

Answer 2

Marc's certainly correct that the Catalan numbers count full binary trees. But while every nested partition defines a full binary tree, not every full binary tree corresponds to a nested partition.

Smallest example: 1+(1+1) would come from 1+2, not a partition of 3 following the standard convention of listing parts in non-increasing order. As in Roy's example, the only two binary-operation nested partitions of four 1's are (1+1)+(1+1) from 2+2 or ((1+1)+1)+1 from 3+1.

Working out more terms, the number of such sums (from 1 to 10) is 1, 1, 1, 2, 3, 6, 11, 24, 47, 103. This is http://oeis.org/A000992, and Callan's description of restricted binary trees there matches this context. The sequence has a convolution recurrence similar to Catalan numbers, only going "half-way." (If Roy's question were about compositions [partitions where "order matters"], allowing 1+2 and then 1+(1+1), the recurrence formula would go the whole way and the answer would be the Catalan numbers.)