縦4個、横4個のマス目のそれぞれに1, 2, 3, 4の数字を入れていく。このマス目の横の並びを行といい、縦の並びを列という。どの行にもどの列にも同じ数字が1回しか現れない入れ方は何通りあるか求めよ。
「行も列も重複がない」という拘束条件です。
1次元なら問題にもなりませんが、2次元になると途端に難しくなります。
一見したところ、必勝法はなさそうです。
愚直にゴリゴリいってみます。
1. 第1行の並べ方
第1行について考えます。
1, 2, 3, 4を重複なく並べるので、並べ方は通りです。
\begin{array}{|c|c|c|c|} \hline
1 & 2 & 3 & 4 \\ \hline
&&& \\ \hline
&&& \\ \hline
&&& \\ \hline
\end{array}
2. 第1列の並べ方
次に、第1列の第2~4行について考えます。
第1行で使った数字を除く3つの数字を重複なく並べることになります。
並べ方は、第1行の並べ方それぞれに対し通りあります。
\begin{array}{|c|c|c|c|} \hline
1 & 2 & 3 & 4 \\ \hline
2 &&& \\ \hline
3 &&& \\ \hline
4 &&& \\ \hline
\end{array}
3. 残りのマスの並べ方
残りのマスの並べ方を考えていきます。
上の図では1行2列と2行1列に同じ数字が入っており、第2行の第2~4列の並べ方を考えます。
そうでない場合も1行2列と同じ数字を第1列に入れた行の第2~4列を考えればよく、上の図で考えても一般性を失いません。
代表で、上の図で考えていきます。
第1行に既に入っている数字を踏まえると、第2行の第2~4列に入る数字は限定されます。
(3, 4, 1)、(1, 4, 3)、(4, 1, 3)の3通りしかありません。
\begin{equation}
\begin{array}{|c|c|c|c|} \hline
1 & 2 & 3 & 4 \\ \hline
2 & 3 & 4 & 1 \\ \hline
3 &&& \\ \hline
4 &&& \\ \hline
\end{array} \quad
\begin{array}{|c|c|c|c|} \hline
1 & 2 & 3 & 4 \\ \hline
2 & 1 & 4 & 3 \\ \hline
3 &&& \\ \hline
4 &&& \\ \hline
\end{array} \quad
\begin{array}{|c|c|c|c|} \hline
1 & 2 & 3 & 4 \\ \hline
2 & 4 & 1 & 3 \\ \hline
3 &&& \\ \hline
4 &&& \\ \hline
\end{array}
\end{equation}
第2行の第2~4列が(3, 4, 1)の場合、残りのマスの並べ方は唯1つに定まります。
\begin{array}{|c|c|c|c|} \hline
1 & 2 & 3 & 4 \\ \hline
2 & 3 & 4 & 1 \\ \hline
3 & 4 & 1 & 2 \\ \hline
4 & 1 & 2 & 1 \\ \hline
\end{array}
第2行の第2~4列が(1, 4, 3)の場合、第2列が一意に定まります。
\begin{array}{|c|c|c|c|} \hline
1 & 2 & 3 & 4 \\ \hline
2 & 1 & 4 & 3 \\ \hline
3 & 4 && \\ \hline
4 & 3 && \\ \hline
\end{array}
空白には1, 2が入りますが、入れ方は2通りです。
第2行の第2~4列が(4, 1, 3)の場合も、残りのマスは以下のように1通りに定まります。
\begin{array}{|c|c|c|c|} \hline
1 & 2 & 3 & 4 \\ \hline
2 & 4 & 1 & 3 \\ \hline
3 & 1 & 4 & 2 \\ \hline
4 & 3 & 2 & 1 \\ \hline
\end{array}
上記1、2項の並べ方それぞれに対し、残りのマスの並べ方は4通りとなります。
まとめ
以上より、どの行にもどの列にも同じ数字が1回しか現れない入れ方は、
\begin{equation}
4! \times 3! \times (1+2+1) = (4!)^2 = 576
\end{equation}通りとなります。
