ラテン方陣

組合せ論や実験計画法において、ラテン方陣とは 、 n 個の異なる記号が各行に 1 回ずつ、各列に 1 回ずつ出現するn  ×  n配列である 。3×3 のラテン方陣の例は次のようになる。

「ラテン方陣」という名前は、ラテン文字を記号として使用したレオンハルト・オイラー（1707-1783）の数学論文に触発されましたが、 ^{[2]任意の記号セットを使用できます。上記の例では、アルファベットのシーケンスA、B、Cは}整数シーケンス1、2、3 に置き換えることができます。オイラーはラテン方陣の一般理論を開始しました。

韓国の数学者チェ・ソクジョンは、レオンハルト・オイラーより67年も前の1700年に、魔方陣を構築するために9次のラテン方陣の例を初めて発表した人物である。 ^[3]

ラテン方陣は、最初の行と最初の列の両方が自然な順序になっている場合、簡約されている（または正規化されている、標準形式である）と言われます。 ^[4] たとえば、上記のラテン方陣は、最初の列がA、B、CではなくA、C、Bであるため、簡約されていません。

任意のラテン方陣は、行と列を並べ替える(つまり、順序を変更する)ことによって縮小できます。ここで、上記の行列の 2 行目と 3 行目を入れ替えると、次の方陣が得られます。

このラテン方陣は縮小されており、最初の行と最初の列はどちらもアルファベット順に A、B、C となっています。

n × nラテン方陣の各要素をr、c、s の3 つの組み合わせで表すと、rは行、cは列、s は記号であり、 n ²の 3 つの組み合わせの集合が得られます。この 3 つの組み合わせは、方陣の 直交表表現と呼ばれます。たとえば、ラテン方陣の直交表表現は次のようになります。

は

{ (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) }、

たとえば、3 つの数字 (2, 3, 1) は、行 2 と列 3 に記号 1 があることを意味します。直交表は通常、3 つの数字が行である配列形式で記述されます。たとえば、次のようになります。

ラテン方陣の定義は、直交表で表すことができます。

• ラテン方陣は、 n ²個の 3 つ組 ( r、c、s ) の集合です。ここで、 1 ≤ r、c、s ≤ nであり、すべての順序付きペア ( r、c ) は異なり、すべての順序付きペア ( r、s ) は異なり、すべての順序付きペア ( c、s ) は異なります。

これは、 n ^{2 の}順序付きペア ( r、c ) は、 1 ≤ i、j ≤ nを満たすすべてのペア ( i、j ) がそれぞれ 1 回ずつであることを意味します。 順序付きペア ( r、s ) と順序付きペア ( c、s )についても同様です。

直交表表現では、行、列、シンボルがかなり似た役割を果たしていることが示されており、これは以下で明らかになります。

ラテン方陣に対する多くの操作により、別のラテン方陣が生成されます (たとえば、上下を反転するなど)。

ラテン方陣の行、列、または記号の名前を並べ替えると、最初の方陣と同位であると言われる新しいラテン方陣が得られます。同位性は同値関係であるため、すべてのラテン方陣の集合は同位体クラスと呼ばれるサブセットに分割され、同じクラスの 2 つの方陣は同位体であり、異なるクラスの 2 つの方陣は同位体ではありません。

別の種類の操作は、ラテン方陣の直交表表現を使用して説明するのが最も簡単です。各 3 つの要素を体系的かつ一貫して並べ替えると (つまり、配列形式で 3 つの列を並べ替えると)、別の直交表 (つまり、別のラテン方陣) が得られます。たとえば、各 3 つの要素 ( r、c、s ) を ( c、r、s ) に置き換えることができます。これは、正方形を転置する (その主対角線について反転する) ことに対応します。または、各 3 つの要素 ( r、c、s ) を ( c、s、r ) に置き換えることもできます。これはより複雑な操作です。全部で 6 つの可能性があり、「何もしない」も含めると、元の正方形の共役 (パラストロフとも呼ばれる) と呼ばれる 6 つのラテン方陣が得られます。^[5]

最後に、これら 2 つの同値演算を組み合わせることができます。2 つのラテン方陣は、一方が他方の共役と同位体である場合、パラトピック、またはメインクラス同位体であると言われます。これも同値関係であり、同値クラスはメインクラス、種、またはパラトピッククラスと呼ばれます。^[5]各メインクラスには、最大 6 つの同位体クラスが含まれます。

記号1、2、…、nを持つn × nのラテン方陣の数L _nに対する簡単に計算できる公式は知られていない。大きなnに対する最も正確な上限と下限は大きく離れている。1つの古典的な結果^[6]は、 $${\displaystyle \prod _{k=1}^{n}\left(k!\right)^{n/k}\geq L_{n}\geq {\frac {\left(n!\right)^ {2n}}{n^{n^{2}}}}.}$$

ラテン方陣の数に関する単純かつ明示的な公式は 1992 年に発表されました。しかし、項の数が指数関数的に増加するため、いまだに簡単には計算できません。n × n 個のラテン方陣の数 L n に関するこの公式は、 B n_が すべての_n × n { 0, 1} 行列の集合、σ ₀ ( A )が行列Aのゼロ要素の数、per( A )が行列Aのパーマネントである場合に、次の式で表されます。^[7]$${\displaystyle L_{n}=n!\sum _{A\in B_{n}}^{}(-1)^{\sigma _{0}(A)}{\binom {\operatorname {per} A}{n}},}$$

下の表には、既知の正確な値がすべて含まれています。数値が非常に急速に増加していることがわかります。各nについて、ラテン方陣の合計数 ( OEISのシーケンスA002860 ) は、縮小ラテン方陣の数 ( OEISのシーケンスA000315 ) のn ! ( n − 1)!倍です。

各nに対して、各同位体クラス ( OEISのシーケンスA040082 ) には最大( n !) ^{3 個の}ラテン方陣が含まれ (正確な数は異なります)、各メインクラス ( OEISのシーケンスA003090 ) には 1、2、3、または 6 個の同位体クラスが含まれます。

n = 1 から 7 までの構造的に異なるラテン方陣 (つまり、回転、反転、および/または記号の順列によって方陣を同一にすることができない方陣) の数は、それぞれ 1、1、1、12、192、145164、1524901344 です ( OEISのシーケンスA264603 )。

各主要クラスから 5 次までのラテン方陣の例を 1 つずつ示します。

${\displaystyle {\begin{bmatrix}1\end{bmatrix}}\quad {\begin{bmatrix}1&2\\2&1\end{bmatrix}}\quad {\begin{bmatrix}1&2&3\\2&3&1\\3&1&2\end{bmatrix}}}$

${\displaystyle {\begin{bmatrix}1&2&3&4\\2&1&4&3\\3&4&1&2\\4&3&2&1\end{bmatrix}}\quad {\begin{bmatrix}1&2&3&4\\2&4&1&3\\3&1&4&2\\4&3&2&1\end{bmatrix}}}$

${\displaystyle {\begin{bmatrix}1&2&3&4&5\\2&3&5&1&4\\3&5&4&2&1\\4&1&2&5&3\\5&4&1&3&2\end{bmatrix}}\quad {\begin{bmatrix}1&2&3&4&5\\2&4&1&5&3\\3&5&4&2&1\\4&1&5&3&2\\5&3&2&1&4\end{bmatrix}}}$

それぞれ、次のグループの掛け算表を示します。

• {0} – 自明な 1 要素群
• ${\displaystyle \mathbb {Z} _{2}}$–バイナリグループ
• ${\displaystyle \mathbb {Z} _{3}}$–位数 3 の巡回群
• ${\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{2}}$–クラインの4群
• ${\displaystyle \mathbb {Z} _{4}}$– 位数 4 の巡回群
• ${\displaystyle \mathbb {Z} _{5}}$– 位数 5 の巡回群
• 最後のものは、結合性のない準群、またはループの例です。

ラテン方陣の横断線はn 個のセルの選択であり、各行には 1 つのセルが含まれ、各列には 1 つのセルが含まれ、各シンボルには 1 つのセルが含まれます。

ラテン方陣は、行が一方の頂点、列がもう一方の頂点、各セルが（行と列の間の）辺、シンボルが色である完全な二部グラフと考えることができます。ラテン方陣の規則は、これが適切な辺の色付けであることを意味します。この定義では、ラテン横断は各辺が異なる色を持つマッチングであり、このようなマッチングはレインボーマッチングと呼ばれます。

そのため、ラテン方陣/ラテン長方形に関する多くの結果は、タイトルに「レインボーマッチング」という用語が含まれる論文に含まれており、その逆も同様です。^[8]

ラテン方陣の中には横断線を持たないものもあります。例えば、nが偶数のとき、セルi , jの値が( i + j ) mod nであるn行n列のラテン方陣には横断線がありません。以下に2つの例を示します。1967年、HJ Ryserは、 nが奇数のとき、すべてのn行n列のラテン方陣には横断線があると推測しました。 ^[9]$${\displaystyle {\begin{bmatrix}1&2\\2&1\end{bmatrix}}\quad {\begin{bmatrix}1&2&3&4\\2&3&4&1\\3&4&1&2\\4&1&2&3\end{bmatrix}}}$$

1975年、SKスタインとブルーディは、nが偶数のとき、すべてのn行n列のラテン方陣にはサイズn −1の部分横断線が存在すると予想した。^[10]

スタインのより一般的な予想は、 n −1の大きさの横断線はラテン方陣だけでなく、各記号が正確にn回出現する限り、 n行n列のn個の記号の配列にも存在するというものである。^[9]

これらの推測のより弱いバージョンがいくつか証明されています。

• すべてのn行n列のラテン方陣には、大きさが2n /3の部分横断線が存在する。 ^[11]
• すべてのn行n列のラテン方陣には、大きさn −sqrt( n )の部分横断線が存在する。^[12]
• すべてのn行n列のラテン方陣には、 n − 11 logの大きさの部分横断線が存在する。²
  ₂（名詞）^[13]
• すべてのn行n列のラテン方陣には、大きさn − O(log n/loglog n)の部分横断線が存在する。 ^[14]
• 十分に大きいn行n列のラテン方陣には必ずn −1の大きさの部分横断線が存在する。^[15] (プレプ​​リント)

小さな正方形の場合、順列を生成し、ラテン方陣の性質が満たされているかどうかをテストすることができます。より大きな正方形の場合、ジェイコブソンとマシューズのアルゴリズムにより、n  ×  nのラテン方陣の空間上の均一分布からサンプリングすることができます。^[16]

• 実験計画法において、ラテン方陣は2つのブロック因子に対する行-列計画法の特殊なケースである。^{[17] [18]}
• 代数学において、ラテン方陣は群の一般化と関連しており、特にラテン方陣は準群の乗算表（ケーリー表）として特徴付けられる。値の表がラテン方陣を形成する二項演算は、ラテン方陣の性質に従うと言われる。

互いに直交するラテン方陣の集合は、電力線を介してブロードバンドインターネットを送信しようとするときなど、単純なホワイトノイズ以外の種類のノイズによって通信が妨害される状況での誤り訂正符号として応用されている。^{[19] [20] [21]}

まず、メッセージは複数の周波数、つまりチャネルを使用して送信されます。これは、信号が特定の周波数でノイズの影響を受けにくくする一般的な方法です。送信するメッセージ内の文字は、一連の信号を連続した時間間隔で異なる周波数で送信することでエンコードされます。以下の例では、文字 A から L は、4 つの異なる周波数で 4 つの時間スロットで信号を送信することでエンコードされます。たとえば、文字 C は、最初に周波数 3、次に周波数 4、1、2 で送信することでエンコードされます。

$${\displaystyle {\begin{matrix}A\\B\\C\\D\\\end{matrix}}{\begin{bmatrix}1&2&3&4\\2&1&4&3\\3&4&1&2\\4&3&2&1\\\end{bmatrix}}\quad {\begin{matrix}E\\F\\G\\H\\\end{matrix}}{\begin{bmatrix}1&3&4&2\\2&4&3&1\\3&1&2&4\\4&2&1&3\\\end{bmatrix}}\quad {\begin{matrix}I\\J\\K\\L\\\end{matrix}}{\begin{bmatrix}1&4&2&3\\2&3&1&4\\3&2&4&1\\4&1&3&2\\\end{bmatrix}}}$$

12 文字のエンコードは、互いに直交する 3 つのラテン方陣から構成されます。ここで、送信中にチャネル 1 と 2 にノイズが加わったと想像してください。文字 A は次のように認識されます。 $${\displaystyle {\begin{matrix}12&12&123&124\end{matrix}}}$$

つまり、最初のスロットでは周波数 1 と周波数 2 の両方から信号を受信し、3 番目のスロットでは周波数 1、2、3 からの信号を受信します。ノイズのため、最初の 2 つのスロットが 1,1 だったのか、1,2 だったのか、2,1 だったのか、2,2 だったのかはわかりません。ただし、1,2 の場合のみ、上記の表の文字 (文字 A) に一致するシーケンスが生成されます。同様に、3 番目のスロットのすべての周波数でノイズのバーストが発生すると想像できます。 $${\displaystyle {\begin{matrix}1&2&1234&4\end{matrix}}}$$

再び、エンコード表から、送信されていたのは文字 A だったに違いないと推測できます。このコードが検出できるエラーの数は、タイムスロットの数より 1 つ少ないです。また、周波数の数が素数または素数の累乗である場合、直交ラテン方陣によって、可能な限り効率的なエラー検出コードが生成されることが証明されています。

部分的に埋められた正方形を完成させてラテン方陣を形成できるかどうかを判断する問題はNP完全である。^[22]

人気の高い数独パズルはラテン方陣の特殊なケースです。数独パズルの解はすべてラテン方陣です。数独では、9 つ​​の特定の 3×3 の隣接するサブスクエアにも 1 ～ 9 の数字が含まれていなければならないという追加の制約があります (標準バージョンの場合)。「数独の数学」も参照してください。

最近のKenKenパズルやStrimkoパズルもラテン方陣の例です。

ラテン方陣は、人気の高い抽象戦略ゲーム「カミサド」をはじめ、さまざまなボードゲームの基礎として使用されてきました。

ラテン方陣は、実験誤差を最小限に抑えるために農業研究実験の設計に使用されます。^[23]

ラテン方陣はカナダ統計学会の紋章にも使われており^[24]、その紋章にも明記されている。また、国際生体測定学会のロゴにも使われている^[25]。

• ラテン長方形は、ラテン方陣を一般化したものであって、n列とn 個の可能な値がありますが、行の数はnより少なくなる場合があります。各値は、各行と各列に最大で 1 回表示されます。
• グレコ・ラテン方陣は、2 つのラテン方陣のペアであり、一方を他方の上に置くと、順序付けられた記号の各ペアが正確に 1 回表示されます。
• ラテン超方陣は、ラテン方陣を 2 次元から多次元に一般化したものです。

• ブロックデザイン
• 組み合わせ設計
• 8つのクイーンのパズル
• ふとしき
• 魔方陣
• ラテン方陣の問題
• ルークのグラフ、ラテン方陣を色付けしたグラフ
• サトール広場
• ヴェーダの広場
• 単語の広場

• Bailey, RA (2008)。「6 つの行と列のデザインと 9 つのラテン方陣について」。比較実験のデザイン。ケンブリッジ大学出版局。ISBN 978-0-521-68357-9. MR  2422352。
• デネス、J.; キードウェル、AD (1974)。ラテン方陣とその応用。ニューヨーク・ロンドン：アカデミック・プレス。p. 547。ISBN 0-12-209350-X. MR  0351850。
• Shah, Kirti R.; Sinha, Bikas K. (1989)。「4 行列設計」。最適設計の理論。統計学の講義ノート。第 54 巻。Springer-Verlag。66 ～ 84 ページ。ISBN 0-387-96991-8MR  1016151 。
• van Lint, JH; Wilson, RM (1992). A Course in Combinatorics . Cambridge University Press. p. 157. ISBN 0-521-42260-4。

• Dénes, JH; Keedwell, AD (1991).ラテン方陣: 理論と応用における新しい展開. Annals of Discrete Mathematics. Vol. 46. Paul Erdős (序文). アムステルダム: Academic Press. ISBN 0-444-88899-3. MR  1096296。
• Hinkelmann, Klaus; Kempthorne, Oscar (2008)。実験の設計と分析。第 I 巻、第 II 巻 (第 2 版) 。Wiley。ISBN 978-0-470-38551-7MR  2363107 。
  • Hinkelmann, Klaus; Kempthorne, Oscar (2008)。実験のデザインと分析、第 1 巻: 実験デザイン入門 (第 2 版) 。Wiley。ISBN 978-0-471-72756-9MR  2363107 。
  • Hinkelmann, Klaus; Kempthorne, Oscar (2005)。実験のデザインと分析、第 2 巻: 高度な実験デザイン (初版) 。Wiley。ISBN 978-0-471-55177-5MR  2129060 。
• Knuth, Donald (2011)。『コンピュータプログラミングの技法』第4A巻: 組み合わせアルゴリズム、パート1。マサチューセッツ州レディング: Addison- Wesley。ISBN 978-0-201-03804-0。
• Laywine, Charles F.; Mullen, Gary L. (1998)ラテン方陣を用いた離散数学. Wiley-Interscience Series in Discrete Mathematics and Optimization. ニューヨーク: John Wiley & Sons, Inc. ISBN 0-471-24064-8. MR  1644242。
• Shah, KR; Sinha, Bikas K. (1996)。「行-列デザイン」。S. Ghosh およびCR Rao (編)。実験のデザインと分析。統計ハンドブック。第 13 巻。アムステルダム: North-Holland Publishing Co.、pp. 903–937。ISBN 0-444-82061-2. MR  1492586。
• ラガヴァラオ、ダマラジュ(1988)。実験計画法における構成と組み合わせ問題(1971 年 Wiley 版の訂正版)。ニューヨーク: ドーバー。ISBN 0-486-65685-3. MR  1102899。
• ストリート、アン・ペンフォールド;ストリート、デボラ・J. (1987)。実験計画の組合せ論。ニューヨーク：オックスフォード大学出版局。ISBN 0-19-853256-3. MR  0908490。
• Berger, Paul D.; Maurer, Robert E.; Celli, Giovana B. (2017年11月28日)。実験デザインと経営、工学、科学への応用 (第2版 (2017年11月28日) 編集)。Springer。pp. 267–282。

• Weisstein、Eric W.「ラテン方陣」。MathWorld。
• 数学百科事典におけるラテン方陣
• 整数列のオンライン百科事典におけるラテン方陣