How many ways to write a commutative non-associative product of $n$ terms? The Catalan numbers give the number of ways to write a non-commutative non-associative product of $n$ terms, as $C_{n-1}\cdot n!=\frac{(2n-2)!}{(n-1)!}$. For example, there are $C_{3-1}\cdot3!=12$ ways to write a product of $3$ terms:
$$(ab)c,\;(ac)b,\;(ba)c,\;(bc)a,\;(ca)b,\;(cb)a,\\a(bc),\;a(cb),\;b(ac),\;b(ca),\;c(ab),\;c(ba).$$
What if the multiplication is commutative? Then we have $(ba)c=(ab)c=c(ab)$ and so on. How many distinct products can we make?
Here are the first few numbers.
$$a;$$
$N_1=1$.
$$ab;$$
$N_2=1$.
$$(ab)c,\;(ac)b,\;(bc)a;$$
$N_3=3$.
$$((ab)c)d,\;((ab)d)c,\;((ac)d)b,\;((bc)d)a,\;(ab)(cd),\\((ac)b)d,\;((ad)b)c,\;((ad)c)b,\;((bd)c)a,\;(ac)(bd),\\((bc)a)d,\;((bd)a)c,\;((cd)a)b,\;((cd)b)a,\;(ad)(bc);$$
$N_4=15$.
 A: There are $n!C_{n-1}=\frac{n!}n\binom{2n-2}{n-1}=\frac{(2n-2)!}{(n-1)!}$ products if the operation is neither associative nor commutative. There are $n-1$ individual products, and each can be ordered in $2$ ways, so if the operation is commutative, this figure overcounts by a factor of $2^{n-1}$. And
$$\frac{(2n-2)!}{2^{n-1}(n-1)!}=\frac{2^{n-1}(n-1)!(2n-3)!!}{2^{n-1}(n-1)!}=(2n-3)!!\;,$$
so $N_n=(2n-3)!!$.
A: Here is another answer, just in case you'd like to see a direct derivation of the formula $N_n=(2n-3)!!$ without going through Catalan numbers. The presentation will be very informal, because writing it up more formally would be painful. Namely, I want to try and explain why
$$N_n=(2n-3)N_{n-1}\text{ for }n\ge2$$
or, equivalently, why
$$N_{n+1}=(2n-1)N_n\text{ for }n\ge1.$$
The reason is that forming the product of $n$ quantities by binary multiplication involves a total of $2n-1$ quantities: the $n$ given quantities and the result of each of the $n-1$ multiplications. Therefore there are $2n-1$ different places where a new quantity can be multiplied in. (If multiplication were noncommutative we would have to double that because the new factor could be multiplied on either side.)
Fo example, say $n=4$ and we have the product $(ab)(cd)$. The $7$ places where a new factor $e$ could be multiplied in are
$$a,\ b,\ c,\ d,\ ab,\ cd,\ (ab)(cd)$$
leading to
$$((ae)b)(cd),\ (a(be))(cd),\ (ab)((ce)d),\ (ab)(c(de)),\ ((ab)e)(cd),\ (ab)((cd)e),\ ((ab)(cd))e.$$
In this way we see that $N_5=7N_4=105$.
The same reasoning leads to the recurrence
$$a_{n+1}=(4n-2)a_n$$
for the number of ways to form a non-commutative non-associative product of $n$ factors, and this is another way to derive the Catalan numbers.
