Combinatorial Question

Here’s something I can prove, but I don’t understand.

Let $T_n$ be the number of trees whose leaves are labeled by $\{ 1,2, \ldots, n \}$, and whose internal vertices all have degree $3$. So $T_7$ counts objects like the tree on the right.

Let $m=2n-4$. Let $M_m$ be the number of pairings of $\{ 1,2, \ldots, m \}$. So $M_{10}$ counts objects like the pairing on the left.

Theorem: $T_n=M_m$.

Proof: We have the recursive relations $T_n = (2n-5) T_{n-1}$ and $M_m = (m-1) M_{m-2}$. (Exercise!)

Of course, it is easy to solve these recursions and compute that $T_7=M_{10} = 9 \times 7 \times 5 \times 3 \times 1$. This is sequence A001147 in Sloane’s encyclopedia, the so-called double factorial sequence.

Now, let $T^{\circ}_n$ be the number of trivalent trees with vertices $\{ 1,2, \ldots, n \}$ which can be embedded in a disc, with the leaves $\{ 1,2, \ldots, n \}$ occurring in circular order on the boundary. And let $M^{\circ}_m$ be the number of pairings of $\{ 1,2, \ldots, m \}$ which can be embedded in a disc, with the points $\{ 1,2, \ldots, m \}$ occurring in circular order around the boundary. The figures below show that $T_5^{\circ} = M_6^{\circ} = 5$.

Theorem: $T^{\circ}_n=M^{\circ}_m$

Proof: We have the recurrences $T^{\circ}_n = \sum_{i+j=n-1} T^{\circ}_{i+1} T^{\circ}_{j+1}$ and $M^{\circ}_m = \sum_{a+b = m-2} M^{\circ}_a M^{\circ}_b$. (Exercise!)

These are, of course, the Catalan numbers (Sloane A000108). There is a closed formula, $T^{\circ}_n = (2n-4)!/(n-2)!(n-1)!$.

So the question is: Why? Is there some bijection between trees and matchings under which the condition of having a planar embedding behaves nicely? Are there other examples where we can go between double-factorial objects, with a symmetric group symmetry and Catalan objects with a dihedral symmetry?

33 thoughts on “Combinatorial Question”

1. Martin says:

I’m not sure whether this really answers the question for a reason, but let me try to explain one bijection for the latter case of matchings/trees in a disc. I think it doesn’t work in the other case.
(By the way, you should add that your trees need to have genus 0, i.e. be simply-connected.)
The basic idea is that m is the number of edges in a tree with n leaves minus one.

Start with a tree with n exterior vertices, consider the vertex 1 and the edge connecting it to the rest of the tree as a root, and draw the tree (or rather, use the orientation on the edges) such that each inner vertex has one incoming and two outgoing edges. (In computer science you would say a “binary tree”.)
Now the tree minus the root has m=2n-4 edges. Observe that starting from the root, each edge corresponds to a certain sequence consisting of “left”s and “right”s. Now use the lexicographic ordering for a numbering. The matching corresponding to the tree pairs always the two outgoing edges at each interior vertex.

2. (By the way, you should add that your trees need to have genus 0, i.e. be simply-connected.)

That’s part of the definition of a tree.

3. Terence Tao says:

I don’t have the answer to your question, but it seems that the second question is to free probability as the first one is to classical probability.

Let $X_1,\ldots,X_n$ be iid real random variables with mean zero and variance 1, and let’s say that all moments are finite for simplicity. Then the central limit theorem tells us that $S_n := \frac{X_1+\ldots+X_n}{\sqrt{n}}$ converges to the normal distribution N(0,1) as $n \to \infty$, so in particular the moment ${\Bbb E} S_n^m$ should converge to a fixed number depending only on m.

What is this number? Well, if one expands out ${\Bbb E} S_n^m$, one gets a mess of terms, but most terms vanish; the only ones that don’t are those in which each $X_i$, if it appears at all, appears at least twice. The dominant contribution is those that come from those $X_i$ that are paired by a perfect matching… and if one pursues this line of thought one soon sees that ${\Bbb E} S_n^m$ converges to your number $M_m$ mentioned above.

