ラテン長方形

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

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

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 ]となる。}

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

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

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

け\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$ $\times$ $nのラテン長方形に$ $n - r$ 行を追加してラテン方陣を形成することができる。^[⁷^]

セミラテン方陣

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

例えば、位数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 ]で与えられます。}

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 となります。}

アプリケーション

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

参照

注記

^コルボーン & ディニッツ 2007、p. 141.
^ストーンズ 2010 .
^ブルアルディ 2010、385ページ
^ ^a ^b ^cデネスとキードウェル、1974 年、p. 150
^一部の著者、特に J. Riordan は、最初の列が順序どおりである必要はなく、これは以下で説明するいくつかの式の有効性に影響します。
^ ^a ^bコルボーン & ディニッツ 2007、p. 142
^ブルアルディ 2010、386ページ
^ ^a ^b ^cブルアルディ 2010、387ページ
^ ^a ^bブルアルディ 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日閲覧

[FOOTNOTEColbournDinitz2007p._141-1] コルボーン & ディニッツ 2007、p. 141.

[FOOTNOTEStones2010-2] ストーンズ 2010 .

[3] ブルアルディ 2010、385ページ

[DK150-4] デネスとキードウェル、1974 年、p. 150

[5] 一部の著者、特に J. Riordan は、最初の列が順序どおりである必要はなく、これは以下で説明するいくつかの式の有効性に影響します。

[CD142-6] コルボーン & ディニッツ 2007、p. 142

[7] ブルアルディ 2010、386ページ

[Bru387-8] ブルアルディ 2010、387ページ

[Bru388-9] ブルアルディ 2010、388ページ

[ 1 ]

[

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]となる。

[

[

[ 9 ]で与えられます。