Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question

2 Answers 2

up vote 8 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.