数学A 完全順列･攪乱順列･モンモール数 問題 4 解説

方針・初手

まず、1行目と1列目を

$$ 1,2,3,4 $$

に固定した標準形を数える。その後、行と列の並べ替えで一般の場合へ戻す。

解法1

1行目と1列目がともに $1,2,3,4$ である入れ方を考える。すなわち、次の形に固定する。

$$ \begin{array}{cccc} 1&2&3&4\\ 2& & & \\ 3& & & \\ 4& & & \end{array} $$

このような標準形の個数を数える。

第2行は、先頭が $2$ なので、残りの3マスには $1,3,4$ が1回ずつ入る。また、各列で同じ数字が重複してはいけない。

第2行の候補のうち、列で重複しないものだけを残すと、次の3通りである。

$$ (2,1,4,3),\quad (2,3,4,1),\quad (2,4,1,3) $$

それぞれについて残りの行を決める。

（i） 第2行が $(2,1,4,3)$ のとき

$$ \begin{array}{cccc} 1&2&3&4\\ 2&1&4&3\\ 3& & & \\ 4& & & \end{array} $$

第2列は $2,1$ がすでにあるので、残りは $3,4$ である。第3行の先頭は $3$ だから、第3行第2列には $3$ は入れられない。よって第3行第2列は $4$、第4行第2列は $3$ である。

したがって、

$$ \begin{array}{cccc} 1&2&3&4\\ 2&1&4&3\\ 3&4& & \\ 4&3& & \end{array} $$

となる。第3列と第4列の残りはどちらも $1,2$ であり、第3行の残り2マスに $1,2$ を入れる方法は2通りある。それぞれ第4行は自動的に決まる。

よって、この場合は $2$ 通りである。

（ii） 第2行が $(2,3,4,1)$ のとき

$$ \begin{array}{cccc} 1&2&3&4\\ 2&3&4&1\\ 3& & & \\ 4& & & \end{array} $$

第4列には $4,1$ があるので、残りは $2,3$ である。第3行にはすでに先頭に $3$ があるから、第3行第4列は $2$ である。

第3列には $3,4$ があるので、残りは $1,2$ である。第3行第4列に $2$ が入ったため、第3行第3列は $1$ である。

すると第3行第2列は残りの $4$ となり、残りの第4行も一意に決まる。

$$ \begin{array}{cccc} 1&2&3&4\\ 2&3&4&1\\ 3&4&1&2\\ 4&1&2&3 \end{array} $$

よって、この場合は $1$ 通りである。

（iii） 第2行が $(2,4,1,3)$ のとき

$$ \begin{array}{cccc} 1&2&3&4\\ 2&4&1&3\\ 3& & & \\ 4& & & \end{array} $$

第2列には $2,4$ があるので、残りは $1,3$ である。第3行にはすでに先頭に $3$ があるから、第3行第2列は $1$ である。

第4列には $4,3$ があるので、残りは $1,2$ である。第3行第2列に $1$ が入ったため、第3行第4列は $2$ である。

すると第3行第3列は残りの $4$ となり、残りの第4行も一意に決まる。

$$ \begin{array}{cccc} 1&2&3&4\\ 2&4&1&3\\ 3&1&4&2\\ 4&3&2&1 \end{array} $$

よって、この場合は $1$ 通りである。

以上より、1行目と1列目を固定した標準形は

$$ 2+1+1=4 $$

通りである。

次に、標準形から一般の場合へ戻す。

任意の入れ方について、まず列を並べ替えれば、1行目を $1,2,3,4$ にできる。この並べ替え方は $4!$ 通りに対応する。

その後、1行目を固定したまま第2行から第4行を並べ替えれば、1列目の下3つの数字を自由に並べ替えられる。この並べ替え方は $3!$ 通りである。

したがって、全体の入れ方は

$$ 4\cdot 4!\cdot 3! $$

通りである。

計算すると、

$$ 4\cdot 24\cdot 6=576 $$

である。

解説

この問題は、$4\times 4$ のラテン方陣の個数を数える問題である。

直接すべてを数えようとすると場合分けが多くなるため、まず1行目と1列目を固定した標準形を数えるのが有効である。標準形では第2行の候補が大きく制限され、残りはほとんど列条件から自動的に決まる。

最後に $4!\cdot 3!$ を掛ける点が重要である。1行目を自由にする列の並べ替えが $4!$ 通り、1列目の下3つを自由にする行の並べ替えが $3!$ 通りである。

答え

$$ \boxed{576} $$