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?