# are there meaningful binary operations on the set of Catalan objects?

Is it possible to come up with some kind of meaningful closed binary operation $\star$ on sets $C_n$ of Catalan objects? By Catalan objects I mean objects that correspond to a given Catalan number. I'll use well-nested parentheses since they're easy to write here, but feel free to choose your favourite objects.

When I say the operation should be meaningful, I mean that in the sense that it would be non-trivial and could be described in natural language just as Catalan objects can be described using a rule without simply listing them all. In other words, on the one hand, I don't want something trivial like every product gives the same result, and on the other hand, I don't want something so complex or unintuitive that you just have to look up the product on a seemingly arbitrary multiplication table.

One natural rule would be that $c \star c = c$ for all $c \in C$.

As an example, suppose we take the two possible ways to nest two sets of parentheses, $C_2 = \{()\ (),((\ ))\}$. We could decide that the level of nesting of a product must be the maximum level of the factors, so that $()\ () \star ((\ )) = ((\ )) \star ()\ () = ((\ ))$. Along with the rule that $c \star c = c$, this leads to a well-defined (and "meaningful") operation on $C_2$. But there is not enough information about how this operation works to generalize to $C_n$.

Any ideas?

Edit: Upon reflection, I see that there would be all sorts of natural operations, but the extent to which they are natural depends on the description of the objects. So maybe it would help if I said that I am particularly interested in binary trees. What now?

The Temperley-Lieb algebra $TL_n$ has a basis indexed by noncrossing partitions; in particular, $\dim TL_n = C_n$. Its multiplication has a very natural pictorial interpretation (given in the Wikipedia article). The multiplication almost gives a binary operation on the basis except that it is sometimes necessary to multiply by a scalar.

• Very interesting! Thank you for the link; I'll look into this. May 30, 2014 at 21:32
• When I asked my question I didn't expect to be learning about quantum teleportation... this is wild! Jun 1, 2014 at 23:15
• The Temperley-Lieb algebra is great. My favorite interpretation of it is that it's the endomorphism algebra of the $n^{th}$ tensor power of the standard representation of the quantum group $U_q(\text{sl}_2)$. In particular, for a suitable choice of the constant, you get the endomorphism algebra of the $n^{th}$ tensor power of the standard representation of the ordinary $\mathfrak{sl}_2$, or equivalently $\text{SU}(2)$. Jun 2, 2014 at 2:17

Consider the set of "mountain ranges" of length $2n$ (i.e., walks from $(0,0)$ to $(2n,0)$ using the displacements $(1,\pm 1)$ that never drop below the $x$-axis). There are $C_n$ of these. Two natural binary operations (that give this set of objects the structure of a lattice) are the maximum height and the minimum height of a pair of mountain ranges.

• Thank you for this suggestion. I have just read about the Tamari lattice, which makes for a nice generalization. Jun 1, 2014 at 23:12

I found something called the Tamari lattice which provides a good general answer to the question since many objects (nested parentheses, binary trees, etc.) can be mapped onto it in a natural way. In particular, regarding natural binary operations:

In this partial order, any two groupings $g_1$ and $g_2$ have a greatest common predecessor, the meet $g_1 ∧ g2$, and a least common successor, the join $g_1 ∨ g_2$.