6
$\begingroup$

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.

1 Answers 1

10

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

  • 1
    @Liudas: Neil Sloane's legendary [on-line encyclopedia of integer sequences](http://oeis.org/search?q=1%2C2%2C5%2C14&language=english&go=Search) gives you more information than you probably care to know:-) This property is second on the list.2011-07-21