# Number of ways to multiply elements with a non-associative operation

The question comes from considerations in algebra but it's probably more related to combinatorics.

Suppose I have a set of $n$ elements $(a, b, c, ...)$ and a possibly non-associative operation $*$ between these elements.

What I want to do is to count the number of elements I could obtain with this operation without interchanging the order of the elements.

Let me illustrate this. Here below the parentheses mean that the operation has higher priority (usual notation).

• For $a$ and $b$, there is only 1 way to multiply them: $a * b$.
• For $a$, $b$ and $c$, we can have 2: $a*(b*c)$ or $(a*b)*c$.
• For $a$, $b$, $c$ and $d$, there are 5: $(a*b)*(c*d)$, $((a*b)*c)*d$, $(a*(b*c))*d$, $a*((b*c)*d)$ or $a*(b*(c*d))$.

It seems that for $5$ elements we have $14$ possibilities unless I've made a mistake by enumerating them all by hand.

Would anyone have an idea on how many could we obtain for $n$ elements? I fail to detect a pattern here.

-

## 1 Answer

The number of ways of inserting parentheses into $n$ objects is given by the $n-1$'th Catalan number (the relationship is mentioned here): $$C_{n-1}=\frac{1}{n}\binom{2n-2}{n-1}.$$ For example, $C_4=\frac{1}{5}\binom{8}{4}=14$.

-

1
It's the $n-1$th Catalan number. $C_4=14$, $C_5=\frac{1}{6}\binom{10}{5}=42$. – Chris Eagle Jul 21 '11 at 11:04
@Chris: Thanks for the correction, I answered too hastily :) – Zev Chonoles♦ Jul 21 '11 at 11:05
Thank you very much! I surely haven't heard of these before. – johnny Jul 21 '11 at 11:13

1
– Jyrki Lahtonen Jul 21 '11 at 14:14
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 29, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9304543137550354, "perplexity_flag": "middle"}