Number of ways to group $n$ operands

Question

My textbook claims there are...

• Two ways to group $3$ operands, i.e. $(a_1+a_2)+a_3$ and $a_1+(a_2+a_3)$;
• Five ways to group $4$ operands, i.e....
  1. $((a_1+a_2)+a_3)+a_4$,
  2. $(a_1+(a_2+a_3))+a_4$,
  3. $a_1+((a_2+a_3)+a_4)$,
  4. $a_1+(a_2+(a_3+a_4))$,
  5. $(a_1+a_2)+(a_3+a_4)$;
• and $14$ ways to group $5$ operands,

where each grouping is a binomial (binary operation), and there are no superfluous groupings. How can one think about and/or solve for $n$ operands?

Answer 1

We can recursively construct the parenthesis structure using strong induction.

We know that for two arguments, there is exactly one possible grouping--this is the base case. As we add an argument, we can construct the different ways we can group. Lets call the number of groups for $n$ arguments as $G_n$ (so we know that $G_2 = 1$, $G_3 = 2$, $G_4 = 5$, $G_5 = 14$--at the least)

\begin{align*} \left(a_1...a_{n - 1}\right) + a_n && \text{$G_{n - 1}$} \\ \left(a_1...a_{n - 2}\right) + \left(a_{n - 1} + a_n\right) && G_{n - 2}G_2 \\ \left(a_1...a_{n - 3}\right) + \left(a_{n - 2} + a_{n - 1} + a_n\right) && G_{n - 3}G_3 \end{align*}

You probably see a pattern here: $G_n = \sum\limits_1^{n - 1}G_iG_{n - i}$ (where we assume $G_1 = 1$). So we see:

\begin{align*} &G_3 = G_1G_2 + G_2G_1 = 1 + 1 &= 2 \\ &G_4 = G_1G_3 + G_2G_2 + G_3G_1 = 2 + 1 + 2 &= 5 \\ &G_5 = G_1G_4 + G_2G_3 + G_3G_2 + G_4G_1 = 5 + 2 + 2 + 5 &= 14 \\ &G_6 = G_1G_5 + G_2G_4 + G_3G_3 + G_4G_2 + G_5G_1 = 14 + 5 + 4 + 5 + 14 &= 42 \end{align*}

This looks very similar to the binomial expansion so I would expect there to be a combinatorial solution.