Kombinatorikus séma

A kombinatorikus sémák elmélete a kombinatorika (a matematika egyik ága ) része, amely olyan véges halmazok családjainak létezését, felépítését és tulajdonságait veszi figyelembe, amelyek szerkezete kielégíti az egyensúly és/vagy szimmetria általános fogalmait . Ezek a fogalmak nincsenek pontosan definiálva, így az objektumok széles köre felfogható kombinatorikus sémaként. Tehát az egyik esetben a kombinatorikus sémák számhalmazok metszéspontjait ábrázolhatják, mint a folyamatábrákban , egy másik esetben pedig a Sudoku elemeinek elrendezését .

A kombinatorikus sémák elmélete felhasználható a kísérletek tervezésében . Néhány alapvető kombinatorikus séma megtalálható Ronald Fishernek a biológiai kísérletek elméletéről szóló munkájában. A kombinatorikus sémák ma már számos területen megtalálhatók, beleértve a véges geometriát , a versenyek ütemezését , a lottójátékokat , a matematikai biológiát , az algoritmusok tervezését és elemzését , a számítógépes hálózatokat , a csoportos tesztelést és a kriptográfiát [1] .

Definíció

Jelölje - az elemek halmaza . Tekintsük ennek a halmaznak a részhalmazait . Mindegyik részhalmazt blokknak nevezzük, a benne lévő halmazelemek számát pedig a blokk térfogatának, és jelöléssel jelöljük . Legyen az ezt az elemet tartalmazó részhalmazok száma . Az ismétlések számát (rendezetlen párok) a következővel jelöljük . Ekkor a blokkhalmaz egy kombinatorikus sémát (vagy blokkdiagramot) alkot [2] paraméterekkel . $v$ ${\displaystyle m_{1},m_{2},...,m_{v))$ ${\displaystyle M_{1},M_{2},...,M_{b))$ ${\displaystyle M_{j))$ ${\displaystyle M_{j))$ ${\displaystyle k_{j))$ ${\displaystyle r_{i))$ $M$ $\lambda _{p}$ ${\displaystyle M_{1},M_{2},...,M_{b))$ ${\displaystyle v,b,r_{i},k_{j},\lambda _{p))$

Példa

Ha n ember van, lehet-e belőlük halmazokat alkotni úgy, hogy minden ember legalább egy halmazba tartozzon, minden pár pontosan egy halmazhoz tartozik, minden két halmazban csak egy személy van a metszéspontban, és egyik halmaz sem áll az összes ember közül az összes ember mínusz egy vagy pontosan egy személy? A válasz n -től függ .

A válasz csak akkor igen, ha n q 2 + q + 1 alakú . Nehezebb bizonyítani a megoldás létezését, ha q prímhatvány . Van egy olyan sejtés, hogy nincs más megoldás. Bebizonyosodott, hogy ha q -re létezik olyan megoldás, amely 1 vagy 2 modulo 4-gyel egybevágó, akkor q két tökéletes négyzet összege . Ezt az eredményt, a Brook-Reiser-Chowl-tételt véges mezőkön és másodfokú alakzatokon alapuló konstrukciós módszerek kombinációjával igazolták .

Ha létezik ilyen szerkezet, véges projektív síknak nevezzük . Ez azt mutatja, hogy a véges geometriák elmélete és a kombinatorika hogyan keresztezi egymást. q = 2 esetén a projektív síkot Fano-síknak nevezzük .

Történelem

A kombinatorikus sémák már az ókorban ismertek a Lo Shu tér formájában, amely a varázstér korai változata volt . A kombinatorikus sémák a 18. század óta a kombinatorika fejlődésével együtt fejlődtek ki , például latin négyzetek formájában a 18. században és Steiner rendszerek formájában a 19. században. A kombinatorikus sémák a szórakoztató matematikában is népszerűek , mint például Kirkman iskoláslány-problémája (1850), és gyakorlati problémák, például körmérkőzéses versenyek ütemezése (az 1880-as években megjelent megoldás). A 20. században a kombinatorikus sémákat alkalmazták kísérletek , véges geometriák és kapcsolatsémák tervezésére, és ez az algebrai statisztika megjelenéséhez vezetett .

Alapvető kombinatorikus sémák

