# Number of ways to multiply elements with a non-associative operation

The question comes from considerations in algebra but it's probably more related to combinatorics.

Suppose I have a set of $n$ elements $(a, b, c, ...)$ and a possibly non-associative operation $*$ between these elements.

What I want to do is to count the number of elements I could obtain with this operation without interchanging the order of the elements.

Let me illustrate this. Here below the parentheses mean that the operation has higher priority (usual notation).

• For $a$ and $b$, there is only 1 way to multiply them: $a * b$.
• For $a$, $b$ and $c$, we can have 2: $a*(b*c)$ or $(a*b)*c$.
• For $a$, $b$, $c$ and $d$, there are 5: $(a*b)*(c*d)$, $((a*b)*c)*d$, $(a*(b*c))*d$, $a*((b*c)*d)$ or $a*(b*(c*d))$.

It seems that for $5$ elements we have $14$ possibilities unless I've made a mistake by enumerating them all by hand.

Would anyone have an idea on how many could we obtain for $n$ elements? I fail to detect a pattern here.

-

The number of ways of inserting parentheses into $n$ objects is given by the $n-1$'th Catalan number (the relationship is mentioned here): $$C_{n-1}=\frac{1}{n}\binom{2n-2}{n-1}.$$ For example, $C_4=\frac{1}{5}\binom{8}{4}=14$.
It's the $n-1$th Catalan number. $C_4=14$, $C_5=\frac{1}{6}\binom{10}{5}=42$. –  Chris Eagle Jul 21 '11 at 11:04