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

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


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.

Tags:

Combinatorics

Nonassociative Algebras

Related

Why does $\frac{|\sin\theta|}{2}<\frac{|\theta|}{2}<\frac{|\tan\theta|}{2}$ not imply that $1>\lim_{\theta\to 0}\frac{\sin\theta}{\theta}>1$? Proof that $\lim_{n\to\infty}\left(1+\frac{x^2}{n^2}\right)^{\frac{n}{2}}=1$ without L'Hospital Simplification of $\displaystyle{0 \binom{n}{0} + 2 \binom{n}{2} + 4 \binom{n}{4} + 6 \binom{n}{6} + \cdots}$ Probability of Exiting A Roundabout Banach-Alaoglu Theorem over spherically complete non-Archimedean fields $\sqrt{a+b} (\sqrt{3a-b}+\sqrt{3b-a})\leq4\sqrt{ab}$ Show that $\int_0^1 h(t)dt\geq\left(\int_0^1 f(t)dt \right)^a\left(\int_0^1 g(t)dt \right)^{1-a}$ Quadratic Euler sums $\sum _{n=1}^{\infty } \frac{(-1)^{n-1} \widetilde H(n)^3}{2 n+1}$ limit related to the Lambert function Integrating $\sin(x)x^2$ by parts, why do we only add $C$ at the end? Question about product of generating functions in a proof that for positive integer $n$, $\sum_{k=0}^n(-1)^k\binom nk\binom{2n-k}n=1$. Which is greater $\frac{13}{32}$ or $\ln \left(\frac{3}{2}\right)$

Recent Posts