We have a sequence of integers $x_1, ..., x_n$. How many different operations can we make by adding parentheses ?
For instance
With $1, 2$ we can make :
- $1 \oplus 2$
With $1, 2, 3$ we can make :
- $(1 \oplus 2) \oplus 3$
- $1 \oplus (2 \oplus 3)$
With $1, 2, 3, 4$ we can make :
- $((1\oplus 2)\oplus 3)\oplus 4$
- $(1\oplus 2)\oplus (3\oplus 4)$
- $1\oplus (2\oplus (3\oplus 4))$
- $1\oplus ((2\oplus 3)\oplus 4)$
- $(1\oplus (2\oplus 3))\oplus 4$
Where $\oplus$ is an arbitrary binary associative operator. I think it's related to how many structurally different binary trees we can make with $n$ leaves.
These are the Catalan numbers. There are $\frac 1{n+1}{2n \choose n}$ ways to make a properly matched string of $n$ pairs of parentheses. You are looking for $C_{n-1}$ because each pair of parentheses is an operator and you have $n-1$ operators. This is the second example on the Wikipedia page. They are given in OEIS A000108 and start $1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670$