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.

$\endgroup$
10
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ It's the $n-1$th Catalan number. $C_4=14$, $C_5=\frac{1}{6}\binom{10}{5}=42$. $\endgroup$ Jul 21 '11 at 11:04
  • $\begingroup$ @Chris: Thanks for the correction, I answered too hastily :) $\endgroup$ Jul 21 '11 at 11:05
  • $\begingroup$ Thank you very much! I surely haven't heard of these before. $\endgroup$
    – johnny
    Jul 21 '11 at 11:13
  • 1
    $\begingroup$ @Liudas: Neil Sloane's legendary on-line encyclopedia of integer sequences gives you more information than you probably care to know:-) This property is second on the list. $\endgroup$ Jul 21 '11 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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