Kombinatorisk skema

Teorien om kombinatoriske skemaer er en del af kombinatorikken (en gren af matematikken ), der overvejer eksistensen, konstruktionen og egenskaberne af familier af endelige mængder hvis struktur opfylder generaliserede begreber om ligevægt og/eller symmetri . Disse begreber er ikke præcist definerede, så en bred vifte af objekter kan forstås som kombinatoriske skemaer. Så i et tilfælde kan kombinatoriske skemaer repræsentere skæringspunkter mellem sæt tal, som i flowcharts , og i et andet tilfælde kan de afspejle arrangementet af elementer i Sudoku .

Teorien om kombinatoriske skemaer kan bruges i design af eksperimenter . Nogle af de grundlæggende kombinatoriske skemaer er givet i Ronald Fishers arbejde med teorien om biologiske eksperimenter. Kombinatoriske skemaer kan nu findes inden for en lang række områder, herunder endelig geometri , turneringsplanlægning , lotterier , matematisk biologi , algoritmedesign og analyse , computernetværk , gruppetest og kryptografi [1] .

Definition

Betegn - sættet af elementer . Overvej delmængder af dette sæt . Hver delmængde kaldes en blok, og antallet af sætelementer i den kaldes blokkens volumen og betegnes som . Lad være antallet af delmængder , der indeholder dette element. Antallet af gentagelser (uordnede par) er angivet som . Derefter danner sættet af blokke et kombinatorisk skema (eller blokdiagram) med parametre [2] . $v$ ${\displaystyle m_{1},m_{2},...,m_{v))$ ${\displaystyle M_{1},M_{2},...,M_{b))$ $M_{j}$ $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))$

Eksempel

Hvis der er n personer, er det muligt at danne sæt ud fra dem, således at hver person tilhører mindst ét sæt, hvert par tilhører præcis ét sæt, hver to sæt kun har én person i skæringspunktet, og ingen af sættene består af af alle mennesker, alle mennesker minus én eller præcis én person? Svaret afhænger af n .

Svaret er kun ja, hvis n har formen q 2 + q + 1. Det er sværere at bevise, at løsningen eksisterer, hvis q er en primpotens . Der er en formodning om, at der ikke er andre løsninger. Det er blevet bevist, at hvis der findes en løsning for q , der er kongruent med 1 eller 2 modulo 4, så er q summen af to perfekte kvadrater . Dette resultat, Brook-Reiser-Chowl-sætningen , blev bevist ved en kombination af konstruktionsmetoder baseret på begrænsede felter og kvadratiske former .

Når en sådan struktur eksisterer, kaldes det et endeligt projektivt plan . Dette viser, hvordan teorien om endelige geometrier og kombinatorik krydser hinanden. I tilfældet q = 2 kaldes det projektive plan Fano-planet .

Historie

