直線型グラフのマッチング数

　以下のような直線型グラフのマッチングについて考える。

一般にノード数nの直線型グラフからk個のマッチングを選ぶパターン数は_n-kC_kとなる。

例えば上のグラフの場合（n=6）は、
k = 1なら_6-1C₁ = 5、
k = 2なら_6-2C₂ = 6、
k = 3なら_6-3C₃ = 1
となり、実際に個数を数えてみると正しいことが分かる。

何をやってるかというと、マッチングに使われる枝の左側のノードを選んでいるわけである。普通にノードを選ぶだけだと一つのノードが複数のマッチングに属してしまうかもしれないので、あらかじめ右側の端点に使われるノードを除いておく。

すると左側のノードの選び方により一意にマッチングが決定する。逆にマッチングの選び方に対して、左側のノードの選び方は一意に決まる。よって一対一の対応にあるのでこの方法で数え上げができることが分かる。