A kombinatorikus sémák témakörének klasszikus magja a kiegyensúlyozott hiányos blokktervezés (en: Balanced Incomplete Block Design, BIBD), mátrixok és Hadamard-sémák , szimmetrikus BIBD , latin négyzetek , feloldható BIBD , különbséghalmazok és páronkénti kiegyensúlyozott sémák köré épül. (hu: Pairwise Balanced Design , PBD) [3] . Más kombinatorikus sémák a felsorolt sémákhoz kapcsolódnak vagy azokon alapulnak.

A kiegyensúlyozott hiányos blokkdiagram (BIBD), amelyet röviden blokkdiagramoknak nevezünk, a v elemek véges X halmazának b részhalmazából ( blokkoknak nevezett) B halmaza , úgy, hogy az X halmaz bármely eleme benne van néhány r számú blokkban, minden blokknak ugyanannyi eleme van (= k ), és minden különálló elempár ugyanannyi ( ) blokkban jelenik meg [2] . A BIBD áramköröket 2-áramköröknek is nevezik, és gyakran áramköröknek is nevezik . Példaként a b = v esetre egy projektív síkot kapunk - X ebben az esetben a síkon lévő pontok halmaza, a blokkok pedig egyenesek. $=\lambda$ $2-(v,k,\lambda )$ $\lambda=1$
Symmetric Balanced Incomplete Block Design vagy SBIBD (en: Symmetric Balanced Incomplete Block Design) egy olyan BIBD, amelyben v = b (a pontok száma megegyezik a blokkok számával). Ez a BIBD legfontosabb és legjobban tanulmányozott alosztálya. A projektív síkok, a kétsíkok és a Hadamard 2-sémák SBIBD-sémák. Ezek a sémák a Fisher-féle egyenlőtlenség szélsőséges példáiként érdekesek ( ). $b\geqslant v$
A feloldható kiegyensúlyozott hiányos blokkdiagram egy BIBD, amelynek blokkjai halmazokra bonthatók (ezt párhuzamos osztályoknak nevezzük ), amelyek mindegyike egy BIBD [2] pontfelosztást alkot . A párhuzamos osztályok halmazát sémafeloldásnak nevezzük . A híres 15 diák probléma megoldása a BIBD felbontás v = 15, k = 3 és [4] . $\lambda=1$
A latin téglalap egyr × n( r ≤ n)mátrix, amelynek elemei az 1, 2, 3, ..., n(vagy bármely másnkülönböző karakterből álló halmaz), amelyben egyetlen szám sem szerepel kétszer bármely sor vagy oszlop. Az n × nméretűlatintéglalapot latin négyzetneknevezzük. Har < nr × nhozzáadhatunkn − rsort, hogylatin négyzetet kapjunk aHall esküvői tételének [5] segítségével .

Azt mondjuk, hogy két n rendű latin négyzet merőleges , ha a két négyzet megfelelő elemeiből álló összes rendezett pár halmaza n 2 különböző párból áll (azaz minden lehetséges rendezett pár előfordul). Az azonos sorrendű latin négyzetek halmaza egymásra merőleges latin négyzetek halmazát alkotja (en: Mutually Orthogonal Latin Squares, MOLS), ha a halmazban lévő latin négyzetek bármelyike merőleges. Egy ilyen n rendű négyzethalmazban legfeljebb n − 1 négyzet lehet . Az n − 1 MOLS n-rendű négyzetek halmaza felhasználható egy n -rendű projektív sík megszerkesztésére (és fordítva).

Az különbséghalmaz avrendűGcsoportDrészhalmaza, amelynekméretekGnem egyenlő eggyel, ábrázolhatód1d2−1elem szorzataként.Dpontosan olyanmódon (haG-t a szorzási művelet reprezentálja) [6] . $(v,k,\lambda )$ $\lambda$

Ha D különbséghalmaz és g G - hez tartozik , akkor ez is különbséghalmaz, és a D halmaz fordításának nevezzük . A D különbséghalmaz átviteleinek halmaza szimmetrikus blokkdiagramot alkot . Egy ilyen sémának v elemei és v blokkjai vannak. A séma minden blokkja k pontból áll, minden pontot k blokk tartalmaz. Bármely két blokk pontosan ugyanazokat az elemeket tartalmazza, és bármely két pont blokkban együtt jelenik meg. Ezt az SBIBD sémát a D halmaz fejlesztésének [7] nevezzük .

{\displaystyle g\mathbf {D} ={gd\colon d\in \mathbf {D} ))

\lambda

\lambda

Különösen, ha , a különbség halmaz egy projektív síkot alkot . Például egy különbséghalmaz (7,3,1) egy csoporton ( egy Abel -csoport additív jelöléssel) az {1,2,4} részhalmaza. Ennek a különbségkészletnek a fejlesztése adja a Fano síkot .

\lambda=1

\mathbb {Z} /7\mathbb {Z}

Mivel minden különbséghalmaz SBIBD-t eredményez, a paraméterkészletnek meg kell felelnie a Brook-Reiser-Chowl-tételnek , de nem minden SBIBD-séma ad különbséget.

Az m rendű Hadamard-mátrix egy m × m H mátrix±1 elemekkel úgy, hogy HH ⊤ = m E m , ahol H ⊤ a H transzpozíciója és E m az m × m azonosságmátrix . A Hadamard-mátrix lecsökkenthető egy szabványosított formára (vagyis átalakítható az egyenértékű Hadamard-mátrixra), amelyben az első sor és az első oszlop bejegyzései +1. Ha a sorrend m > 2, akkor m - nek oszthatónak kell lennie 4-gyel.

Adott egy 4a rendű Hadamard -mátrix szabványos formában, távolítsa el az első sort és az első oszlopot, majd cserélje ki az összes −1-et 0-ra. A kapott 0-1 M mátrix egy szimmetrikus áramkör beesési mátrixa , amelyet Hadamard 2-áramkörnek neveznek. [8] . Ez a konstrukció reverzibilis, így egy szimmetrikus 2-áramkör beesési mátrixa ezekkel a paraméterekkel 4a nagyságrendű Hadamard-mátrixot kaphat . A = 2 esetén a már ismert Fano síkot kapjuk (Hadamard 2-sémaként).

2-(4a-1,2a-1,a-1)

A páronkénti kiegyensúlyozott tervezés (en: Pairwise Balanced Design, PBD) egy X halmaz az X részhalmazainak családjával együtt (nem feltétlenül azonos méretűek, és az alhalmazok lehetnek azonosak), úgy, hogy az X -ből bármely különálló elem párja pontosan (pozitív számú) részhalmazokban szerepel. Egy X halmaz egy család része lehet , és ha az összes részhalmaz egy X halmaz másolata , a PBD sémát triviálisnak mondjuk . Az X halmaz mérete v , a család részhalmazainak száma (az azonos részhalmazokat külön számoljuk) b . $\lambda$

Fisher egyenlőtlensége a PBD-sémákra teljesül [9] – bármely nem triviális PBD-sémára, .

v\leqslant b

Ez az eredmény általánosítja a híres de Bruijn-Erdős-tételt – minden olyan PBD-séma esetében igaz , amelyben nincsenek 1 vagy v méretű blokkok , és az egyenlőség akkor és csak akkor áll fenn, ha a séma egy projektív sík vagy majdnem egy köteg. [10] .

\lambda=1

v\leqslant b

Egyéb kombinatorikus sémák

Colbourne és Dinitz Kézikönyve a Kombinatorikus Tervekről [11] többek között 65 fejezetet tartalmaz a fentebb felsoroltaktól eltérő kombinatorikus tervekről. Az alábbiakban egy részleges lista látható.

Kapcsolati sémák
A Balanced ternary Design (en: Balanced Ternary Design) V elemek elrendezése B multihalmazban (blokkokban, az egyes halmazok kardinalitása K ( K ≤ V )), amely megfelel a feltételeknek: $BTD(V,B;\rho _{1},\rho _{2},R;K,\Lambda )$

Minden elem egyszer jelenik meg 1-es többszörösséggel (1 példány a multihalmazban) pontosan blokkokban, és 2-es többszörösséggel pontosan blokkban. ${\displaystyle R=\rho _{1}+2\rho _{2))$ $\rho_{1}$ $\rho _{2}$
Minden különböző elempár egyszer jelenik meg (figyelembe véve a többszörösséget). Vagyis ha m vb a v elem többszöröse a b blokkban , akkor bármely v és w elempár esetén . $\lambda$ $\sum _{b=1}^{B}m_{vb}m_{wb}=\Lambda$

