Latinský obdélník - Latin rectangle - Wikipedia

v kombinatorická matematika, a Latinský obdélník je $r \times n$ matice (kde $r \leq n$ ), použitím $n$ symboly, obvykle čísla $1, 2, 3, ..., n$ nebo $0, 1, ..., n - 1$ jako jeho položky, přičemž v žádném řádku nebo sloupci se počet nevyskytuje více než jednou.^[1]

An $n \times n$ Latinský obdélník se nazývá a Latinský čtverec.

Příkladem obdélníku 3 × 5 v latině je:^[2]

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

Normalizace

Říká se latinský obdélník normalizováno (nebo snížena) pokud je jeho první řádek v přirozeném pořadí, stejně jako jeho první sloupec.^[3]^[4]

Výše uvedený příklad není normalizován.

Výčet

Nechat $L$ ( $k, n$ ) označte počet normalizovaných $k$ × $n$ Latinské obdélníky. Poté celkový počet $k$ × $n$ Latinské obdélníky jsou^[5]

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

2 × $n$ Latinský obdélník odpovídá a permutace bez č pevné body. Takové permutace byly nazývány nesouhlasné obměny.^[3] Slavný je výčet permutací nesouhlasících s danou permutací problème des rencontres. Výčet permutací nesouhlasných se dvěma permutacemi, z nichž jedna je prostým cyklickým posunem druhé, je známý jako redukovaný problème des ménages.^[3]

Počet normalizovaných latinských obdélníků, $L (k, n)$ , malých velikostí je dáno^[5]

k 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

Když $k$ = 1, to znamená, že existuje pouze jeden řádek, protože latinské obdélníky jsou normalizovány, není možné zvolit, čím tento řádek může být. To ukazuje také tabulka $L (n - 1, n) = L (n, n)$ , který následuje, protože pokud chybí pouze jeden řádek, lze chybějící údaj v každém sloupci určit z Vlastnost latinského čtverce a obdélník lze jedinečně rozšířit na latinský čtverec.

Rozšiřitelnost

Vlastnost možnosti rozšířit latinský obdélník, který chybí o jeden řádek na výše uvedený latinský čtverec, lze výrazně posílit. Jmenovitě, pokud $r < n$ , pak je možné připojit $n - r$ řádky do $r \times n$ Latinský obdélník pro vytvoření latinského čtverce pomocí Hallova věta o manželství.^[6]

Pololatinské čtverce

Semilatinský čtverec je další typ neúplného latinského čtverce. A semi-latinský čtverec je $n$ × $n$ pole, $L$ , ve kterých jsou některé pozice neobsazené a jiné pozice jsou obsazeny jedním z celých čísel ${0, 1, ..., n - 1$ }, takový, že pokud je celé číslo $k$ se vyskytuje v $L$ , pak k tomu dojde $n$ krát a žádné dva $k$ patří do stejného řádku nebo sloupce. Li $m$ různá celá čísla se vyskytují v $L$ , pak $L$ má index $m$ .^[7]

Například semi-latinský čtverec řádu 5 a indexu 3 je:^[7]

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

Pololatinský čtverec řádu $n$ a index $m$ budu mít $nm$ obsazené pozice. Vyvstává otázka, je možné doplnit pololatinský čtverec na latinský čtverec? Odpověď je poněkud překvapivá vždy.

Nechat $L$ být semi-latinským čtvercem řádu $n$ a index $m$ , kde $m . Pak L lze doplnit na latinský čtverec. [7]$

Jedním ze způsobů, jak to dokázat, je pozorovat semi-latinský čtverec řádu $n$ a index $m$ je ekvivalentní s $m$ × $n$ Latinský obdélník. Nechat $L = || A ij ||$ být latinský obdélník a $S = || b ij ||$ být semi-latinský čtverec, pak je ekvivalence dána^[8]

{ displaystyle b_ {ij} = k { text {když a jen když}} a_ {kj} = i.}

Například latinský obdélník 3 × 5

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

je ekvivalentní tomuto semi-latinskému čtverci řádu 5 a indexu 3:^[8]

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

protože například $A$ ₁₀ = 3 v latinském obdélníku $b$ ₃₀ = 1 na semi-latinském čtverci.

Aplikace

v statistika, Latinské obdélníky mají aplikace v návrh experimentů.

Viz také

Poznámky

^ Colbourn & Dinitz 2007, str. 141
^ Brualdi 2010, str. 385
^ ^A ^b ^C Denes & Keedwell 1974, str. 150
^ Někteří autoři, zejména J. Riordan, nevyžadují pořadí prvního sloupce, což ovlivní platnost některých níže uvedených vzorců.
^ ^A ^b Colbourn & Dinitz 2007, str. 142
^ Brualdi 2010, str. 386
^ ^A ^b ^C Brualdi 2010, str. 387
^ ^A ^b Brualdi 2010, str. 388

Reference

Brualdi, Richard A. (2010), Úvodní kombinatorika (5. vydání), Prentice Hall, ISBN 978-0-13-602040-0
Colbourn, Charles J .; Dinitz, Jeffrey H. (2007), Příručka kombinatorických vzorů (2. vyd.), Boca Raton: Chapman & Hall / CRC, ISBN 1-58488-506-8
Dénes, J .; Keedwell, A. D. (1974), Latinské čtverce a jejich aplikace, New York-Londýn: Academic Press, s. 547, ISBN 0-12-209350-X, PAN 0351850

Další čtení

Mirsky, L. (1971), Transverzální teorie: popis některých aspektů kombinatorické matematiky Akademický tisk, ISBN 0-12-498550-5, OCLC 816921720
Riordan, John (2002) [1958], Úvod do kombinatorické analýzyDover, ISBN 978-0-486-42536-8

externí odkazy

Weisstein, Eric W., „Latin Rectangle“, mathworld.wolfram.com, vyvoláno 2020-07-12

[1] Colbourn & Dinitz 2007, str. 141

[2] Brualdi 2010, str. 385

[DK150-3] A ^b ^C Denes & Keedwell 1974, str. 150

[4] Někteří autoři, zejména J. Riordan, nevyžadují pořadí prvního sloupce, což ovlivní platnost některých níže uvedených vzorců.

[CD142-5] A ^b Colbourn & Dinitz 2007, str. 142

[6] Brualdi 2010, str. 386

[Bru387-7] A ^b ^C Brualdi 2010, str. 387

[Bru388-8] A ^b Brualdi 2010, str. 388

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]