# Counting nested integer partitions

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

-

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

-