Solution
Chords Without Crossing
Show the problem again
Eight distinct points are marked on a circle. You draw some number of chords (possibly none) between them so that no point is an endpoint of more than one chord and no two chords cross (meet at a point inside the circle). The points are labelled, so drawings that are rotations of each other count as different. How many different drawings are possible? Give an integer.
Worked solution
**Answer: 323.** Let M(n) count such drawings on n labelled points in circular order, with M(0) = M(1) = 1. Look at point 1. Either it is unused, leaving M(n − 1) drawings on the other points, or it is joined to some point j. The chord from 1 to j splits the remaining points into the j − 2 points on one side and the n − j on the other, and since chords cannot cross it, the two sides are filled independently. So M(n) = M(n − 1) + Σ_{k=0..n−2} M(k) M(n − 2 − k). These are the Motzkin numbers: 1, 1, 2, 4, 9, 21, 51, 127, 323. With 8 points the answer is 323.
Source: Classic exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.