『ラテン方陣』

『ラテン方陣』解答

◆新潟県　加藤　英晴さんからの解答。

【問題１】

（１）

☆ ◆

◆ ☆

◆ ☆

☆ ◆

（２）

ａｂｃ

ｂｃａ

ｃａｂ

ａｂｃ

ｃａｂ

ｂｃａ

ａｃｂ

ｂａｃ

ｃｂａ

ａｃｂ

ｃｂａ

ｂａｃ

ｂａｃ

ａｃｂ

ｃｂａ

ｂａｃ

ｃｂａ

ａｃｂ

ｂｃａ

ａｂｃ

ｃａｂ

ｂｃａ

ｃａｂ

ａｂｃ

ｃａｂ

ａｂｃ

ｂｃａ

ｃａｂ

ｂｃａ

ａｂｃ

ｃｂａ

ａｃｂ

ｂａｃ

ｃｂａ

ｂａｃ

ａｃｂ

（３）

１２３４

２１４３

３４１２

４３２１

１２３４

２１４３

３４２１

４３１２

１２３４

２１４３

４３１２

３４２１

１２３４

２１４３

４３２１

３４１２

１２３４

２３４１

３４１２

４１２３

１２３４

２３４１

４１２３

３４１２

１２３４

２４１３

３１４２

４３２１

１２３４

２４１３

４３２１

３１４２

１２３４

３１４２

２４１３

４３２１

１２３４

３１４２

４３２１

２４１３

１２３４

３４１２

２１４３

４３２１

１２３４

３４１２

２３４１

４１２３

１２３４

３４１２

４１２３

２３４１

１２３４

３４１２

４３２１

２１４３

１２３４

３４２１

２１４３

４３１２

１２３４

３４２１

４３１２

２１４３

１２３４

３４２１

２１４３

４３１２

１２３４

３４２１

４３１２

２１４３

１２３４

４１２３

２３４１

３４１２

１２３４

４１２３

３４１２

２３４１

１２３４

４３１２

２１４３

３４２１

１２３４

４３１２

３４２１

２１４３

１２３４

４３２１

２１４３

３４１２

１２３４

４３２１

３４１２

２１４３

１行目の他の配列（あと４！－１）に対しても，それぞれこれと同じ数（２４）だけ種類があることは明らか（実際に挙げません（略））です。

【問題２】の解答

（１）

【問題１】の（２）の解答より，
｜L(３)｜＝１２

（２）

【問題１】の（３）の解答より，
｜L(４)｜＝４！×２４＝５７６

（３）

一般は，未解決の問題だったと思います。

｜L(ｎ)｜＝ｎ！(ｎ－１)！I_ｎと表せ，

I_１＝I_２＝I_３＝１，
I_４＝４
I_５＝５６
I_６＝９４０８
I_７＝１６９４２０８０だそうですが，
一般の　I_ｎについては，知られていないそうです。

【問題３】の解答

任意のｎに対して，L(ｎ)は生成可能です。

１行目が１　２　３　・・・・　ｎ　のものだけ生成すれば，
１行目の他の配列（あとｎ！－１）に対しても，文字の置換で，
それぞれ同じ数（(ｎ－１)！I_ｎ）ずつ生成できる。

ｎ次正方行列

ａ_１１ａ_１２・・・ａ_１ｎ

ａ_２１ａ_２２・・・ａ_２ｎ

：： … ：

ａ_ｎ１ａ_ｎ２・・・ａ_ｎｎ

を用意する。

(1)

１行目の１列目２列目・・・ｎ列目
２行目の１列目２列目・・・ｎ列目
・・・
ｎ行目の１列目２列目・・・ｎ列目

の順で決定する。

(2)

ａ_１１＝１ａ_１２＝２・・・ａ_１ｎ＝ｎ

(3)ａ_２１は，ａ_１１と異なるように決める。
ａ_２２は，ａ_１２とａ_２１と異なるように決める。
という具合に，各要素を決めるときは，その以左のどれとも，以上のどれとも同じにならないように選ぶ。

そう選べないときは，一つ前の要素の選び方を変える。
それでも選べないときは、その前の要素の選び方を変える。

各要素を決めるとき，以左のどれとも，以上のどれとも同じにならない数は何通りかあり，その選び方の違いが，生成される方陣の違いになる。
これで　しらみつぶせます。

（感想）

何だか，定義を言い換えただけのようなアルゴリズムで，無意味な気もします。

◆東京都　ぽこぺんさんからのコメント。

【加藤英晴さんの生成アルゴリズムに関するコメント】

(1) 第1行に対しては

　a_1j = j　（1≦j≦n）

のように決めますが，同時に，第1列に対しても

　a_i1 = i　（1≦i≦n）

と決めるべきです。

この二つの条件を満たす Latin 方陣の個数が，
問題２（３）の解答に書かれた I_n となります。

この条件を満たす各 Latin 方陣に対して，
その第2行～第n行を入れ替え ((n-1)!通り)，

さらに第1列～第n列を入れ替える (n!通り) ことにより，すべての Latin 方陣が漏れなく重複なく得られることはすぐわかります。

(2) 上記の二条件を満たす Latin 方陣を求めるには，単純なシラミ潰しではなく，攪乱順列（＝完全順列）を使うべきです。

すなわち，与えられた n に対して，

　p(j) ≠ j　（1≦j≦n）

を満たす攪乱順列 {p(j)} のすべての組をあらかじめ求めておきます。

この個数が

a(n) = n! ( 1
2! - 1
3! + 1
4! - 1
5! +- …+ (-1)ⁿ
n! )

であり， a(n)
n! → 1
e となることはよく知られています。

ここで，このすべての組を

　P_k = {{p(j)} | p(1) = k}　（2≦k≦n）

に分割しておき，Latin 方陣の第k行（2≦k≦n）を P_k から選ぶようにすれば，シラミ潰しの範囲を非常に狭めることができます。

明らかに |P₂| = ... = |P_n| ですから，

第k行（2≦k≦n）の選択肢は a(n)
n-1 通りずつあります。

したがって，

{ a(n)
n-1 } ^n-1 通り

だけを調べればいいというわけです。

　『ラテン方陣』へ

　数学の部屋へもどる

ａ_１１	ａ_１２	・・・	ａ_１ｎ
ａ_２１	ａ_２２	・・・	ａ_２ｎ
：	：	…	：
ａ_ｎ１	ａ_ｎ２	・・・	ａ_ｎｎ

ａ	ｂ	ｃ
ｂ	ｃ	ａ
ｃ	ａ	ｂ

ａ	ｂ	ｃ
ｃ	ａ	ｂ
ｂ	ｃ	ａ

ａ	ｃ	ｂ
ｂ	ａ	ｃ
ｃ	ｂ	ａ

ａ	ｃ	ｂ
ｃ	ｂ	ａ
ｂ	ａ	ｃ