## Task 4 - 221224

Let $n \neq 0$ be a natural number. On a circle, there are $2 n$ pairwise distinct points $P_{1}, P_{2}, \ldots, P_{2 n}$ given.

We are looking for the number $A_{n}$ of all different ways to draw a set of $n$ chords such that the following conditions are met:

Each chord connects one of the points $P_{1}, P_{2}, \ldots, P_{2 n}$ with another of these points, and no two of these chords have a common point inside or on the boundary of the circle.

Two possibilities are considered different if and only if there is at least one pair of points $P_{i}, P_{j}$ that is connected by a chord in one of the two possibilities but not in the other.

a) Determine the number $A_{3}$ by providing several different possibilities for three chords for six points $P_{1}, P_{2}, \ldots, P_{6}$ and proving that all different possibilities of the required type are covered!

b) Determine a formula that can be used to calculate the number $A_{n}$ for any $n \geq 2$ from the numbers $A_{1}, \ldots, A_{n-1}$!

c) Determine the number $A_{5}$!
In the following, we assume that the points $P_{1}, P_{2}, \ldots, P_{2 n}$ are arranged in exactly this order, and in a uniform direction of rotation on the circumference, which only simplifies the terminology here, but does not restrict the generality of the problem.

Furthermore, we will refer to a selection of $n$ chords as "admissible" if it meets all the requirements of the problem. More generally, we also want to call a selection of $k \leq n$ chords admissible if it can be completed in at least one way to an admissible selection of $n$ chords. Here, the special case $k=1$ is particularly important.

a) First, we make a "rough subdivision" according to the possibilities of drawing an admissible chord from the fixed point $P_{1}$, which can then, according to the above, be completed in at least one way to an admissible selection of chords.

- If $P_{1}$ is connected to one of its two neighboring points $P_{2}$ or $P_{6}$, then for the remaining 4 points, there are 2 possibilities each for completing to an admissible selection of chords.
- If $P_{1}$ is connected to the point $P_{4}$, then the remaining chords for an admissible selection are thus fixed as follows: $P_{2}$ must be connected to $P_{3}$ and $P_{5}$ to $P_{6}$, i.e., there is only one possibility here.
- If $P_{1}$ is connected to one of the other points $P_{3}$ or $P_{5}$, then there is no admissible "pairing" for $P_{2}$ or $P_{6}$ with a still free point via a chord, these connections are thus

Examples of inadmissible chords.

The total number $A_{3}$ of possibilities in a) for an admissible selection of chords is thus 5.

b) For the general case, we need to answer the following question: When exactly is a chord from $P_{1}$ to another point $P_{k}, k=2,3, . ., 2 n$ admissible in the above sense? If we assume, which can also be shown to be valid by induction, that all $A_{k}>0$ for $k=0,1, . ., n-1$ (where we also set $A_{0}:=1$ for reasons of compatibility), then the answer is surprisingly simple: It suffices to require that between $P_{1}$ and $P_{k}$, as well as between $P_{k}$ and $P_{1}$ in the sense of our cyclic orientation, there is an even number of points, since then for these two subsets of points, there is an admissible selection of chords for each subset by assumption.

This now also clearly provides an inductive method for calculating $A_{n}$ for $n>0$, namely:

$$
A_{n}=\sum_{k=0}^{n-1} A_{k} A_{n-k-1} \quad\left(n \in \mathbb{N}^{*}\right)
$$

For example, we get:

- $A_{1}=A_{0} A_{0}=1 \cdot 1=1$.
- $A_{2}=A_{0} A_{1}+A_{1} A_{0}=1 \cdot 1+1 \cdot 1=2$.
- $A_{3}=A_{0} A_{2}+A_{1} A_{1}+A_{2} A_{1}=1 \cdot 2+1 \cdot 1+2 \cdot 1=5$.
- $A_{4}=A_{0} A_{3}+A_{1} A_{2}+A_{2} A_{1}+A_{3} A_{0}=1 \cdot 5+1 \cdot 2+2 \cdot 1+5 \cdot 1=14$

With this, the last remaining point c) can also be answered very simply as follows:

c) $A_{5}=A_{0} A_{4}+A_{1} A_{3}+A_{2} A_{2}+A_{3} A_{1}+A_{4} A_{0}=1 \cdot 14+1 \cdot 5+2 \cdot 2+5 \cdot 1+14 \cdot 1=42$.