Meanwhile, let $X_1,\ldots,X_n$ be identical self-adjoint _noncommutative_ variables (living in a tracial algebra) which are independent in the sense of free probability, and with $tr(X_i) = 0$ and $tr(X_i^2) = 1$. (One can for instance view the $X_i$ as appropriately normalised random matrices of huge dimension, with the trace being the normalised trace.) We can then form the averages $S_n$ as before, and look at the limit of the $tr(S_n^m)$ (these correspond to moments of random symmetric matrices). By much the same arguments as before, these converge to the Catalan numbers $M_m^\circ$ (a computation first done by Wigner).

So presumably one can also expand moments of averages in terms of binary trees. It sounds like something that the free probability theorists have already observed, I can ask around.

4. I was trying to come up with a representation theory argument analogous to what Terry suggests: that your first statement is about the representation theory of some group while the latter statement is the same fact about the representation theory of the corresponding “free quantum group” (in the sense of Banica et al.). But so far I’m stuck.

The basic idea would be that these diagrams should form a basis for some Hom space in some tensor category. But everything I could think of failed to distinguish trees from forests in a nice way.

5. Martin says:

Thanks, Ben, for reminding me…
The way to expand my above bijection to the non-embedded case would be to answer the following question:
Rooted binary trees with n external vertices (including the root) give matchings of their m non-root edges. In the embedded case, there is a distinguished numbering of the edges, which gives the required bijection.
In the non-embedded case, can we get a numbering of the edges from the numbering of the vertices which will induce the bijection?

6. The answer to Martin’s question is an easy yes. A 1-3 valent tree with numbered vertices has no automorphisms; there are thus many ways to canonically number its edges. Any numbering of the edges induces a bijection between matchings and 1-3 trees. If the tree is planar, you could use the edge numbering that Martin described above. That gives a positive answer to David Speyer’s question, albeit a hack answer. Here is a somewhat cleaner answer:

Imagine that you put the vertices in both cases at the integers 1,…,n or 1,…,m in the real number line, and that you draw the tree or the matching in the upper half plane. Then in the case of a matching, the endpoints divide the line into m+1 segments. Meanwhile the tree has m+1 edge. Now there is an inductive encoding of the trees, or the matchings, such that each new leaf or each new matched pair is described by an integer from 1 to m+1. It is essentially what David describes. In the tree case, place the new leaf at 0, and connect 0 to one of the middle of one of the edges of the tree. In the matching case, place a new vertex at 0, and place a second new vertex between j and j+1 for some j from 0 to m.

Can you maintain a bijection between the edges of the tree and the segments between the matched vertices, so that the tree stays planar if and only if the matching stays planar? I think that by induction you can. In the tree case, a new edge A emanates from 0, and a second new edge is created by splitting another edge B into C on the left and D on the right. In the matching case, a new segment A is created to the left of 0, and a second new segment is created by splitting another segment B into C on the left and D on the right. This gives you a way to maintain the bijection and I think that it does preserve planarity. In both cases, if you require planarity, A and D are exposed while C is trapped; also all of the old exposed segments or edges to the left of B become trapped; also the exposed segments stay in the same order as the exposed tree edges.

There is also a way to explore the question further. There is a sequence of successively weaker conditions on the matchings of 1,…,m that takes you from the planar matchings to, in the limit, all of the matchings. The kth condition is that no subset of 2k+2 vertices should be matched in a star pattern, e.g., when k=2 you never have (a,d),(b,e),(c,f) with a < b < c < d < e < f. This yields a filtration on the set of matchings. The k-admissible matchings are bijective with a basis of invariants of V^{tensor m}, where V is the defining representation of sp(2k). Anyway k-admissibility is a filtration on the set of matchings. Is it an interesting filtration on the corresponding set of trees? Or is there some other bijection such that the induced filtration is interesting?

7. I’m not sure what you’re looking for, but if you unwrap the circle to a line segment, you get the usual bijection between the binary tree for a nonassociative word and the parentheses that define it. Parentheses naturally form planar matchings a la Temperley-Lieb.

8. Greg: Interesting connection to sp(2k). When m=6, the associated graded of your filtration gives 5, 9, 1. I don’t see a great way to pick out one of the 10 nonplanar trees to be “extra nonplanar”, but maybe I’d see it with more data.

Scott: Thanks! For those who find Scott’s note too cryptic, he is describing an elegant bijection between planar trees and matchings. Treat vertex n as the root of the tree. Interpret the tree as telling you a way to associate a product of (n-1) terms. Write down this product using parentheses. Match a left parenthesis to the corresponding right parenthesis

9. Danny Calegari says:

An “infinite” version of this relationship is the fact that laminations of the disk are dual to planar R-order trees, a familiar fact to low-dimensional topologists.

