So I'm asked to count the number of ways of connecting n+1 collinear points with n line segments subjected to the following constraints:

If the line is L

1) No segment passes below L. 2) Starting at any vertex, you can "walk" to any other by some sequence of arcs. 3) No two arcs can intersect (except at the vertices). 4) At every vertex, the arcs all leave in the same direction (left or right).

Counting the number of ways to do this should yield the catalan numbers I think. If anyone wants to provide a combinatorial solution of this, it's more than welcome. However, I'm more interested in showing the relation of these graphs to triangulations of an n+2 gon.

Namely, provided I'm right about the catalan-ness of it all, there should be the same number of triangulations of the n+2 gon as there are ways to draw this n+1 vertex graph. But I'm not sure how to associate each graph to a triangulation. I'm assuming I need to number the vertices of the graph, add one, and then permute them in some consistent way to get a uniquely associated triangulation. But I'm coming up short here...suggestions?

  • $\begingroup$ You write "line segments", but then you switch to "arcs". Either way, it's hard to see any way to satisfy all the requirements for $n\ge2$. Say you have 3 points, 2 arcs. If there's an arc from 1 to 2, then to get anywhere from 2 there must be an arc leaving 2, but to get anywhere from 3 there must be an arc leaving 3. Similarly if there's an arc from 1 to 3, etc. $\endgroup$ Feb 25 '13 at 0:28
  • $\begingroup$ @GerryMyerson if there's an arc from 1 to 3 then you can walk back from 2 to 1 and then to 3, giving a path from 2 to 3. $\endgroup$ Feb 25 '13 at 0:37
  • $\begingroup$ You can do that if there's an arc from 2 to 1 and an arc from 1 to 3, but then you can't walk from 1 to 2. You write about each arc having a direction, so I'm assuming you can only walk in one direction on any given arc. Otherwise, I don't know what condition 4) means. $\endgroup$ Feb 25 '13 at 0:58
  • $\begingroup$ @GerryMyerson No restriction on which way to walk. I just mean if there's an arc leaving point k to the right, then every other arc leaving point k must also leave to the right. It's the cartographer who has restrictions, not the pedestrians. $\endgroup$ Feb 25 '13 at 1:03

The objects you are describing are usually called "non-crossing alternating trees".

The following picture, taken from a paper of mine, illustrates the bijection between them and binary trees (top) or parenthesizations (bottom). In the picture two binary trees/non-crossing alternating trees/parenthesizations that are related by a flip are shown.

The bijection between these and triangulations can be found in many places.

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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