算数オリンピック・続き

とやさんからご質問いただいたので〜（って、週末まで待ってくださいとか言いつつ、図がエクセルで案外と簡単に書けちゃったので(笑)）。
昨日のエントリの考え方をちょっと解説。

まず、図のように、4個の○を、各行各列に重ならないように入れてみます。
※図の黒い○の入れ方は一つの例ですので、ご注意下さいませ。

まずは(1)の発想

こっちは非常に簡単。5個目の○を、「各行各列に重ならない場所」、つまりこの図で言うと右下の隅っこに入れて、残りの1個は黄色で塗られた部分のどこに入れてもいいですよ、という発想。前述の通り、こうやって入れる形が全部で2,400通りです。

続いて(2)の発想

こっちが厄介。まずは、5個目の○を、「各行各列に重ならない場所」に入れないとどうなるか（つまり、図でいう赤の×がついているところに○を入れない前提をおくとどうなるか）、という考え方から始めます。
このとき、条件である「各行各列に少なくとも1個を入れる」ことを満たすためには、1個の○は図の緑色で塗られた4カ所のうちどこか、もう1個の○は図の青色で塗られた4カ所のうちのどこか、に入れる必要があります。
昨日の計算では、これが9600通り（重複込みで）ありまっせ、という計算をしてました。重複入れて9600通り、ってとこまでは間違ってないので、あとはどう重複を排除するかだけの問題。

ちょっと脱線

まず5個入れる(1)、まず4個入れる(2)、という発想があれば、当然次に「まず3個を各行各列に重ならないように入れて、残りの3個を適当に配置する、っていう組み合わせもあるんじゃね？」と思いつきますよね。
が、これは(1)(2)と同じ配列にならないように入れる事は不可能です。なぜなら、残ってる2行2列に対して、○は3個しかないので、少なくとも1個は、他の3個と行、列ともに重ならない場所に入れなければならない（＝(2)の配置のどれかと重なる）、からです。

で、エレガントな解法に向けた、(2)の重複問題。

※この項は図解がないので分かりにくいと思います。自分用思考過程メモにつき、読み飛ばしてくだされ。
よーく考えてみると、3600通りどころか、もっと重複あるわな…。2行2列に入った4個の○の組み合わせを重複として排除すれば終了なので、単純に9600通りを、4C2＝（4×3）÷（2×1）＝6で割ってやればいいんじゃね？と、最初は思った。
が、さらに考えてみれば、最初に入れた○のどれかが、後から入れた2個の○と行列ともに重なる組み合わせがあるはずなので、これじゃダメ、ということになります。そもそも9600÷6＝1600通り、なので計算も合ってないしね。
ここから更に、排除しちゃいけない組み合わせの数を求めれば終了かな、と思って思考中…。そもそも、重複を一気に排除するんじゃなくて、更に場合分けして重複排除せんと計算できないかなあ…とか、思考がトビウオ状態(笑)