10. David: The bijection that I describe implies an explicit definition of “extra non-planarity” of trees that are properly immersed in the upper half plane. The only question is whether it is an interesting description. To begin with, is it rotationally invariant? (I have not checked.)

11. Okay, now I’ve checked that it doesn’t work. :-) There does not exist a tree on 8 vertices which is rotationally invariant.

Still, I did give a bijection that could be worth studying. It is perhaps a bit arbitrary how to split the edge of a tree into left and right when you attach a new twig to it, but there are canonical choices for that, and in any case you could study the resulting family of bijections from looking at all choices.

12. Danny, the lamination picture is really neat (and was totally off my radar). Is there a natural way to extract the finite statement as a consequence, e.g., by passing to some kind of PL structures?

13. So following up on Scott’s suggestion, to get the first bijection we want a non-planar way of parenthesizing commutative but still nonassociative words?

The first thing I could think of would be to send David’s element of T_7 to a pairing as follows. Connect the left of 1 to the right of 5, connect the left of 3 to the right of 4, connect the left of 15 to the right of 6. Connect the left of 156 to the right of 34, connect the left of 13456 to the right of 2.

The rule I’ve used (for no good reason) is that when you multiply two words you connect the left of the word with the smallest letter in it to the right of the other word.

So in the end reading from left to right we have:
left of 13456=a, left of 156=b, left of 15=c, left of 1=d, right of 2=e, left of 3=f, right of 4=g, right of 34=h, right of 5=i, right of 6=j.

Hence the under this ostensible bijection David’s example tree would be sent to the pairing which pairs ae, bh, cj, di, fg.

I kinda doubt that this exact construction is a bijection, but maybe something similar will work?

14. Hrm, I think I got myself confused between the parentheses in parenthesized words and the parentheses in strings of matching parentheses.

15. Danny Calegari says:

Dear Scott: probably, but nothing immediately comes to mind. :)

16. john mangual says:

There might be an approach using path integrals. The Catalan numbers are the moments of the Gaussian, so $C_n = \frac{1}{\sqrt{2\pi}} \int x^{2m} e^{-x^2/2} dx$ and obviously the odd moments vanish.

There is an action you can integrate to give labelled 3-valent graphs. $\frac{1}{\sqrt{\hbar}} \int e^{ [x^2/2 - g(x + x^3/6)]/\hbar }$. Take the limit as $\hbar$ goes to 0 and get a generating function (in $g$) for trivalent labelled trees.

I don’t know if these model exactly the combinatorial objects you have above. This fancy use of Gaussians is not unrelated to comment 3.

17. I don’t entirely understand Scott’s suggestion in comment 9. If you parenthesize a non-associative expression, like (a*b)*c vs a*(b*c), you have to retain the the binary operation symbol * as part of the combinatorial object. This is not the bijection between trees and parenthesis strings with nothing inside. That bijection is the “CAR-CDR” bijection in Lisp. In other words, what is the inside the first pair of parentheses is the CAR, what is after the first pair is the CDR, or for short you condense the string to (CAR)CDR. Then in tree form the CAR is the left child while the CDR is the right child.

I’m not entirely sure, but I think that the planar special case of the bijection that I described is exactly the CAR-CDR bijection between matchings and trees. But I am wondering now if I did not describe it clearly enough.

Danny’s remark about R-trees is interesting, but these are not the same structure as 3-1-valent trees as David described. Rather, planar R-trees generalize planar trees with no valence restrictions. Yes, these are Catalan-sized and geometrically dual to planar matchings. But that bijection is different from the bijection with 3-1-valent trees; in particular it does not generalize to the non-planar case because the numbers are not the same. There are 4 trees with 4 labeled leaves, and 4 is not an odd factorial.

18. Certainly somewhere between Scott’s comment, David’s rephrasing of it, and my reading of that comment something got confused. (Probably my fault.) Here’s the tricky thing: Catalan numbers count either expressions like ((a*b)*c) or expressions like (()), but the bijection isn’t “forget all the non-parenthesis symbols,” instead it’s “keep the left parens, turn multiplications into right parens, and forget the rest.”

I’m not sure if this is the same as Greg’s CAR-CDR bijection because all I know about those symbols is that “My other car is a cdr” is a funny bumper sticker.

19. Yes, multiplication should close the matching, and this gives car-cdr. I think I was a little too hasty with “the usual bijection”.

20. Yeah, I the mistake is in my rephrasing. Noah has it right.

21. Alexander Woo says:

Yes that is the same as the CAR-CDR bijection.

Note that there is a second similar bijection where one turns multiplications into left parens and leaves the right parens.

My experience is that, as a heuristic that isn’t always true, there are two kinds of Catalan objects. Within each kind there is only one natural bijection, and between sets of different kinds, there are two natural bijections related by some involution.

22. I have a similar opinion, but I think there are three types.

Type 1:

planar trivalent trees with $n$ leaves
planar binary rooted trees with $(n-1)$-leaves
triangulations of the $n$-gon
ways of associating an $n$-fold product

Type 2:

noncrossing matchings of $2n-4$ points
noncrossing partitions of $n-2$ points
permutations of $n-2$ elements which are below $(1 2 ... n-2)$ in the total length order

Type 3:

matching parenthesis sequences with $2n-4$ parentheses
partitions contained in the staircase $(1,2, ..., n-3)$
regions of the Shi arrangement in the dominant chamber
rooted planar trees with $n-1$ vertices

23. Grr… Can’t figure out how to fix wordpress’s list formatting right now. “permutations of $n-2$ elements which are below $(1 2 ... n-2)$ in the total length order” is a single entry.

24. To say a bit more, Type I objects occur in cluster algebras, in canonical bases and certain computations with quivers. Type II objects occur in Garside structures, free probability, basketballs and other computations with quivers. There has been a lot of work relating these two: I’ll single out Thomas and Ingalls as my favorite, and also plug my own work with Nathan Reading.

As far as I know, Type III is still pretty much a mystery. Drew Armstrong and Hugh Thomas have been announcing that they have a partial understanding of where these fit in, but I don’t think there is a preprint yet.

25. The four examples in Type 1 are all nearly identical. They have a geometric action of the dihedral group D_n.

The first two examples in Type 2 are nearly identical. They have a geometric action of the dihedral group D_{2n-4}.

I do not know of any good way to relate these two dihedral group actions.

I am not sure what message is intended in Type 3, or in the third example in Type 2. For instance, parenthesis sequences with 2n-4 parentheses are nearly identical to planar matchings of 2n-4 points.

26. Actually it’s an ironic statement that Type 1 Catalan objects are the ones that occur in canonical bases. In fact, the set of planar matchings of 2n points is the dual canonical basis of Inv(V^{tensor 2n}), where V is the defining representation of sl(2).

27. john mangual says:

Oof… I made a typo. The moments of the Wigner semicircle distribution are the Catalan numbers: $C_{m} = \mathbb{E}[x^{2m}] = \int_{[-2,2]} x^{2m} \sqrt{4 - x^2} dx$ These are like non-crossing matchings.

The moments of the Gaussian correspond to perfect matchings so
$(2k-1)!! = \mathbb{E}[x^{2m}] = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^\infty x^{2m}e^{-x^2/2} dx$

28. Danny Calegari says:

Greg’s remark about my remark is interesting (and correct), but it is easy to make the correspondence respect valence: just restrict to laminations with ideal triangle complementary regions (which one often wants to do in practice anyway, to rigidify the situation) and R-order trees with order 3 branch points. And actually, the situation does generalize to the non-planar case: if one takes the product with R, one obtains a 2-dimensional lamination of R^3, and now (a nontrivial fact, well-known to laminators) there are automorphisms of the pair (R^3, lamination) which have the effect of reversing the cyclic order on the branches at any given family of branch points of the R-order tree.

29. Yes, that’s also an important correspondence, but also not the same as David’s. If you restrict the laminations to the simplicial ones, they no longer generalize planar matchings.

Unrestricted measured geodesic laminations really do generalize planar matchings. For instance, in the representation theory of sl(2), you see ways to parametrize planar matchings that are a discrete version of train track coordinates. (See my old paper arXiv:q-alg/9712003.) It’s interesting and quite possibly not a coincidence that sl(2) is connected to both planar matchings, and in a different way to measured laminations on surfaces.

30. Danny Calegari says:

Dear Greg – thanks for the reference!

31. “I am not sure what message is intended in Type 3, or in the third example in Type 2. For instance, parenthesis sequences with 2n-4 parentheses are nearly identical to planar matchings of 2n-4 points.”

The third example in type 2: Consider $S_{n-2}$ as generated by all of its reflections (transpositions), and let $\ell_T$ denote the corresponding length function. So $S_3$ has one element of length $0$ (the identity), three elements of length $1$ (the transpositions), and two elements of length $2$ (the three cycles). This makes $S_{n-2}$ into a poset in the usual manner that length functions do: $u \leq w$ if $\ell(u) + \ell(u^{-1} w) \leq \ell(w)$. The elements of $S_{n-2}$ which are below the $(n-2)$-cycle $(1 \ 2 \ \ldots \ n-2)$ are precisely the permutations whose cycles form a noncrossing partition. This poset has a lot of interesting structure — see Brady and Watt’s papers for Lie theoretic and Coxeter theoretic perspectives.

While I agree that it is easy to go between parentheses and matchings, I do think that type 2 and type 3 have very different natural structures. For example, both suggest natural poset structures, but different ones. In type 2, you have the lattice of noncrossing partitions (the order relation is refinement); in type 3, you have the lattice of Dyck paths (the order relation is one path lying below another). It is rather hard to translate operations on one side (including the dihedral symmetry) into operations on the other.

Finally, regarding canonical bases, here is what I was thinking: Look at the homogenous coordinate ring of $G(2,n)$. This ring is generated by the Plucker coordinates, $p_{ij}$, with $1 \leq i < j \leq n$. The canonical basis for this ring is those products $\prod p_{ij}^{a_{ij}}$ where the $p_{ij}$ which occur are contained among the diagonals of a triangulation of the $n$-gon. For example, the canonical bases for the coordinate ring of $G(2,5)$ consists of monomials of the following forms

$p_{12}^a p_{23}^b p_{34}^c p_{45}^d p_{15}^e p_{13}^f p_{35}^g$
$p_{12}^a p_{23}^b p_{34}^c p_{45}^d p_{15}^e p_{24}^f p_{14}^g$
$p_{12}^a p_{23}^b p_{34}^c p_{45}^d p_{15}^e p_{35}^f p_{25}^g$
$p_{12}^a p_{23}^b p_{34}^c p_{45}^d p_{15}^e p_{14}^f p_{13}^g$
$p_{12}^a p_{23}^b p_{34}^c p_{45}^d p_{15}^e p_{24}^f p_{25}^g$.

But you are right that noncrossing matchings also occur in this situation.

32. Brent Werness says:

Hey,

It looks like a lot of interesting things have been said and an answer in the affirmative already found, but here is [I hope at least] a graphically clear bijection between such perfect matchings and such trees which preserves planarity. I’ve included below an image which illustrates the process on a particular matching (which is planar, but that is not required by the construction; it just simplifies the diagram).

The bijection proceeds as follows. Throughout this description, I’ll refer to edges in the matching as initial edges, and edges in the tree as final edges. Take a matching with the vertices 1, …, 2n-4 arranged on the circle and a special vertex marked (corresponding to one in the above description of the problem). I will consider the vertices to be ordered so that they increase in the clockwise direction. Now (as indicated in the diagram 2 above) add two more vertices after 2n-4 and connect them with a final edge (in bold in the diagram). Here comes the fun part (drawn in diagram 3): take each initial edge, say between i and j with i < j and replace it with two final edges, one from i to j+1 and one from j+1 to j. The tree was then cleaned up in diagram 4, but this is not required, the bolded edges in diagram 3 suffice.

I claim now that this is the type of tree which we want. Since the initial edges formed a matching, the resulting final edges from the above process will be acycylic (and hence will be a forest) and every vertex will have will have degree (with respect to the final edges) of either 1 or 3. Moreover, there are 2(n-2)+1 final edges (the plus one is from the extra edge added in step 2 and the rest are from the matching) which suffices to tell us when combined with the above that our forest is in fact a tree with n leaf vertices (just edge counting).

I haven’t worked out entirely why this is bijective, but I believe that it is pretty clearly injective if you mull over it a bit and hence since we know the two sets are the same size from the post, this will be a bijection.

Finally, note that planar matchings clearly yield planar trees (embedded in the correct manner) since we may think of the process of making the final edges as simply distorting the initial edges in such a way that in never crosses an initial edge nor the possible zone into which another initial edge may be distorted (since the distortion is clockwise). Thus again by counting this gives the desired bijection.

I’d like to see a version which gives an explicit inverse map so everything could be seen more clearly, but I still think that this is interesting as a response in its own right.

33. Brent Werness says:

Oops,

The image didn’t work! To make sense of what I said you need this diagram:

If someone could show me how to streamline it in, I’d be grateful.