Find the distinct ways for this binary operation

Question

Let ∗ be a non-associative binary operation defined on a set . For 1, 2, … , ∈ , how can I find the number of distinct ways of performing the operation 1 ∗ 2 ∗ ⋯ ∗ ?

I tried to enumerate it as 1 ∗ (2 ∗ ⋯ ∗ n), 1 ∗ 2 ∗ (x3 * ⋯ ∗ n) but could not really come up with a solution.

Answer 1

Let $S_n$ be the number you want.

We get:

$S_{n+1}=\sum\limits_{k=1}^{n-1} S_kS_{n-k}$. and $S_2=1$.

You can identify this as the catalan recurrence, so the answer is $\binom{2n-2}{n-1}/n$.