Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 8 down vote accepted

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

share|improve this answer
1  
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
    
@Chris: Thanks for the correction, I answered too hastily :) –  Zev Chonoles Jul 21 '11 at 11:05
    
Thank you very much! I surely haven't heard of these before. –  johnny Jul 21 '11 at 11:13
1  
@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. –  Jyrki Lahtonen Jul 21 '11 at 14:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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