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 ?


2 Answers 2


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


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .