問題
座標平面上に8本の直線
がある。以下，16個の点
から異なる5個の点を選ぶことを考える。
(1) 次の条件を満たす5個の点の選び方は何通りあるか。
上の8本の直線のうち，選んだ点を1個も含まないものがちょうど2本ある。
(2) 次の条件を満たす5個の点の選び方は何通りあるか。
上の8本の直線は，いずれも選んだ点を少なくとも1個含む。
方針
4本の縦線と4本の横線を、4列・4行の格子として扱う。(1)は空になる横線の本数と縦線の本数に分け、の3場合を数える。残った行・列にさらに空きが出ない条件を必ず入れる。(2)は5点で4行4列をすべて使うため、行の点数分布も列の点数分布もになることを使い、2点を含む行と列を固定して数える。
解答
4本の横線を行、4本の縦線を列と呼ぶことにする。
(1)
選んだ点を含まない行の本数を、選んだ点を含まない列の本数をとする。条件は である。
まずの場合を考える。空の2行の選び方は 通りである。残ったの格子から5点を選び、4列すべてを使う必要がある。各列に少なくとも1点ずつ入り、合計5点なので、1列だけに2点、残り3列に1点ずつ入る。2点入る列の選び方が4通り、残り3列ではそれぞれ上下どちらの行に置くかを選べるので 通りである。よってこの場合は 通りである。対称性により、の場合も192通りである。
次にの場合を考える。空の1行と1列の選び方は 通りである。残ったの格子から5点を選び、残りの3行3列をすべて使う必要がある。まず5点を自由に選ぶと通りである。このうち、ある1行がさらに空になる選び方は、残り6点から5点を選ぶので通りであり、その行の選び方が3通りある。同様に、ある1列がさらに空になる選び方も通りである。5点を選ぶため、2行が同時に空になることや、行と列が同時に追加で空になることは起こらない。したがって 通りである。この場合は 通りである。
以上を合わせて、求める数は 通りである。
(2)
5点で4行すべてを使うので、行ごとの点数分布は である。同様に、列ごとの点数分布もである。
2点を含む行を、2点を含む列をとする。の選び方が4通り、の選び方が4通りで、合わせて 通りである。以下、を固定して数える。
交点を選ぶ場合、行にはあと1点必要であり、その列は以外の3列から選ぶ。また列にもあと1点必要であり、その行は以外の3行から選ぶ。残った2行と2列には1点ずつ置けばよいので、対応のさせ方が2通りある。よって 通りである。
交点を選ばない場合、行の2点は以外の3列から2列を選んで置く。また列の2点は以外の3行から2行を選んで置く。すると残った1行と1列の交点に最後の1点を置くしかない。したがって 通りである。
よって求める数は 通りである。
別解。
(2)は包除原理でも数えられる。16点から5点を選ぶ総数はである。少なくとも1本の行または列が空になる選び方を除くと、
となる。これは であり、同じ答えを得る。交点を固定する本解の方が構造は見やすいが、包除原理は確認用として有効である。