We have a collection of objects $ P $ and an operator $(\star)$ such that for all of our objects: $\rho_i \star \rho_j = \rho_j \star \rho_i = \rho_k $

Where $\{\rho_i, \rho_j\, \rho_k \} \in P$, and $\{i, j, k\}$ may or may not be equal to each other.

Suppose we have 4 objects from $P$. How many different ways are there to operate on all of them with $(\star)$? I.E.

$(\rho_1 \star \rho_2) \star (\rho_3 \star \rho_4) $

$\rho_1 \star (\rho_2 \star (\rho_3 \star \rho_4)) $

... Etc.

What is the generalisation of this problem to $n$ such objects?


1 Answer 1


These products are in bijection with the unordered full binary tree with $n$ labeled leaves, of which there are $(2n-3)!!$ (where $(-1)!!=1$). See double factorial and OEIS sequence A001147.

You can see this by noting that removing the $n$-th element from a product generates each of the products of the remaining $n-1$ elements $2n-3$ times, once for each node of the corresponding tree at which the $n$-th element could be inserted.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .