ラテン方格

提供: miniwiki
移動先:案内検索

ラテン方格(ラテンほうかく、Latin square)とは nn 列の表に n 個の異なる記号を、各記号が各行および各列に1回だけ現れるように並べたものである。ラテン方陣(ラテンほうじん)ともいう。例を示す:

[math] \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \\ \end{bmatrix} \quad\quad \begin{bmatrix} a & b & d & c \\ b & c & a & d \\ c & d & b & a \\ d & a & c & b \end{bmatrix} [/math]

ラテン方格は数学的には擬群の積表と見ることができる。

ラテン方格は実験計画法に応用される。またペンシルパズルの一種「数独」や「賢くなるパズル」もラテン方格の応用である。

ラテン方格の名はオイラーによるもので、記号としてラテン文字(ローマ字)を用いたことによる。

ラテン方格は、第1行および第1列が自然な順序で並んでいる場合に標準形という。例えば上記1番のラテン方格は第1行と第1列がいずれも1,2,3であるから標準形である。どんなラテン方格も行、または列を交換することで標準形にできる。

記号には自然な順序がある(ない場合は適当に決めればよい)から、一般には1から始まる連続した数字(自然数)で書くのが便利である。

2次元のラテン方格をn次元に拡張した物をラテン超方格(Latin hypercube)という。これに基づく実験計画法をラテン超方格法Latin Hypercube Sampling; LHS)という。

直交配列表現

n × n ラテン方格の各マスを3つ組 (r,c,s) (ただし r は行、 c は列、 s は記号)で表現すると、 n2 組の3つ組が得られ、これを直交配列表現orthogonal array representationと呼ぶ。例えば上の1番目のラテン方格の直交配列表現は

{ (1,1,1),(1,2,2),(1,3,3),(2,1,2),(2,2,3),(2,3,1),(3,1,3),(3,2,1),(3,3,2) },

となる。ラテン方格は直交配列を用いて次のように定義できる:

  • (r,c,s) (ただし 1 ≤ r, c, sn )の形の n2 組の3文字組があり、
  • すべての (r,c) 、 (r,s) 、 (c,s) の形の対がそれぞれすべて異なる。

この表現法から、行、列、および記号は似た役割を持つことがわかる。

ラテン方格の同値類

ラテン方格に対するいろいろな操作(例えば上下あるいは左右の反転など)で別のラテン方格が作れる。

行、列、または記号を交換すれば、新しいラテン方格が作れる。これを最初のものに対してイソトピック (isotopic) であるという。イソトピックな関係(イソトピー、isotopy)は一種の同値関係であり、すべてのラテン方格は同値類(イソトピー類、isotopy classes)に分けることができる。

もう一つのタイプの操作は、直交配置表現を使うと簡単に表せる。各3つ組の中の3文字を系統的に並べ替えれば他のラテン方格が作れる。例えば、各3つ組(r,c,s)を(c,r,s)に並べ替え(これは対角線を中心にして行と列を反転すること)、あるいは各3つ組(r,c,s)を(c,s,r)に並べ替える(これはもっと複雑な操作)ことができる。このような操作は全部で(何もしないのを含めて)6つの可能性があり、これらで得られるラテン方格を基の方格に対して共役(conjugate または parastrophe)という。

これらの同値操作を2つ組み合わせることができる。2つのラテン方格の一方がもう一方の共役に対しイソトピックなとき、これらはパラトピック(paratopic または main class isotopic)という。これもやはり同値関係であって、この同値類は main classes、species、paratopy classes などという。各 main class は最高6のイソトピー類を含む。

関連項目