OMC174 (for experts)
OMC174(C)
の番号のついた頂点を用意し,番号の和が のいずれかである頂点の間に辺を張ることで(無向)グラフ を構成すると, は図1のようになる.ただし図1において,
である.スコアが となるような 枚のカードの選び方は,頂点の個数が ,辺の本数が である の誘導部分グラフに対応し,その誘導部分グラフを図1の頂点の位置関係で考えたときの形は図2の (i)~(v) のいずれかである(それぞれ回転や反転したものも含む).
(i) は連結な 頂点の位置で場合分けして考えれば 通り.また (ii)~(v) については反転および回転を考えると (ii) は 通り,(iii), (iv), (v) は 通りずつとわかる.
以上より,求める場合の数は 通り.
誘導部分グラフとは
もとのグラフからいくつかの頂点を選ぶとき,それらの頂点の間の辺の有無がもとのグラフと一致する部分グラフを誘導部分グラフと呼ぶ.解説YouTube
解説YouTubeが存在しません.