Let be a positive integer and fix distinct points on a circumference. Split these points into pairs and join the points in each pair by an arrow (i.e., an oriented line segment). The resulting configuration is good if no two arrows cross, and there are no arrows and such that is a convex quadrangle oriented clockwise. Determine the number of good configurations.
Solution
First solution. The required number is . To prove this, trace the circumference counterclockwise to label the points .
Let be any good configuration and let be the set of all points from which arrows emerge. We claim that every -element subset of is an -image of a unique good configuration; clearly, this provides the answer.
To prove the claim induct on . The base case is clear. For the induction step, consider any -element subset of , and assume that for some good configuration . Take any index such that and (assume throughout that indices are cyclic modulo , i.e., etc.).
If the arrow from points to some , , then the arrow pointing to emerges from some , in the range through , since these two arrows do not cross. Then the arrows and form a prohibited quadrangle. Hence, contains an arrow .
On the other hand, if any configuration contains the arrow , then this arrow cannot cross other arrows, neither can it occur in prohibited quadrangles.
Thus, removing the points from and the point from , we may apply the induction hypothesis to find a unique good configuration on points compatible with the new set of sources (i.e., points from which arrows emerge). Adjunction of the arrow to yields a unique good configuration on points, as required.
Second solution. Use the counterclockwise labeling in the solution above.
Letting be the number of good configurations on points, we establish a recurrence relation for the . To this end, let the th Catalan number; it is well-known that is the number of ways to connect given points on the circumference by pairwise disjoint chords.
Since no two arrows cross, in any good configuration the vertex is connected to some . Fix in the range through and count the number of good configurations containing the arrow . Let be any such configuration.
In , the vertices are paired off with one other, each arrow pointing from the smaller to the larger index, for otherwise it would form a prohibited quadrangle with . Consequently, there are ways of drawing such arrows between .
On the other hand, the arrows between also form a good configuration, which can be chosen in ways. Finally, it is easily seen that any configuration of the first kind and any configuration of the second kind combine together to yield an overall good configuration.
Thus the number of good configurations containing the arrow is . Clearly, this is also the number of good configurations containing the arrow , so
To find an explicit formula for , let and let be the generating functions of the and the , respectively. Since , relation (*) yields , so
Consequently, .
Third solution. Let denote the th Catalan number and recall that there are exactly ways to join distinct points on a circumference by pairwise disjoint chords. Such a configuration of chords will be referred to as a *Catalan -configuration*. An orientation of the chords in a Catalan configuration making it into a good configuration (in the sense defined in the statement of the problem) will be referred to as a good orientation for .
We show by induction on that there are exactly good orientations for any Catalan -configuration, so there are exactly good configurations on points. The base case is clear.
For the induction step, let , let be a Catalan -configuration, and let be a chord of minimal length in . By minimality, the endpoints of the other chords in all lie on the major arc of the circumference.
Label the endpoints 1, 2, ..., counterclockwise so that , and notice that the good orientations for fall into two disjoint classes: Those containing the arrow , and those containing the opposite arrow.
Since the arrow cannot be involved in a prohibited quadrangle, the induction hypothesis applies to the Catalan -configuration formed by the other chords to show that the first class contains exactly good orientations.
Finally, the second class consists of a single orientation, namely, , every other arrow emerging from the smaller endpoint of the respective chord; a routine verification shows that this is indeed a good orientation. This completes the induction step and ends the proof.
Fourth solution. (Sang-il Oum) As in the previous solution, we intend to count the number of good orientations of a Catalan -configuration.
For each such configuration, we consider its dual graph whose vertices are finite regions bounded by chords and the circle, and an edge connects two regions sharing a boundary segment. This graph is a plane tree with edges and vertices. There is a canonical bijection between orientations of chords and orientations of edges of in such a way that each chord crosses an edge of from the right to the left of the arrow on that edge. A good orientation of chords corresponds to an orientation of the tree containing no two edges oriented towards each other. Such an orientation is defined uniquely by its source vertex, i.e., the unique vertex having no incoming arrows.
Therefore, for each tree on vertices, there are exactly ways to orient it so that the source vertex is unique — one for each choice of the source. The answer now follows along the lines in the solution above.