ラテン長方形

組合せ数学において、ラテン長方形はr  ×  n行列（r  ≤  n）であり、 n個の記号（通常は1、2、3、...、  nまたは0、1、...、n − 1 ）を要素として持ち、どの行や列にも同じ数字が複数回出現しない行列である。^{[ 1 ]}

n × n の ラテン 長方形はラテン方陣と呼ばれる。ラテン長方形とラテン方陣は、ルークグラフの最適彩色、あるいは完全二部グラフの最適辺彩色とも呼ばれる。^{[ 2 ]}

3×5のラテン長方形の例は次の通りである: ^{[ 3 ]}

0	1	2	3	4
3	4	0	1	2
4	0	3	2	1

正規化

ラテン長方形は、その最初の行と最初の列が自然な順序になっている場合、正規化（または縮小）されていると呼ばれます。 ^{[ 4 ] [ 5 ]}

上記の例は正規化されていません。

列挙

L ( k, n ) を正規化されたk × nラテン長方形の数とすると、 k × nラテン長方形の総数は^{[ 6 ]となる。}

${\displaystyle {\frac {n!(n-1)!L(k,n)}{(nk)!}}.}$

2 × n のラテン長方形は、不動点を持たない順列に対応する。このような順列は不一致順列と呼ばれている。^{[ 4 ]}与えられた順列と一致しない順列の列挙は、有名な「巡り合わせ問題」である。一方が他方の単純な巡回シフトであるような2つの順列と一致しない順列の列挙は、「縮約されたメネジャージュ問題」として知られている。^{[ 4 ]}

小さいサイズの正規化ラテン長方形の数L ( k , n )は^{[ 6 ]}で与えられる。

け\n	1	2	3	4	5	6	7	8
1	1	1	1	1	1	1	1	1
2		1	1	3	11	53	309	2119
3			1	4	46	1064	35792	1673792
4				4	56	6552	1293216	420909504
5					56	9408	11270400	27206658048
6						9408	16942080	335390189568
7							16942080	535281401856
8								535281401856

k = 1、つまり行が1つしかない場合、ラテン方陣は正規化されているため、この行が何になるかは選択できません。表はまた、 L ( n − 1, n ) = L ( n , n )であることも示しています。これは、1行だけが欠けている場合、各列の欠けているエントリはラテン方陣の性質から決定でき、方陣はラテン方陣に一意に拡張できるためです。

拡張性

前述のラテン長方形から1行を省略してラテン方陣に拡張できるという性質は、大幅に強化される。すなわち、r  <  nならば、ホールの結婚定理を用いて、 r  ×  nのラテン長方形にn  −  r行を追加してラテン方陣を形成することができる。^{[ 7 ]}

セミラテン方陣

半ラテン方陣は不完全ラテン方陣の別の種類である。半ラテン方陣はn × nの配列Lであり、一部の位置は空いており、他の位置は整数{0, 1, ..., n − 1 }のいずれかで占められている。Lに整数kが出現する場合、それはn回出現し、2つのkは同じ行または列には属さない。Lにm個の異なる整数が出現する場合、Lのインデックスはmである。^{[ 8 ]}

例えば、位数5、指数3の半ラテン方陣は次のようになる。^{[ 8 ]}

1		0		2
	2	1		0
0	1		2
2	0		1
		2	0	1

n位、 m指数の半ラテン方陣は、nm 個の埋められた位置を持ちます。ここで疑問が生じます。半ラテン方陣はラテン方陣に完成できるでしょうか？ 少々意外ですが、答えは常に「完成」です。

Lをn位、添字mの半ラテン方陣とする（ただしm < n）。すると、Lはラテン方陣に完成できる。^{[ 8 ]}

これを証明する一つの方法は、 n位数で添字mの半ラテン方格がm × nのラテン長方形と等価であることを観察することです。L = || a _ij ||をラテン長方形、S = || b _ij ||を半ラテン方格とすると、等価性は^{[ 9 ]で与えられます。}

${\displaystyle b_{ij}=k{\text{ }}a_{kj}=i のときのみ。}$

例えば、3×5のラテン長方形

0	1	2	3	4
3	4	1	0	2
1	0	4	2	3

は、次の5次指数3の半ラテン方陣と同等である：^{[ 9 ]}

0	2		1
2	0	1
		0	2	1
1			0	2
	1	2		0

たとえば、ラテン長方形ではa ₁₀ = 3 なので、半ラテン方陣では b _{30 = 1 となります。}

アプリケーション

統計学では、ラテン長方形は実験の設計に応用されています。

参照

• 組み合わせ設計
• レインボーマッチング

注記

1. コルボーン & ディニッツ 2007、p. 141.
2. ストーンズ 2010 .
3. ブルアルディ 2010、385ページ
4. デネスとキードウェル、1974 年、p. 150
5. 一部の著者、特に J. Riordan は、最初の列が順序どおりである必要はなく、これは以下で説明するいくつかの式の有効性に影響します。
6. コルボーン & ディニッツ 2007、p. 142
7. ブルアルディ 2010、386ページ
8. ブルアルディ 2010、387ページ
9. ブルアルディ 2010、388ページ

参考文献

• Brualdi, Richard A. (2010)、Introductory Combinatorics (第5版)、Prentice Hall、ISBN 978-0-13-602040-0
• コルボーン、チャールズ・J.; ディニッツ、ジェフリー・H. (2007)、『コンビナトリアルデザインハンドブック（第2版）』ボカラトン：チャップマン＆ホール/CRC、ISBN 978-1-58488-506-1
• デネス、J.; キードウェル、AD (1974)、「ラテン方陣とその応用」、ニューヨーク・ロンドン：アカデミック・プレス、p. 547、ISBN 0-12-209350-X、MR  0351850
• ストーンズ、ダグラス・S.（2010）、「ラテン長方形の数に関する多くの公式」、電子組合せ論ジャーナル、17（1）：記事1、46、doi：10.37236/487、MR  2661404

さらに読む

• ミルスキー、L.（1971）、横断理論：組み合わせ数学のいくつかの側面の説明、アカデミックプレス、ISBN 0-12-498550-5、OCLC  816921720
• リオダン、ジョン（2002）[1958]、組み合わせ分析入門、ドーバー、ISBN 978-0-486-42536-8

外部リンク

• ワイスタイン、エリック・W.、「ラテン長方形」、mathworld.wolfram.com 、 2020年7月12日閲覧