Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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. – Gerry Myerson Feb 25 '13 at 0:28
@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. – AsinglePANCAKE Feb 25 '13 at 0:37
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. – Gerry Myerson Feb 25 '13 at 0:58
@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. – AsinglePANCAKE Feb 25 '13 at 1:03

Your Answer


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

Browse other questions tagged or ask your own question.