OMC125(E)

　$U=\{u_1,u_2,\ldots,u_7\},V=\{v_1,v_2,\ldots,v_7\}$ を頂点集合とし，$U$ と $V$ の任意の頂点間に辺を張った辺集合を $E$ とする．$6$ つの辺 $(u_1,v_1),(u_1,v_2),(u_2,v_1),(u_2,v_2),(u_3,v_3),(u_4,v_4)$ を禁止辺と呼ぶとき，二部完全グラフ $(U+V,E)$ の最大マッチングであって，禁止辺を一つも含まないものの個数を数え上げよ．

　ここで，$a_k$ を「$k$ 個の禁止辺の選び方 ${}_6\mathrm{C}_{k}$ 通りそれぞれについて，その禁止辺を全て含むマッチングの場合の数を考えたとき，それらの総和」と定義すると，$a_k$ は以下のように計算される．

• $a_0=7!$
• $a_1=6!\times 6$
• $a_2=5!\times 11$
• $a_3=4!\times 8$
• $a_4=3!\times 2$
• $a_5,a_6=0$

　よって，包除原理より禁止辺を一つも含まない最大マッチングの個数は $a_0-a_1+a_2-a_3+a_4=1860$ である．したがって，元の問題の答えは $1860^2=\mathbf{3459600}$ である．

　このように，包除原理を用いると機械的に計算が可能である．