How many ways to write a commutative non-associative product of $n$ terms?

Question

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

Answer 1

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

Answer 2

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.