Kombinatoriske skemaer har været kendt siden antikken i form af Lo Shu-pladsen , som var en tidlig version af den magiske plads . Kombinatoriske skemaer har udviklet sig med udviklingen af kombinatorik siden det 18. århundrede, for eksempel i form af latinske firkanter i det 18. århundrede og Steiner-systemer i det 19. århundrede. Kombinatoriske skemaer er også populære i underholdende matematik , såsom Kirkmans skolepigeproblem (1850), og praktiske problemer såsom planlægning af round robin-turneringer (løsning offentliggjort i 1880'erne). I det 20. århundrede blev kombinatoriske skemaer anvendt til design af eksperimenter , endelige geometrier og relationsskemaer og førte til fremkomsten af algebraisk statistik .

Grundlæggende kombinatoriske skemaer

Den klassiske kerne af emnet kombinatoriske skemaer er bygget op omkring balanceret ufuldstændigt blokdesign (en: Balanced Incomplete Block Design, BIBD), matricer og Hadamard-skemaer , symmetrisk BIBD , latinske kvadrater , opløselig BIBD , differenssæt og parvis balancerede skemaer (da: Pairwise Balanced Design , PBD) [3] . Andre kombinatoriske skemaer er relateret til eller baseret på de anførte skemaer.

Et balanceret ufuldstændigt blokdiagram (BIBD), kaldet blokdiagrammer for korte , er et sæt B af b delmængder (kaldet blokke ) af et endeligt sæt X af v elementer, sådan at ethvert element i mængden X er indeholdt i nogle antal r blokke, hver blok har det samme antal elementer (= k ), og hvert par af forskellige elementer optræder i det samme antal ( ) af blokke [2] . BIBD-kredsløb er også kendt som 2-kredsløb og omtales ofte som kredsløb. Som et eksempel, for tilfældet og b = v får vi et projektivt plan - X i dette tilfælde er sættet af punkter på planet, og blokkene er lige linjer. $=\lambda$ $2-(v,k,\lambda )$ $\lambda=1$
Symmetric Balanced Incomplete Block Design eller SBIBD (en: Symmetric Balanced Incomplete Block Design) er en BIBD, hvor v = b (antallet af punkter er lig med antallet af blokke). Dette er den vigtigste og mest velstuderede underklasse af BIBD. Projektive fly, biplaner og Hadamard 2-skemaer er SBIBD-skemaer. Disse ordninger er af interesse som ekstreme eksempler på Fishers ulighed ( ). $b\geqslant v$
Et opløseligt afbalanceret ufuldstændigt blokdiagram er et BIBD, hvis blokke kan opdeles i sæt (kaldet parallelle klasser ), som hver danner en BIBD [2] punktopdeling . Sættet af parallelle klasserkaldes skemaopløsning . Løsningen på det berømte problem med 15 elever er BIBD-opløsningen med v = 15, k = 3 og [4] . $\lambda=1$
Det latinske rektangel er enr × n( r ≤ n)matrix,der som elementer har tallene 1, 2, 3, ..., n(eller ethvert andet sæt afnforskellige tegn), hvor intet tal optræder to gange i enhver række eller kolonne. Et latinskrektangelmed dimensionernen × nkaldeslatinsk kvadrat. Hvisr < n, så kan man tilføjen − rrækker til etr × nfor at danne et latinsk kvadrat ved hjælp afHalls bryllupssætning [5] .

Vi siger, at to latinske kvadrater af orden n er ortogonale, hvis mængden af alle ordnede par bestående af de tilsvarende elementer af to kvadrater består af n 2 forskellige par (det vil sige, at alle mulige ordnede par forekommer). Et sæt latinske kvadrater af samme rækkefølge danner et sæt indbyrdes ortogonale latinske kvadrater (en: Mutually Orthogonal Latin Squares, MOLS), hvis et par latinske kvadrater i sættet er ortogonale. Der kan højst være n − 1 kvadrater i et sådant sæt kvadrater af orden n . Mættet af n − 1 MOLS kvadrater af orden n kan bruges til at konstruere et projektivt plan af orden n (og omvendt).

Differencemængden er endelmængdeDaf gruppenGaf ordenv, medstørrelsenkGikke er lig med én, kan repræsenteres som et produkt afd1d2−1elementer afDpå præcis demåder (hvisGer repræsenteret ved multiplikationsoperationen) [6] . $(v,k,\lambda )$ $\lambda$

Hvis D er en differensmængde og g hører til G , så er det også en differensmængde og kaldes en translation af mængden D . Sættet af overførsler af differenssættet D danner et symmetrisk blokdiagram . Et sådant skema har v -elementer og v -blokke. Hver blok i skemaet består af k punkter, hvert punkt er indeholdt i k blokke. Alle to blokke har nøjagtig de samme elementer, og to punkter vises sammen i blokke. Dette skema SBIBD kaldes udviklingen af sættet D [7] .

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

\lambda

\lambda

Især hvis , differenssættet danner et projektivt plan . For eksempel er et differenssæt (7,3,1) over en gruppe ( en Abelsk gruppe med additiv notation) en delmængde af {1,2,4}. Udviklingen af dette differenssæt giver Fano-flyet .

\lambda=1

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

Da ethvert differenssæt giver SBIBD, skal parametersættet opfylde Brook-Reiser-Chowl-sætningen , men ikke alle SBIBD-skemaer giver et differenssæt.

En Hadamard-matrix af orden m er en m × m -matrix H med elementer ±1, således at HH ⊤ = m E m , hvor H ⊤ ertransponeringen af H og Em er m × m identitetsmatrixen . Hadamard-matricen kan reduceres til en standardiseret form (det vil sige konverteret til den tilsvarende Hadamard-matrix), hvor indtastningerne i første række og første kolonne er +1. Hvis rækkefølgen m > 2, så skal m være delelig med 4.

Givet en Hadamard-matrix af orden 4a i standardiseret form, fjern den første række og den første kolonne, og erstat derefter alle −1 med 0. Den resulterende 0-1 matrix M er incidensmatricen af et symmetrisk kredsløb, kaldet et Hadamard 2-kredsløb [8] . Denne konstruktion er reversibel, således at incidensmatricen af et symmetrisk 2-kredsløb med disse parametre kan bruges til at opnå en Hadamard matrix af størrelsesordenen 4a . I tilfældet a = 2 får vi det allerede velkendte Fano-fly (som et Hadamard 2-skema).

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

Et parvis afbalanceret design (da: Pairwise Balanced Design, PBD) er et sæt X sammen med en familie af delmængder af X (ikke nødvendigvis af samme størrelse, og delmængderne kan være de samme), således at ethvert par af forskellige elementer fra X er indeholdt i nøjagtigt (et positivt antal) af delmængder. Et sæt X er tilladt at være en del af en familie, og hvis alle undersæt er kopier af et sæt X , siges PBD-skemaet at være trivielt . Størrelsen af mængden X er v , og antallet af delmængder i familien (identiske delmængder tælles separat) er b . $\lambda$

Fishers ulighed for PBD-ordninger er opfyldt [9] — for enhver ikke-triviel PBD-ordning, .

v\leqslant b

Dette resultat generaliserer den berømte de Bruijn-Erdős-sætning - for ethvert PBD-skema med , som ikke har blokke af størrelse 1 eller v , er sandt , og ligheden gælder, hvis og kun hvis skemaet er et projektivt plan eller næsten et hylster [10] .

\lambda=1

v\leqslant b

Andre kombinatoriske skemaer

The Handbook of Combinatorial Designs af Colbourne og Dinitz [11] indeholder blandt andet 65 kapitler om andre kombinatoriske designs end dem, der er givet ovenfor. En delvis liste er givet nedenfor.

Relationsordninger
Balanceret ternært design (da: Balanced Ternary Design) er et arrangement af V - elementer i B -multisæt (blokke, kardinaliteten af hvert sæt er K ( K ≤ V )), der opfylder betingelserne: $BTD(V,B;\rho _{1},\rho _{2},R;K,\Lambda )$

Hvert element vises én gang med en multiplicitet på 1 (1 instans i multisættet) nøjagtigt i blokke, og med en multiplicitet på 2 nøjagtigt i blokke. ${\displaystyle R=\rho _{1}+2\rho _{2))$ $\rho_{1}$ $\rho _{2}$
Hvert par af forskellige elementer vises én gang (under hensyntagen til mangfoldigheden). Det vil sige, hvis m vb er multipliciteten af element v i blok b , så for ethvert par af forskellige elementer v og w . $\lambda$ $\sum _{b=1}^{B}m_{vb}m_{wb}=\Lambda$

For eksempel er et af de to ikke-isomorfe skemaer BTD(4,8;2,3,8;4,6) (kolonner tjener som blokke) [12]

en	en	en	2	2	3	en	en
en	en	en	2	2	3	2	2
2	3	fire	3	fire	fire	3	3
2	3	fire	3	fire	fire	fire	fire

Incidensmatricen af et BTD-skema (hvis elementer er multipliciteter af elementer i blokke) kan bruges til at danne ternære fejlkorrigerende koder på samme måde som konstruktionen af binære koder fra incidensmatricerne af BIBD-skemaer [13] .

Et balanceret turneringskredsløb af ordenn(BTD(n)) er placeringen af alle distinkte uordnede par af et2nsætVn × (2narray , således at

hvert element af V optræder nøjagtigt én gang i hver kolonne
hvert element i sættet V optræder højst to gange i hver række.

BTD(3) Skema eksempel

16	3 5	2 3	4 5	24
25	4 6	fjorten	13	3 6
3 4	12	5 6	26	femten

Søjlerne i skemaet BTD( n ) giver en 1-faktorisering af hele grafen med 2 n toppunkter, K 2n [14] . BTD( n )-skemaer kan bruges til at planlægge round robin-turneringer - rækker repræsenterer steder, kolonner repræsenterer ture (runder, cirkler), og tabelposter definerer spillere eller hold.

Bøjede funktioner
Arrays af Costas
Fuld faktorielle eksperimenter
Frekvenskvadraten ( F -kvadrat ) er en generalisering af det latinske kvadrat . Lad S = { s 1 , s 2 , ..., s m } være et sæt af forskellige symboler og være en frekvensvektor af positive tal. Et frekvenskvadrat af orden n er et n × n array, hvor hvert tegn s i forekommer gange ( i = 1,2,...,m) i hver række og hver kolonne. Frekvenskvadraten har en standardform, hvis elementerne s i går foran s j i første række og første kolonne for i < j . $(\lambda _{1},\lambda _{2},...,\lambda _{m})$ $(n=\lambda _{1}+\lambda _{2}+...+\lambda _{m})$ $\lambda _{i}$

Et frekvenskvadrat F 1 af orden n over et sæt { s 1 , s 2 , ..., s m } med en frekvensvektor og et frekvenskvadrat F 2 også af orden n over et sæt med en frekvensvektor er ortogonale, hvis nogen ordnet par ( s i , t j ) vises nøjagtigt én gang, når F 1 og F 2 overlapper hinanden.

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

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

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

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

Hall Triple Systems (HTS) er Steiner Triple Systems (STS) (hvor blokke kaldes linjer ) med den egenskab, at understrukturen dannet ved skæringen af to linjer er isomorf til den endelige affine plan AG(2 ,3).

Ethvert affint rum AG( n ,3) giver et eksempel på et HTS-skema, sådanne skemaer kaldes affint HTS. Ikke-affine HTS-ordninger findes også. Antallet af punkter i HTS-skemaet er 3 m for et eller andet heltal . Ikke-affine HTS-ordninger findes for nogen og eksisterer ikke for eller 3 [15] .

m\geqslant 2

m\geqslant 4

m=2

Ethvert Steiner-tredobbelt system svarer til en Steiner- kvasigruppe ( idempotent , kommutativ og gælder for alle x og y ). Systemet med Hall-tripler svarer til en Steiner-kvasigruppe med den fordelende egenskab , det vil sige, at det gælder for alle a,x,y i kvasigruppen [16] .

(xy)y=x

a(xy)=(ax)(ay)

Lad S være et sæt af 2n elementer. Howell-skemaet , H( s , 2n ) (på tegnsættet S ) er et s × s -array , således at:

Hver matrixcelle er enten tom eller indeholder et uordnet par fra S ,
Hvert tegn optræder nøjagtigt én gang i hver række og hver kolonne i arrayet,
Hvert uordnet par vises i højst én matrixcelle.

Skemaeksempel H(4,6)

0 4		13	25
2 3	fjorten	0 5
	3 5	24	0 1
femten	0 2		3 4

H(2 n − 1, 2 n ) er Roms kvadrat med side 2 n − 1, så Howells skemaer generaliserer begrebet Roms kvadrater. Symbolparrene i cellerne i Howell-diagrammet kan opfattes som kanter s af en regulær graf med 2n hjørner, som kaldes Howell-diagrammets hovedgraf . Howells cykliske skemaer bruges som Howells bevægelser (spilafslutningsskema) i double bridge- turneringer . Rækkerne i diagrammet repræsenterer runderne (cirklerne), kolonnerne repræsenterer kasserne (med aftaler forberedt på forhånd, se "Bro - forberedelse til spillet" ), og diagonalerne repræsenterer tabellerne [17] .

Lineære mellemrum
Et lottoskema ( n , k , p , t ) er et sæt V af n elementer sammen med et sæt af k -element-delmængder (blokke), således at der for enhver undergruppe P , der består af p - elementer i mængden V , eksisterer en blok B i , for hvilket . L( n , k , p , t ) betyder det mindste antal blokke i enhver lottoordning ( n , k , p , t ). Lottoordning (7,5,4,3) med det mindst mulige antal blokke [18] : $\beta$ $\beta$ $|P\cap B|\geqslant t$

{1,2,3,4,7} {1,2,5,6,7} {3,4,5,6,7}. Lotto-ordningen modellerer ethvert lotteri med følgende regler: En spiller køber lodder , der indeholder k numre, valgt fra et sæt, der indeholder n numre. På et tidspunkt stopper billetsalget, og et tilfældigt sæt p -numre indeholdt i det originale sæt af n numre vælges. Disse er vindertallene . Hvis den solgte billet indeholder t eller flere vindernumre, gives præmien til billetindehaveren. Jo flere kampe, jo højere gevinst. Tallet L( n , k , p , t ) er interessant for både spillere og forskere, fordi det repræsenterer det mindste antal billetter, der skal købes for at garantere en gevinst. Det ungarske lotteri er en lottoordning (90,5,5, t ), og det er kendt, at L(90,5,5,2) = 100. Lotterier med parametre (49,6,6, t ) er populære overalt verden og er kendt , at L(49,6,6,2) = 19. Generelt er disse tal svære at beregne og forbliver ukendte [19] . Den geometriske konstruktion af en af disse ordninger er givet i artiklen " Transylvanian Lottery ".

magiske firkanter
Et Mendelssohn-skema ( ) er et sæt V af v elementer og et sæt ordnede k - tupler af distinkte elementer i sættet V (kaldet blokke ), således at hvert ordnet par ( x , y ) af elementer fra V ( x ≠ y ) er cyklisk tilstødende i blokke (et ordnet par ( x , y ) af distinkte elementer er cyklisk tilstødende i en blok, hvis elementerne optræder side om side i blokken - enten (..., x , y ,...) eller ( y ,..., x )). Ordningen er et system af Mendelssohn tripler , betegnet MTS . MTS(4,1) eksempel over V = {0,1,2,3}: $(\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) Ethvert system af tripler kan konverteres til et Mendelssohn triple system ved at erstatte den uordnede tripel { a , b , c } med et par ordnede tripler ( a , b , c ) og ( a , c , b ), men det omvendte er ikke sandt, som eksemplet viser. Lad ( Q ,∗) være en idempotent semisymmetrisk kvasigruppe , dvs. x ∗ x = x (idempotent) og x ∗ ( y ∗ x ) = y (semisymmetrisk) holde i den for alle x , y fra Q . Lad . Så er et system af Mendelssohn tripler MTS(| Q |,1). Denne konstruktion er reversibel [20] .

{\displaystyle \beta =\{(x,y,x\ast y)\kolon x,y\i Q\))

(Q,\beta )

Ortogonale borde
Et kvasi-3-kredsløb er et symmetrisk kredsløb (SBIBD), hvor hver bloktripel skærer ved enten x- eller y - punkter for faste x- og y -tal , kaldet de tredobbelte skæringsnumre ( x < y ). Ethvert symmetrisk kredsløb med er et kvasi-3 kredsløb med og . Punkt-hyperplan-skemaet for geometrien PG ( n , q ) er et kvasi-3-skema med og . Hvis for et kvasi-3 kredsløb, er kredsløbet isomorf til PG ( n , q ) eller det projektive plan [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$
Et kredsløb er kvasisymmetrisk med skæringsnumrene x og y ( x < y ), hvis to distinkte blokke har enten x- eller y - punkter i deres skæringspunkt. Disse ordninger opstår naturligt i undersøgelsen af dobbeltordninger med . Et ikke-symmetrisk kredsløb ( b > v ) 2-( v , k ,1) er kvasisymmetrisk med x = 0 og y = 1. Multiple (blokke gentages et vist antal gange) symmetriske 2 -kredsløb er kvasi- symmetrisk med og y = k . Hadamard 3-skemaer (en udvidelse af Hadamard 2-skemaer ) er kvasisymmetriske [22] . $Dt-(v,k,\lambda )$ $\lambda=1$ $(v,k,\lambda )$ $x=\lambda$

Ethvert kvasisymmetrisk blokdiagram genererer en meget regulær graf (som dens blokgraf ), men ikke alle SRG-kredsløb genereres på denne måde [23] . Incidensmatricen af et kvasisymmetrisk kredsløb 2- med k ≡ x ≡ y (mod 2) danner en binær selvortogonal kode [24] .

(v,k,\lambda )

Squares of Rum
Et sfærisk design er et endeligt sætXaf punkter på en (d − 1)-dimensionalkugle,således at for et heltalter middelværdien afpolynomietX

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

med en grad, der ikke overstiger t , er lig med gennemsnitsværdien af f over hele kuglen (det vil sige integralet af funktionen f divideret med kuglens areal).

Turan systemer
Det toscanske r × n k -rektangel over n tegn har r rækker og n kolonner, med

hver linje er en permutation på n tegn
for to forskellige tegn a og b , og for hvert tal m fra 1 til k , er der højst én linje, hvor b er m trin til højre for a .

Hvis r = n og k = 1, kaldes skemaerne toscanske firkanter , mens de i tilfælde af r = n og k = n - 1 kaldes florentinske firkanter . En romersk firkant er en toscansk plads, der også er en latinsk firkant (sådanne firkanter er også kendt som række-komplette latinske firkanter ). Vatikanets plads er en florentinsk plads, som også er en latinsk plads. Et eksempel på en toscansk 1-kvadret på 7 tegn, der ikke er en 2-kvadret [25] :

6	en	5	2	fire	3	7
2	6	3	5	fire	7	en
5	7	2	3	en	fire	6
fire	2	5	en	6	7	3
3	6	2	en	7	fire	5
en	3	2	7	5	6	fire
7	6	5	3	fire	en	2

Et toscansk kvadrat på n symboler svarer til en nedbrydning af komplette grafer med n hjørner til n Hamilton-orienterede stier [26] .

Et t-fold balanceret kredsløb (eller t BD) af typen t - er et sæt X af v elementer sammen med en familie af delmængder af X (kaldet blokke ), hvis størrelser er indeholdt i et sæt K , således at enhver t -delmængde af distinkte elementer af X er indeholdt nøjagtigt i blokke. Hvis K er et sæt positive heltal strengt mellem t og v , så kaldes skemaet t BD egentligt . Hvis alle k -delmængder af X for nogle k er blokke, så kaldes skemaet t BD trivielt [27] . $(v,K,\lambda )$ $\lambda$

Bemærk, at i eksempel 3-{12,{4,6},1)-skemaerne på sættet X = {1,2,...,12}, optræder nogle par fire gange (f.eks. parret {1, 2}), mens andre vises fem gange (for eksempel parret {6,12}) [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

En ufuldstændig latinsk firkant er en k × v rektangulær matrix ( k < v ) v af tegn, således at hvert tegn optræder nøjagtigt én gang i hver række, og tegnene, der optræder i en hvilken som helst kolonne, danner blokke af et symmetrisk kredsløb , hvor alle blokke optræder nøjagtigt én gang . En ufuldstændig latinsk firkant er et latinsk rektangel. Udtrykket "kvadrat" i titlen kommer fra en ældre definition, der brugte et kvadratisk array [29] . Et eksempel på en ufuldstændig latinsk 4×7 kvadrat: $(v,k,\lambda )$

en	2	3	fire	5	6	7
2	3	fire	5	6	7	en
3	fire	5	6	7	en	2
5	6	7	en	2	3	fire

Syv blokke (søjler) danner en biplan af orden 2 (symmetrisk skema (7,4,2)).

Noter

↑ Stinson, 2003 , s. en.
↑ 1 2 3 Rybnikov, 1972 , s. 130.
↑ Stinson, 2003 , s. IX.
↑ Beth, Jungnickel, Lenz, 1999 , s. 40 Eksempel 5.8.
↑ Ryser, 1963 , s. 52 Sætning 3.1.
↑ Hvis G er en abelsk gruppe (eller er skrevet med en additionsoperation), har definitionen formen d 1 –d 2 , hvorfra termen differensmængde er opstået .
↑ Beth, Jungnickel, Lenz, 1999 , s. 262 Sætning 1.6.
↑ Stinson, 2003 , s. 74 Sætning 4.5.
↑ Stinson, 2003 , s. 193 Sætning 8.20.
↑ Stinson, 2003 , s. 183, Sætning 8.5.
↑ Colbourn, Dinitz, 2007 .
↑ Colbourn, Dinitz, 2007 , s. 331 Eksempel 2.2.
↑ Colbourn, Dinitz, 2007 , s. 331 Bemærkning 2.8.
↑ Colbourn, Dinitz, 2007 , s. 333, Bemærkning 3.3.
↑ Colbourn, Dinitz, 2007 , s. 496 Sætning 28.5.
↑ Colbourn, Dinitz, 2007 , s. 497 Sætning 28.15.
↑ Colbourn, Dinitz, 2007 , s. 503 Anmærkning 29.38.
↑ Colbourn, Dinitz, 2007 , s. 512 Eksempel 32.4.
↑ Colbourn, Dinitz, 2007 , s. 512, Bemærkning 32.3.
↑ Colbourn, Dinitz, 2007 , s. 530 Sætning 35,15.
↑ Colbourn, Dinitz, 2007 , s. 577 Sætning 47,15.
↑ Colbourn, Dinitz, 2007 , s. 578-579.
↑ Colbourn, Dinitz, 2007 , s. 579 Sætning 48.10.
↑ Colbourn, Dinitz, 2007 , s. 580 Lemma 48,22.
↑ Colbourn, Dinitz, 2007 , s. 652 Eksempler 62.4.
↑ Colbourn, Dinitz, 2007 , s. 655 Sætning 62,24.
↑ Colbourn, Dinitz, 2007 , s. 657.
↑ Colbourn, Dinitz, 2007 , s. 658 Eksempel 63.5.
↑ Colbourn, Dinitz, 2007 , s. 669 Bemærkning 65.3.

Litteratur

Rybnikov K.A. Introduktion til kombinatorisk analyse. - Moscow State University, 1972.
Tarannikov Yu. V. Kombinatoriske egenskaber af diskrete strukturer og applikationer til kryptologi. - MTSNMO, 2011. - ISBN 978-5-94057-812-3 .
Hall M. Combinatorics. - MIR, 1966.
Assmus EF, Key JD Designs og deres koder. - Cambridge: Cambridge University Press, 1992. - ISBN 0-521-41361-3 .
Beth T., Jungnickel D., Lenz H. Design Theory. - Cambridge: Cambridge University Press , 1999. - ISBN 978-0-521-44432-3 .
Bose RC En note om Fishers ulighed for balancerede ufuldstændige blokdesigns // Annals of Mathematical Statistics . - 1949. - S. 619-620 .
Caliński T., Kageyama S. Blokdesign : A Randomization approach, bind 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 En undersøgelse af de forskellige mulige løsninger på et problem i ufuldstændige blokke // Annals of Eugenics . - 1940. - T. 10 . — S. 52–75 .
Hall Marshall Jr. kombinatorisk teori. — 2. - New York: Wiley-Interscience, 1986. - ISBN 0-471-09138-3 .
Hughes DR, Piper EC Design teori . - Cambridge: Cambridge University Press, 1985. - ISBN 0-521-25754-9 .
Lander ES Symmetric Designs: An Algebraic Approach. — Cambridge: Cambridge University Press, 1983.
Lindner CC, Rodger CA Design Theory . - Boca Raton: CRC Press, 1997. - ISBN 0-8493-3986-3 .
Raghavarao D. Konstruktioner og kombinatoriske problemer i design af eksperimenter. — rettet genoptryk af Wiley fra 1971. — New York: Dover, 1988.
Raghavarao D., Padgett LV Block Designs: Analysis, Combinatorics and Applications. - World Scientific, 2005.
Ryser Herbert John. Kapitel 8: Kombinatoriske designs // Kombinatorisk matematik (Carus Monograph #14). - Mathematical Association of America, 1963.
Shrikhande SS, Vasanti NB-N. Ikke-isomorfe løsninger af nogle afbalancerede ufuldstændige blokdesigns I – // Journal of Combinatorial Theory . - 1970.
Stinson Douglas R. Kombinatoriske designs: konstruktioner og analyse. - New York: Springer, 2003. - ISBN 0-387-95487-2 .
Street Anne Penfold, Street Deborah J. Combinatorics of Experimental Design. - Oxford UP [Clarendon], 1987. - S. 400+xiv. — ISBN 0-19-853256-3 .
van Lint, JH, og R.M. Wilson. Et kursus i kombinatorik. — Cambridge, Eng.: Cambridge University Press, 1992.