ホーム >> 組合せ >> 交差しないマッチングの組み合わせ
hide or visible

問題の意味

条件 $1$ は要するに,$10$ 個の相異なる点を $2$ 点ずつペアにして,合計 $5$ 組のペアをつくるということです.

条件 $1$ だけであれば,ペアの作り方は,${}_{10} \mathrm{C} _2\times {}_{8} \mathrm{C} _2 \times {}_{6} \mathrm{C} _2 \times {}_{4} \mathrm{C} _{2} \times {}_{2} \mathrm{C} _{2}=145800$ 通りありますが,このうち条件 $2$ を満たすものは何通りあるでしょうか.

ヒント

下図のように各点に $1$ から $10$ の番号を指定して,$1$ とペアになりうる点を探してみます.すると,$1$ とペアになりうる点は,偶数番号の点に限ることがわかります.

なぜなら,$1$ と奇数番号を結んでしまうと,残りの点が線分を交差せずにペアにすることができなくなるからです.

漸化式で解いてみる

円周上に $2n$ 個の点がある場合に,問題の条件を満たす場合の数を $C_{2n}$ とかくことにします.求める値は $C_{10}$ です. また,便宜的に $C_{0}=1$ としておきます.

$$C_{2}=1,C_{4}=2,C_{6}=5$$ などは簡単にわかります.例えば,$C_{6}=5$ は下図を参照してください.


$C_{10}$ を求めるために漸化式をたててみましょう.

まず,一点 $1$ を指定すると,$1$ と線分で結ばれうる番号は,$2,4,6,8,10$ のいずれかです.
$1$ と $2$ が結ばれたとすると,残りの結び方はちょうど $C_{8}$ 通りあります.

$1$ と $4$ が結ばれたとすると,残りの結び方はちょうど $C_{6}\cdot C_{2}$ 通りあります.

同様に,$1$ と $6$ が結ばれたとすると,残りの結び方はちょうど $C_{4}\cdot C_{4}$ 通りあります.

と以下同様に考えていくと,次の漸化式が成り立ちます. $$C_{10}=C_{8}\cdot C_{0}+C_{6}\cdot C_{2}+C_{4}\cdot C_{4}+C_{2}\cdot C_{6}+C_{0}\cdot C_{8}$$ ところで,$C_{8}$ を求めていませんでしたが,いまの考察を $C_{8}$ に適用すると, $$C_{8}=C_{6}\cdot C_{0}+C_{4}\cdot C_{2}+C_{2}\cdot C_{4}+C_{0}\cdot C_{6}=14$$ となります.よって, $$C_{10}=14+5+4+5+14=42$$ です.

おまけ

実は,円周上に $2n$ 個の点がある場合は, $$C_{2n}=\frac{{}_{2n} \mathrm{C} _{n}}{n+1}=\frac{(2n)!}{(n+1)!n!}$$ で求められます.これはカタラン数とよばれています.