完全被覆問題
完全被覆 (perfect matching) に関する問題の多くは組合せ論やグラフ理論などの離散数学と関わりがある。
普通のチェス盤は8×8の64のマス目がある。チェス盤の隣り合う2マスを覆うことのできるドミノが十分に与えられたとする。チェス盤に次のように32個のドミノを並べることは可能かを考える。
ドミノ同士が重ならないようにする。
ドミノはチェス盤の2マスを覆う。
チェス盤の全てのマスを覆うようにする。
このような並べ方をドミノによるチェス盤の「完全被覆(perfect matching)」と言う。これは簡単な並べ方の問題で、すぐに様々な完全被覆を作れるだろう。大変ではあるが異なる完全被覆の数を数えることもできる。ちなみにその数は、1961年にフィッシャー(Fischer)によって12988816個と解っている。また3×3の盤で完全被覆がない。少なくとも縦と横のどちらかが偶数の場合ならば、つまり、チェス盤のマス目の数が偶数の場合ならば、そのチェス盤が完全被覆を持っている。一般的にはm×nのmnマスで完全被覆が存在するかについて議論される。また、フィッシャーはm×nのチェス盤の異なる完全被覆の数を数えるための三角関数による一般的公式を見いだした。