There are 16 distinct points on a circle. Determine the number of different ways to draw 8 nonintersecting line segments connecting pairs of points so that each of the 16 points is connected to exactly one other point. (For example, when the number of points is 6 , there are 5 different ways to connect them, as shown.)

![](https://cdn.mathpix.com/cropped/2024_04_17_56af4dba662dd63eccc5g-3.jpg?height=200&width=965&top_left_y=1903&top_left_x=642)
Let $f(2 n)$ be the number of different ways to draw $n$ non-intersecting line segments connecting pairs of points so that each of the $2 n$ points is connected to exactly one other point.

Then $f(2)=1$ (since there are only 2 points) and $f(6)=5$ (from the given example).

Also, $f(4)=2$. (Can you see why?)

We show that

$$
f(2 n)=f(2 n-2)+f(2) f(2 n-4)+f(4) f(2 n-6)+f(6) f(2 n-8)+\cdots+f(2 n-4) f(2)+f(2 n-2)
$$

Here is a justification for this equation:

Pick one of the $2 n$ points and call it $P$.

$P$ could be connected to the 1 st point counter-clockwise from $P$. This leaves $2 n-2$ points on the circle. By definition, these can be connected in $f(2 n-2)$ ways.

$P$ cannot be connected to the 2 nd point counter-clockwise, because this would leave an odd number of points on one side of this line segment. An odd number of points cannot be connected in pairs as required.

Similarly, $P$ cannot be connected to any of the 4th, 6 th, 8 th, $(2 n-2)$ th points.

$P$ can be connected to the 3 rd point counter-clockwise, leaving 2 points on one side and $2 n-4$ points on the other side. There are $f(2)$ ways to connect the 2 points and $f(2 n-4)$ ways to connect the $2 n-4$ points. Therefore, in this case there are $f(2) f(2 n-4)$ ways to connect the points. We cannot connect a point on one side of the line to a point on the other side of the line because the line segments would cross, which is not allowed.

$P$ can be connected to the 5 th point counter-clockwise, leaving 4 points on one side and $2 n-6$ points on the other side. There are $f(4)$ ways to connect the 4 points and $f(2 n-6)$ ways to connect the $2 n-6$ points. Therefore, in this case there are $f(4) f(2 n-6)$ ways to connect the points.

Continuing in this way, $P$ can be connected to every other point until we reach the last $((2 n-1)$ th) point which will leave $2 n-2$ points on one side and none on the other. There are $f(2 n-2)$ possibilities in this case.

Adding up all of the cases, we see that there are

$$
f(2 n)=f(2 n-2)+f(2) f(2 n-4)+f(4) f(2 n-6)+f(6) f(2 n-8)+\cdots+f(2 n-4) f(2)+f(2 n-2)
$$

ways of connecting the points.

The figures below show the case of $2 n=10$.

![](https://cdn.mathpix.com/cropped/2024_04_30_be08db732f430ab57efag-16.jpg?height=236&width=962&top_left_y=1964&top_left_x=641)

We can use this formula to successively calculate $f(8), f(10), f(12), f(14), f(16)$ :

$$
\begin{aligned}
f(8) & =f(6)+f(2) f(4)+f(4) f(2)+f(6) \\
& =5+1(2)+2(1)+5 \\
& =14 \\
f(10) & =f(8)+f(2) f(6)+f(4) f(4)+f(6) f(2)+f(8) \\
& =14+1(5)+2(2)+5(1)+14 \\
& =42 \\
f(12) & =f(10)+f(2) f(8)+f(4) f(6)+f(6) f(4)+f(8) f(2)+f(10) \\
& =42+1(14)+2(5)+5(2)+14(1)+42 \\
& =132 \\
f(14) & =f(12)+f(2) f(10)+f(4) f(8)+f(6) f(6)+f(8) f(4)+f(10) f(2)+f(12) \\
& =132+1(42)+2(14)+5(5)+14(2)+42(1)+132 \\
& =429 \\
f(16) & =f(14)+f(2) f(12)+f(4) f(10)+f(6) f(8)+f(8) f(6)+f(10) f(4)+f(12) f(2)+f(14) \\
& =429+1(132)+2(42)+5(14)+14(5)+42(2)+132(1)+429 \\
& =1430
\end{aligned}
$$

Therefore, there are 1430 ways to join the 16 points.

(The sequence $1,2,5,12,42, \ldots$ is a famous sequence called the Catalan numbers.)

ANSWER: 1430

## Relay Problems

(Note: Where possible, the solutions to parts (b) and (c) of each Relay are written as if the value of $t$ is not initially known, and then $t$ is substituted at the end.)