Például a két nem izomorf séma közül a BTD(4,8;2,3,8;4,6) (az oszlopok blokkként szolgálnak) [12]

egy	egy	egy	2	2	3	egy	egy
egy	egy	egy	2	2	3	2	2
2	3	négy	3	négy	négy	3	3
2	3	négy	3	négy	négy	négy	négy

A BTD séma előfordulási mátrixa (amelynek elemei blokkokban lévő elemek többszörösei) felhasználhatók hármas hibajavító kódok kialakítására, hasonlóan a BIBD sémák előfordulási mátrixaiból bináris kódok felépítéséhez [13] .

Az n(BTD(n) ) kiegyensúlyozott versenykör egy 2nhalmazösszes rendezetlen párjának elhelyezéseegyn × (2ntömbben úgy, hogy

V minden eleme pontosan egyszer jelenik meg minden oszlopban
a V halmaz minden eleme legfeljebb kétszer fordul elő minden sorban.

BTD(3) séma példa

16	3 5	2 3	4 5	24
25	4 6	tizennégy	13	3 6
3 4	12	5 6	26	tizenöt

A BTD( n ) séma oszlopai a 2 n csúcsú teljes gráf 1-es faktorizációját adják meg, K 2n [14] . A BTD( n ) sémák körmérkőzéses versenyek ütemezésére használhatók – a sorok a helyeket, az oszlopok a túrákat (körök, körök), a táblázatbejegyzések pedig a játékosokat vagy csapatokat jelölik.

Hajlított funkciók
Costas tömbjei
Teljes faktoriális kísérletek
A frekvencianégyzet ( F -négyzet) a latin négyzet általánosítása . Legyen S = { s 1 , s 2 , ..., s m } különböző szimbólumok halmaza, és pozitív számok frekvenciavektora . Az n rendű gyakorisági négyzet egy n × n tömb, amelyben minden s i karakter többször fordul elő ( i = 1,2,...,m) minden sorban és minden oszlopban. A gyakorisági négyzet szabványos alakú , ha az s i elemek megelőzik az s j -t az első sorban és az első oszlopban i < j esetén . $(\lambda _{1},\lambda _{2},...,\lambda _{m})$ $(n=\lambda _{1}+\lambda _{2}+...+\lambda _{m})$ $\lambda _{i}$

A frekvenciavektorral rendelkező { s 1 , s 2 , ..., s m } halmaz feletti n - rendű F 1 frekvencianégyzet és egy frekvenciavektorral rendelkező halmaz felett egy szintén n -rendű F 2 frekvencianégyzet ortogonális , ha van ilyen . a rendezett pár ( s i , t j ) pontosan egyszer jelenik meg, ha F 1 és F 2 átfedik egymást.

(\lambda _{1},\lambda _{2},...,\lambda _{m})

{\displaystyle \{t_{1},t_{2},...,t_{k}\))

(\mu _{1},\mu _{2},...,\mu _{k})

{\displaystyle \lambda _{i}\mu _{j))

A Hall Triple Systems (HTS) a Steiner Triple Systems (STS) (ahol a blokkokat vonalaknak nevezzük ), azzal a tulajdonsággal, hogy a két egyenes metszéspontjából kialakított részstruktúra izomorf az AG(2 ,3) véges affin síkkal .

Bármely affin tér AG( n ,3) példát ad egy HTS-sémára, az ilyen sémákat affin HTS-nek nevezzük. Léteznek nem-affin HTS-sémák is. A HTS sémában a pontok száma 3 m valamilyen egész szám esetén . Nem affin HTS-sémák léteznek bármelyikhez , és nem léteznek a vagy 3 számára [15] .

m\geqslant 2

m\geqslant 4

m=2

Bármely Steiner-hármas rendszer ekvivalens egy Steiner - kvázicsoporttal ( idempotens , kommutatív , és minden x -re és y -re érvényes ). A Hall-hármasok rendszere ekvivalens egy Steiner-kvázicsoporttal, melynek disztributív tulajdonsága , azaz a kvázicsoport minden a,x,y-jára érvényes [16] .

{\megjelenítési stílus (xy)y=x}

a(xy)=(ax)(ay)

Legyen S egy 2n elemű halmaz. A Howell-séma , H( s ,2 n ) (az S karakterkészleten) egy s × s tömb , amely:

Minden tömbcella vagy üres, vagy egy rendezetlen párt tartalmaz S -ből ,
Minden karakter pontosan egyszer jelenik meg a tömb minden sorában és oszlopában,
Minden rendezetlen pár legfeljebb egy tömbcellában jelenik meg.

Séma példa H(4,6)

0 4		13	25
2 3	tizennégy	0 5
	3 5	24	0 1
tizenöt	0 2		3 4

H(2 n − 1, 2 n ) Rum négyzete 2 n − 1 oldallal, így Howell sémái általánosítják a Rum-négyzet fogalmát. A Howell-diagram celláiban lévő szimbólumpárok felfoghatók egy 2n csúcsú szabályos gráf s éleiként , amelyet a Howell-diagram főgráfjának nevezünk. Howell ciklikus sémáit Howell mozdulataiként (játék befejezési séma) használják dupla bridzs versenyeken . A diagram sorai a köröket (köröket), az oszlopok a dobozokat (előre elkészített ügyletekkel, lásd "Híd - felkészülés a játékra" című részt), az átlók pedig a táblázatokat [17] jelölik .

Lineáris terek
A lottóséma ( n , k , p , t ) egy n elemből álló V halmaz k elemű részhalmazok (blokkok) halmazával együtt úgy, hogy a V halmaz p elemeiből álló bármely P részhalmazhoz létezik B blokk. -ban , amihez . L( n , k , p , t ) a legkisebb blokkszámot jelenti bármely lottósémában ( n , k , p , t ). Lotto séma (7,5,4,3) a lehető legkisebb blokkszámmal [18] : $\beta$ $\beta$ $|P\cap B|\geqslant t$

{1,2,3,4,7} {1,2,5,6,7} {3,4,5,6,7}. A lottó séma bármilyen lottót modellez a következő szabályokkal: A játékos k számot tartalmazó jegyet vásárol, amelyet egy n számot tartalmazó halmazból választ ki. Egy adott időpontban a jegyértékesítés leáll, és az eredeti, n számból álló halmazban található p számok véletlenszerű halmaza kerül kiválasztásra. Ezek a nyerőszámok . Ha az eladott jegy t vagy több nyerőszámot tartalmaz, a nyereményt a jegy birtokosa kapja. Minél több meccs, annál nagyobb a győzelem. Az L( n , k , p , t ) szám a játékosok és a kutatók számára egyaránt érdekes, mert ez jelenti a legkevesebb jegyet, amelyet a győzelem garantálásához meg kell vásárolni. A magyar lottó egy lottó séma (90,5,5, t ) és köztudott, hogy L(90,5,5,2) = 100. A (49,6,6, t ) paraméterű lottó mindenhol népszerű a világ és ismertek , hogy L(49,6,6,2) = 19. Általában ezek a számok nehezen kiszámíthatók és ismeretlenek maradnak [19] . Az egyik ilyen séma geometriai felépítését az " Erdélyi lottó " című cikk tartalmazza.

mágikus négyzetek
A Mendelssohn-séma ( ) v elemből álló V halmaz és a V halmaz különálló elemeinek rendezett k sorozatának halmaza ( blokkoknak nevezzük ), így minden rendezett ( x , y ) elempár V -ből ( x ≠ y ) blokkokban ciklikusan szomszédos (egy rendezett pár ( x , y ) különálló elemek ciklikusan szomszédos egy blokkban, ha az elemek egymás mellett jelennek meg a blokkban – vagy (..., x , y ,...) vagy ( y ,..., x )). A rendszer Mendelssohn triplák rendszere , amelyet MTS-nek neveznek . MTS(4,1) példa V = {0,1,2,3} felett: $(\mathbf {v} ,\mathbf {k} ,{\boldsymbol {\lambda )))$ $MD(\mathbf {v} ,\mathbf {k} ,{\boldsymbol {\lambda )))$ $\beta$ $\lambda$ $MD(\mathbf {v} ,\mathbf {3} ,{\boldsymbol {\lambda )))$ $(\mathbf {v} ,{\boldsymbol {\lambda )))$

(0,1,2) (1,0,3) (2,1,3) (0,2,3) Bármely hármasrendszer átalakítható Mendelssohn hármasrendszerré, ha a rendezetlen hármast { a , b , c } lecseréljük egy pár rendezett hármasra ( a , b , c ) és ( a , c , b ), de ennek fordítottja. nem igaz, ahogy a példa is mutatja. Legyen ( Q ,∗) egy idempotens félszimmetrikus kvázicsoport , azaz x ∗ x = x (idempotens) és x ∗ ( y ∗ x ) = y (félszimmetrikus) teljesüljön benne minden x , y Q - ra . Hadd . Ekkor egy Mendelssohn-hármas MTS(| Q |,1) rendszer. Ez a konstrukció megfordítható [20] .

{\displaystyle \beta =\{(x,y,x\ast y)\colon x,y\in Q\))

(Q,\beta )

Ortogonális táblázatok
A kvázi-3-as áramkör egy szimmetrikus áramkör (SBIBD), amelyben minden blokkhármas x vagy y pontban metszi egymást rögzített x és y számok esetén, amelyeket hármas metszéspontszámoknak nevezünk ( x < y ). Bármely szimmetrikus áramkör kvázi-3-as áramkörrel és . A PG ( n , q ) geometria pont-hipersík sémája egy kvázi-3-as séma és -val . Ha egy kvázi-3-as áramkör esetében, akkor az áramkör izomorf a PG -vel ( n , q ) vagy a projektív síkkal [21] . $\lambda \leqslant 2$ $x=0$ $y=1$ $x=(q^{n-2}-1)/(q-1)$ $y=\lambda =(q^{n-1}-1)/(q-1)$ $y=\lambda$
Egy áramkör kvázi - szimmetrikus x és y metszéspontjaival ( x < y ), ha bármely két különböző blokk metszéspontjában x vagy y pont található. Ezek a sémák természetesen felmerülnek a kettős sémák tanulmányozása során . Egy nem szimmetrikus áramkör ( b > v ) 2-( v , k ,1) kváziszimmetrikus, ahol x = 0 és y = 1. Többszörös (a blokkok bizonyos számú alkalommal ismétlődnek) szimmetrikus 2 -áramkörök kvázi- szimmetrikus és y = k . A Hadamard 3-sémák ( a Hadamard 2-sémák kiterjesztése ) kvázi -szimmetrikusak [22] . $Dt-(v,k,\lambda )$ $\lambda=1$ $(v,k,\lambda )$ $x=\lambda$

Bármely kváziszimmetrikus blokkdiagram egy erősen szabályos gráfot generál (mint a blokkgráfja ), de nem minden SRG áramkör jön létre így [23] . Egy k ≡ x ≡ y (mod 2) kváziszimmetrikus 2- áramkör beesési mátrixa egy bináris önortogonális kódot alkot [ 24 ] .

(v,k,\lambda )

Rum négyzetei
A gömbtervezés egy végesXponthalmaz egy (d − 1)-dimenziósgömbönúgy, hogy valamilyentXpolinomátlaga

f(x_{1},\ldots ,x_{d})\

t- t meg nem haladó fokkal egyenlő f átlagos értékével a teljes gömbön (vagyis az f függvény integrálja osztva a gömb területével).

Turan rendszerek
A toszkán r × n k téglalap n karakter felett r sort és n oszlopot tartalmaz,

minden sor n karakter permutációja
bármely két különálló a és b karakterhez , valamint minden 1-től k -ig terjedő m számhoz legfeljebb egy olyan sor van, amelyben b m lépéssel jobbra a -tól .

Ha r = n és k = 1, akkor a sémákat toszkán négyzeteknek , míg r = n és k = n - 1 esetén firenzei négyzeteknek nevezzük . A római tér egy toszkán négyzet, amely egyben latin négyzet is (az ilyen négyzeteket sorteljes latin négyzeteknek is nevezik ). A Vatikán tér egy firenzei tér, ami egyben latin tér is. Példa egy 7 karakterből álló toszkán 1-négyzetre, amely nem 2-négyzet [25] :

6	egy	5	2	négy	3	7
2	6	3	5	négy	7	egy
5	7	2	3	egy	négy	6
négy	2	5	egy	6	7	3
3	6	2	egy	7	négy	5
egy	3	2	7	5	6	négy
7	6	5	3	négy	egy	2

Egy toszkán négyzet n szimbólumon ekvivalens n csúcsú teljes gráfok n Hamilton-orientált pályára való felbontásával [26] .

A t-típusú t - szeres kiegyensúlyozott áramkör (vagy t BD) v elemek X halmaza X részhalmazainak családjával ( blokkoknak nevezett ) együtt, amelyek méretei egy K halmazban vannak úgy, hogy bármely t - részhalmaz különálló elemből álljon. X elemei pontosan blokkokban találhatók. Ha K pozitív egészek halmaza szigorúan t és v között, akkor a t BD sémát megfelelőnek nevezzük . Ha X valamennyi k részhalmaza blokk, akkor a t BD sémát triviálisnak nevezzük [27] . $(v,K,\lambda )$ $\lambda$

Vegye figyelembe, hogy a 3-{12,{4,6},1) példában az X = {1,2,...,12} halmaz sémáiban néhány pár négyszer jelenik meg (például az {1, 2}), míg mások ötször jelennek meg (például a {6,12} pár) [28] . 1 2 3 4 5 6 1 2 7 8 1 2 9 11 1 2 10 12 3 5 7 8 3 5 9 11 3 5 10 12 4 6 7 8 4 6 9 11 4 6 10 12 7 8 9 10 11 12 2 3 8 9 2 3 10 7 2 3 11 12 4 1 8 9 4 1 10 7 4 1 11 12 5 6 8 9 5 6 10 7 5 6 11 12 3 4 9 10 3 4 11 8 3 4 7 12 5 2 9 10 5 2 11 8 5 2 7 12 1 6 9 10 1 6 11 8 1 6 7 12 4 5 10 11 4 5 7 9 4 5 8 12 1 3 10 11 1 3 7 9 1 3 8 12 2 6 10 11 2 6 7 9 2 6 8 12 5 1 11 7 5 1 8 10 5 1 9 12 2 4 11 7 2 4 8 10 2 4 9 12 3 6 11 7 3 6 8 10 3 6 9 12

A hiányos latin négyzet egy k × v téglalap alakú tömb ( k < v ) v karakterekből áll , amelyekben minden karakter pontosan egyszer jelenik meg minden sorban , és a bármely oszlopban megjelenő karakterek egy szimmetrikus áramkör blokkjait alkotják , amelyek mindegyik blokkja pontosan egyszer jelenik meg . . A hiányos latin négyzet egy latin téglalap. A címben szereplő "négyzet" kifejezés egy régebbi definícióból származik, amely négyzettömböt használt [29] . Példa egy hiányos latin 4×7 négyzetre: $(v,k,\lambda )$

egy	2	3	négy	5	6	7
2	3	négy	5	6	7	egy
3	négy	5	6	7	egy	2
5	6	7	egy	2	3	négy

Hét blokk (oszlop) alkot egy 2. rendű kétsíkot (szimmetrikus séma (7,4,2)).

Jegyzetek

↑ Stinson, 2003 , p. egy.
↑ 1 2 3 Rybnikov, 1972 , p. 130.
↑ Stinson, 2003 , p. IX.
↑ Beth, Jungnickel, Lenz, 1999 , p. 40 5.8. példa.
↑ Ryser, 1963 , p. 52 3.1. Tétel.
↑ Ha G egy Abel-csoport (vagy egy összeadási művelettel írjuk), a definíció d 1 –d 2 alakot ölt , amelyből a differenciahalmaz kifejezés keletkezett .
↑ Beth, Jungnickel, Lenz, 1999 , p. 262 1.6. tétel.
↑ Stinson, 2003 , p. 74 4.5. Tétel.
↑ Stinson, 2003 , p. 193 8.20. tétel.
↑ Stinson, 2003 , p. 183, 8.5. Tétel.
↑ Colbourn, Dinitz, 2007 .
↑ Colbourn, Dinitz, 2007 , p. 331 2.2. példa.
↑ Colbourn, Dinitz, 2007 , p. 331 Megjegyzés 2.8.
↑ Colbourn, Dinitz, 2007 , p. 333, Megjegyzés 3.3.
↑ Colbourn, Dinitz, 2007 , p. 496 28.5. tétel.
↑ Colbourn, Dinitz, 2007 , p. 497 28.15. tétel.
↑ Colbourn, Dinitz, 2007 , p. 503 Megjegyzés 29.38.
↑ Colbourn, Dinitz, 2007 , p. 512 Példa 32.4.
↑ Colbourn, Dinitz, 2007 , p. 512, Megjegyzés 32.3.
↑ Colbourn, Dinitz, 2007 , p. 530 35.15. tétel.
↑ Colbourn, Dinitz, 2007 , p. 577 47.15. tétel.
↑ Colbourn, Dinitz, 2007 , p. 578-579.
↑ Colbourn, Dinitz, 2007 , p. 579 48.10. tétel.
↑ Colbourn, Dinitz, 2007 , p. 580 Lemma 48.22.
↑ Colbourn, Dinitz, 2007 , p. 652 Példák 62.4.
↑ Colbourn, Dinitz, 2007 , p. 655 62.24. tétel.
↑ Colbourn, Dinitz, 2007 , p. 657.
↑ Colbourn, Dinitz, 2007 , p. 658 Példa 63.5.
↑ Colbourn, Dinitz, 2007 , p. 669 Megjegyzés 65.3.

Irodalom

Rybnikov K.A. Bevezetés a kombinatorikus elemzésbe. - Moszkvai Állami Egyetem, 1972.
Tarannikov Yu. V. Diszkrét struktúrák kombinatorikus tulajdonságai és kriptológiai alkalmazások. - MTSNMO, 2011. - ISBN 978-5-94057-812-3 .
Hall M. Kombinatorika. - MIR, 1966.
Assmus EF, Key JD Designs és kódjaik. - Cambridge: Cambridge University Press, 1992. - ISBN 0-521-41361-3 .
Beth T., Jungnickel D., Lenz H. Tervezéselmélet. - Cambridge: Cambridge University Press , 1999. - ISBN 978-0-521-44432-3 .
Bose RC Megjegyzés a Fisher-féle egyenlőtlenséghez kiegyensúlyozott hiányos blokktervezés esetén // Annals of Mathematical Statistics . - 1949. - S. 619-620 .
Caliński T., Kageyama S. Block designs: A Randomization approach, Volume II : Design. - New York: Springer-Verlag, 2003. - Vol. 170. - (Lecture Notes in Statistics). — ISBN 0-387-95470-8 .
Colbourn Charles J., Dinitz Jeffrey H. Handbook of Combinatorial Designs. — 2. — Boca Raton: Chapman & Hall/CRC, 2007. — ISBN 1-58488-506-8 .
Fisher RA Egy probléma különböző lehetséges megoldásainak vizsgálata hiányos blokkokban // Annals of Eugenics . - 1940. - T. 10 . – S. 52–75 .
Hall Marshall Jr. kombinatorikus elmélet. — 2. - New York: Wiley-Interscience, 1986. - ISBN 0-471-09138-3 .
Hughes DR, Piper EC Design theory . - Cambridge: Cambridge University Press, 1985. - ISBN 0-521-25754-9 .
Lander ES szimmetrikus tervek: algebrai megközelítés. – Cambridge: Cambridge University Press, 1983.
Lindner CC, Rodger CA Design Theory . - Boca Raton: CRC Press, 1997. - ISBN 0-8493-3986-3 .
Raghavarao D. Konstrukciók és kombinatorikai problémák a kísérletek tervezésében. – az 1971-es Wiley javított utánnyomása. – New York: Dover, 1988.
Raghavarao D., Padgett LV blokktervek : elemzés, kombinatorika és alkalmazások. – World Scientific, 2005.
Ryser Herbert John. 8. fejezet: Kombinatorikus tervek // Kombinatorikus matematika (Carus Monograph #14). – Amerikai Matematikai Szövetség, 1963.
Shrikhande SS, Vasanti NB-N. Egyes kiegyensúlyozott hiányos blokktervek nem izomorf megoldásai I – // Journal of Combinatorial Theory . – 1970.
Stinson Douglas R. Kombinatorikus tervek: Konstrukciók és elemzés. - New York: Springer, 2003. - ISBN 0-387-95487-2 .
Street Anne Penfold, Street Deborah J. Combinatorics of Experimental Design. - Oxford UP [Clarendon], 1987. - P. 400+xiv. — ISBN 0-19-853256-3 .
van Lint, JH és R. M. Wilson. Kombinatorika tanfolyam. – Cambridge, Eng.: Cambridge University Press, 1992.