Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
Very interesting! Thank you for the link; I'll look into this. –  Théophile May 30 at 21:32
    
When I asked my question I didn't expect to be learning about quantum teleportation... this is wild! –  Théophile Jun 1 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)$. –  Qiaochu Yuan Jun 2 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.

share|improve this answer
    
Thank you for this suggestion. I have just read about the Tamari lattice, which makes for a nice generalization. –  Théophile Jun 1 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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.