　内部の点がなく，正方形の辺上に点が $2n$ 個ある場合のペアの作り方が $C_n$ だけあるとする．$C_n$ を求めよう．ある点 $A$ を固定して，$A$ とペアになる点が $A$ から時計回りに奇数だけ隣の点である必要がある． $A$ から $2k-1$ だけ隣の点であったとき，残りのペアの繋ぎ方は $C_{k-1}C_{n-k}$ だけある．ただし $C_0=1$ である．よって次が成り立つ．
$$C_n=\sum_{k=1}^n C_{k-1}C_{n-k}$$
この漸化式から $C_1=1, ~ C_2=2, ~ C_3=5, ~ C_4=14$ がわかる．\
　さて，本問において内部の $4$ 点を含むペアを先に決めることで内部の点がない場合に帰着しよう．
 - 内部の $4$ 点がすべて辺上の点とペアを作るとき，  
まずペアの作り方が ${}\_{8}\mathrm{P}\_{4}$ 通り，それぞれについて辺上の点同士の結び方が $C_2$ 通り．

- 内部の $2$ 点がペアを作り，残りの $2$ 点が辺上の点とペアを作るとき，  
内部の点同士でペアを作る点の選び方が $6$  通り，残った $2$ 点と辺上の点とのペアの作り方が ${}\_{8}\mathrm{P}\_{2}$ 通り，それぞれについて辺上の点同士の結び方が $C_3$ 通り．

 - 内部の $4$ 点がすべて内部の点同士でペアを作るとき，  
まず内部の点同士のペアの作り方が $3$ 通り，それぞれについて辺上の点同士の結び方が $C_4$ 通り．

　したがって求めるペアの作り方は
$$ {}\_{8}\mathrm{P}\_{4} \cdot C_2 +  6 \cdot {}\_{8}\mathrm{P}\_{2} \cdot C_2  +3\cdot C_4=\textbf{5082}$$
通りである．

----

**余談．**\
　本解説で導入した数列 $\\{C_n\\}$ に現れる数は Catalan 数と呼ばれており，一般に $n$ 番目の Catalan 数 $C_n$ は次のように一般項で表せる．（ $C_0=C_1=1$ および解説で得た漸化式を満たすことを確かめよ．）
$$C_n=\frac{1}{n+1}\binom{2n}{n}=\frac{(2n)!}{(n+1)!n!}$$
公式解説
https://onlinemathcontest.com/contests/omcb020/editorial/3209
　図のように，正方形上に点が $12$ 個あります（ $8$ 個は辺上，$4$ 個は内部にあります）．これら $12$ 個の点を $2$ 個ずつ $6$ 組のペアに分割する方法であって，次が成り立つようなものは何通りありますか？

- 各ペアの $2$ 点を端点とする**曲線**を計 $6$ 本引く方法であって，どの曲線も正方形の内部または境界を通り，かつ他の曲線と共有点を持たないようなものが存在する．

![figure 1](\/images\/gR2n8kAKfyaZlT4zLBovoQ81VXGfvkcMfspS57uz)