4×4のラテン方格の数え方

ラテン方格とは

ラテン方格とは、以下の表のことを言います。

ただし、条件があります。

・同じ列に同じ数字は入らない
・同じ行に同じ数字は入らない

これはあるパズルに似てますよね。

そう、ナンプレです。

ただ、ナンプレと違い、ブロック内に同じ数が入らない、という条件はないです。

この4×4のラテン方格の数え方がよくわからなかったので、ここにまとめたいと思います。

自分が犯したミス

自分は以下のように考えました。

1.まず1行目に1を入れ、次に2行目に1を入れ、3行目に1を入れ、最後に1を入れる。

この時のパターンは

$4×3×2×1 = 24$

2.次に、1行目の空いたマスに2を入れ、同じ列に1が入っていない行(下の表で言えば2行目か3行目)の空いたマスに2を入れる。

残りは自動的に2が入る。

この時のパターンは

$3×2 = 6$

3.最後に、空いたマスに3を入れると自動的に3が入る。

この時のパターンは

$2$

4.自動的に4が入る。

1.～4.から、4×4のラテン方格の総数は

$24×6×2 = 288$

どこが間違いか

しかし、上記は間違っています。

なぜなら、以下のパターンがあるからです。

この表の場合、1.2.までは正しいです。

この時、3を入れるパターンは

$2×2=4$

となります。

なので、上記の僕の考えは間違いとなります。

正しい計算方法

以下のPDFの「Why is so hard?」の章を参考にしましたが、英語でわかりづらかったので要約します。
Latin Squares

手順は以下の通りです。

1.まず1行目を埋める。

このときのパターンは

$4! = 4・3・2・1 = 24$

2.2行目を埋める時、パターンを(a b c d)の場合と、(a b)(c d)の場合に分ける。

例えば(1 2 3 4)は、1を2に、2を3に、3を4に、4を1にする置換を表します。

$σ=(1 2 3 4)$とすると

$σ(1)=2、σ(2)=3、σ(3)=4、σ(4)=1$

となるので、(1 2 3 4)の場合は

となります。

一方で(1 2)(3 4)は、1を2に、3を2する置換を表します。

$σ=(1 2 3 4)$とすると

$σ(1)=2、σ(2)=1、σ(3)=4、σ(4)=3$

となるので、(1 2)(3 4)の場合は

となります。

3.(a b c d)のパターン数を数える。
例えば(1 2 3 4)の場合は以下の通りでした。

この場合、例えば3行目の1列目か3列目に3を入れると、残りが自動で決まります。

他の(a b c d)のパターンも同じように考えます。

(a b c d)は

(1 2 3 4)、(1 2 4 3)、(1 3 2 4)、(1 3 4 2)、(1 4 2 3)、(1 4 3 2)

の6通りあるので

$6×2=12$

となります。

4.(a b)(c d)のパターンを数える。
例えば(1 2)(3 4)の場合は以下の通りでした。

この場合、例えば3行目の1列目か2列目に3を入れるので、2通りあります。

例えば、3行目の1列目に3を入れると、2列目が自動的に決まりますが、3列目、4列目がまだ決まりません。

ここでさらに2通りあります。

(a b)(c d)は

(1 2)(3 4)、(1 3)(2 4)、(1 4)(2 3)

の3通りあるので

$3×2×2=12$

となります。

5.1.-4.をまとめる。
まず、1.で24通りあり、3.4.でそれぞれ12通りずつあるので、4×4のラテン方格の総数は

24×(12+12) = 576

となります。