Let there be 2n points V on a circle in the plane. A perfect matching M is a set

Question

Let there be 2n points V on a circle in the plane. A perfect matching M is a set of
segments with endpoints only from V and every point in V is an endpoint of exactly one
segment. Note that jMj = n as one segment needs exactly 2 points from V . A matching
M in non-crossing if the segments are disjoint. Find the number of non-crossing perfect
matchings for 2n points.

This can be stated in graph theory language as follows. Count the number of perfect
matchings of K2n with vertices are vertices of a regular 2n-gon in the plane such that the
edges of the matching do not cross.

Example for n = 3 and hence 6 points.

Explanation / Answer

=n(n+1)/2

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.