If $G$ be a set and $f:G \times G \longmapsto G$ be a binary operation on G then $f$ is called associative on $G$ if $a(bc)=(ab)c$ for all a,b in $G$.

My question is that for a finite number of elements $a_1,a_2,...,a_n$ how many ways are there to operate the element for a particular ordering of them .

Let's call a function $N(m)$ for $m$ elements defined by the above condition . Recall that by associative law $a_1(a_2a_3)$ and$(a_1a_2)a_3$ are same and this are the only ways to operate elemets$a_1a_2a_3$ so $N(3)=2$

Now consider four elements $a_1,a_2,a_3,a_4$.The only way to operate this elements in this order is $((a_1a_2)a_3)a_4$,$(a_1a_2)(a_3a_4)$,$(a_1(a_2a_3))a_4$,$a_1((a_2a_3)a_4)$ and $a_1(a_2(a_3a_4))$ thus $N(4)=5$

So can we generalize thus process to get the value $N(m)$ in general?


You want to count certain binary trees. The result is given by Catalan numbers. With $n$ denoting that number of leaves, this can be expressed as$$\frac1{n}{2(n-1)\choose n-1} =\frac{(2n-2)!}{(n-1)!\,n!}.$$

For example, $n=3$ leads to $\frac{4!}{3!2!}=2$ and $n=4$ leads to $\frac{6!}{4!3!}=5$.


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.