Kombinatorinen kaava

Kombinatoristen kaavioiden teoria on osa kombinatoriikkaa ( matematiikan haara ), joka tarkastelee äärellisten joukkojen , joiden rakenne täyttää yleistetyt tasapaino- ja/tai symmetriakäsitteet , olemassaoloa, rakentamista ja ominaisuuksia . Näitä käsitteitä ei ole määritelty tarkasti, joten monet objektit voidaan ymmärtää kombinatorisina skeemoina. Joten yhdessä tapauksessa kombinatoriset mallit voivat edustaa lukujoukkojen leikkauskohtia, kuten vuokaavioissa , ja toisessa tapauksessa ne voivat kuvastaa elementtien järjestelyä Sudokussa .

Kombinatoristen kaavioiden teoriaa voidaan käyttää kokeiden suunnittelussa . Jotkut kombinatorisista peruskaavioista on esitetty Ronald Fisherin teoksessa biologisten kokeiden teoriasta. Kombinatorisia järjestelmiä löytyy nyt useilta aloilta, mukaan lukien äärellinen geometria , turnausaikataulut , arpajaiset , matemaattinen biologia , algoritmien suunnittelu ja analysointi , tietokoneverkot , ryhmätestaus ja kryptografia [1] .

Määritelmä

Merkitse - elementtijoukko . _ Harkitse tämän joukon osajoukkoja . Jokaista osajoukkoa kutsutaan lohkoksi, ja siinä olevien joukkoelementtien lukumäärää kutsutaan lohkon tilavuudeksi, ja sitä merkitään . Antaa olla tämän elementin sisältävien osajoukkojen lukumäärä . Toistojen lukumäärä (järjestämättömät parit) on merkitty . Sitten lohkojoukko muodostaa kombinatorisen kaavion (tai lohkokaavion) parametreilla [2] . $v$ ${\displaystyle m_{1},m_{2},...,m_{v))$ ${\displaystyle M_{1},M_{2},...,M_{b))$ $M_{j}$ $M_{j}$ ${\näyttötyyli k_{j))$ ${\displaystyle r_{i))$ $M$ $\lambda _{p}$ ${\displaystyle M_{1},M_{2},...,M_{b))$ ${\displaystyle v,b,r_{i},k_{j},\lambda _{p))$

Esimerkki

Jos on n henkilöä, voidaanko niistä muodostaa joukkoja siten, että jokainen henkilö kuuluu vähintään yhteen joukkoon, jokainen pari kuuluu täsmälleen yhteen joukkoon, joka kahdessa joukossa on vain yksi henkilö risteyksessä, eikä mikään joukoista koostu kaikista ihmisistä, kaikista ihmisistä miinus yksi vai täsmälleen yksi henkilö? Vastaus riippuu n :stä .

Vastaus on kyllä vain, jos n on muotoa q 2 + q + 1. Ratkaisun olemassaoloa on vaikeampi todistaa, jos q on alkupotentti . On olemassa olettamus, ettei muita ratkaisuja ole. On todistettu, että jos q :lle on olemassa ratkaisu, jotka ovat kongruentteja 1 tai 2 modulo 4:n kanssa, niin q on kahden täydellisen neliön summa . Tämä tulos, Brook-Reiser-Chowlin lause , todistettiin yhdistelmällä äärellisiin kenttiin ja neliömuotoihin perustuvia rakennusmenetelmiä .

Kun tällainen rakenne on olemassa, sitä kutsutaan äärelliseksi projektiivitasoksi . Tämä osoittaa, kuinka äärellisten geometrioiden teoria ja kombinatoriikka leikkaavat toisiaan. Tapauksessa q = 2, projektiivista tasoa kutsutaan Fanon tasoksi .

Historia

Kombinatoriset suunnitelmat ovat olleet tunnettuja antiikista lähtien Lo Shu -aukion muodossa , joka oli varhainen versio maagisesta neliöstä . Kombinatoriset järjestelmät ovat kehittyneet kombinatoriikan kehityksen myötä 1700-luvulta lähtien, esimerkiksi latinalaisina neliöinä 1700-luvulla ja Steiner-järjestelminä 1800-luvulla. Kombinatoriset menetelmät ovat suosittuja myös viihdyttävässä matematiikassa , kuten Kirkmanin koulutyttöongelma (1850), ja käytännön ongelmissa, kuten round robin -turnausten aikatauluissa (1880-luvulla julkaistu ratkaisu). 1900-luvulla kombinatorisia järjestelmiä sovellettiin kokeiden , äärellisten geometrioiden ja suhdekaavioiden suunnitteluun, ja ne johtivat algebrallisten tilastojen syntymiseen .

Perusteelliset kombinatoriset mallit

Kombinatoristen kaavioiden aiheen klassinen ydin on rakennettu tasapainotetun epätäydellisen lohkosuunnittelun (en: Balanced Incomplete Block Design, BIBD), matriisien ja Hadamardin kaavioiden , symmetrisen BIBD :n , latinalaisten neliöiden , erotettavissa olevan BIBD :n , erotusjoukkojen ja pareittain tasapainotettujen skeemojen ympärille. (en: Pairwise Balanced Design , PBD) [3] . Muut kombinatoriset järjestelmät liittyvät mainittuihin järjestelmiin tai perustuvat niihin.

Tasapainotettu epätäydellinen lohkokaavio (BIBD), jota kutsutaan lyhennettynä lohkokaavioiksi , on v -elementtien rajallisen joukon X b osajoukon (kutsutaan lohkoiksi ) joukko B siten , että mikä tahansa joukon X elementti sisältyy joihinkin lukuisiin r lohkoihin, jokaisessa lohkossa on sama määrä elementtejä (= k ) ja jokainen eri elementtien pari esiintyy samassa määrässä ( ) lohkoja [2] . BIBD-piirejä kutsutaan myös 2-piireiksi ja niitä kutsutaan usein piireiksi. Esimerkkinä tapaukselle ja b = v saadaan projektiivinen taso - X on tässä tapauksessa tason pisteiden joukko ja lohkot ovat suoria viivoja. $=\lambda$ $2-(v,k,\lambda )$ $\lambda=1$
Symmetric Balanced Incomplete Block Design eli SBIBD (en: Symmetric Balanced Incomplete Block Design) on BIBD, jossa v = b (pisteiden määrä on yhtä suuri kuin lohkojen määrä). Tämä on BIBD:n tärkein ja parhaiten tutkittu alaluokka. Projektiiviset tasot, kaksitasot ja Hadamard 2 -skeemat ovat SBIBD-skeemoja. Nämä suunnitelmat ovat kiinnostavia ääriesimerkkeinä Fisherin epätasa-arvosta ( ). $b\geqslant v$
Ratkaistava tasapainotettu epätäydellinen lohkokaavio on BIBD, jonka lohkot voidaan jakaa sarjoiksi (kutsutaan rinnakkaisluokiksi ), joista jokainen muodostaa BIBD [2] pistejaon . Rinnakkaisten luokkien joukkoa kutsutaanskeeman resoluutioksi . Ratkaisu kuuluisaan 15 opiskelijan ongelmaan on BIBD-resoluutio, jossa v = 15, k = 3 ja [4] . $\lambda=1$
Latinalainen suorakulmio onr × n( r ≤ n)-matriisi, jonka elementteinä on numerot 1, 2, 3, ..., n(tai mikä tahansa muuneri merkin joukko), jossa yksikään numero ei esiinny kahdesti mikä tahansa rivi tai sarake. Latinalaistasuorakulmiota, jonka mitat ovatn × nkutsutaanlatinalaisiksi neliöiksi. Josr < n, voidaanr × nn − rriviälatinalaisen neliön muodostamiseksi käyttämälläHallin häälauselausetta [5] .

Sanomme, että kaksi latinalaista neliötä, joiden kertaluku on n , ovat ortogonaalisia , jos kahden neliön vastaavista alkioista koostuvien kaikkien järjestettyjen parien joukko koostuu n 2 eri parista (eli kaikki mahdolliset järjestetyt parit esiintyvät). Saman järjestyksen latinalaisten neliöiden joukko muodostaa joukon keskenään ortogonaalisia latinalaisia neliöitä (en: Mutually Orthogonal Latin Squares, MOLS), jos jokin joukon latinalaisista neliöistä on ortogonaalinen. Tällaisessa kertaluvun n neliöjoukossa voi olla enintään n − 1 neliötä . Joukkoa n − 1 MOLS-neliötä, joiden kertaluku on n , voidaan käyttää projektiivisen tason rakentamiseen (ja päinvastoin).

Erotusjoukko onluokanvryhmänGosajoukkoD, jonkakokokGole yhtä suuri kuin yksi,voidaan esittäätulonad1d2−1Dtäsmälleen samallatavalla (josG:tä edustaa kertolasku) [6] . $(v,k,\lambda )$ $\lambda$

Jos D on erotusjoukko ja g kuuluu G :hen , niin se on myös erojoukko ja sitä kutsutaan joukon D käännökseksi . Erotusjoukon D siirtojen joukko muodostaa symmetrisen lohkokaavion . Tällaisessa järjestelmässä on v - elementtejä ja v - lohkoja. Kukin kaavion lohko koostuu k pisteestä, jokainen piste sisältyy k lohkoon. Kaikissa kahdessa lohkossa on täsmälleen samat elementit, ja mitkä tahansa kaksi pistettä näkyvät yhdessä lohkoina. Tätä mallia SBIBD kutsutaan joukon D kehitykseksi [7] .

g\mathbf {D} ={gd\kaksoispiste d\in \mathbf {D} }

\lambda

\lambda

Erityisesti, jos Ero joukko muodostaa projektiivisen tason . Esimerkiksi erojoukko (7,3,1) ryhmän yli ( Abelin ryhmä additiivisella merkinnällä) on {1,2,4}:n osajoukko. Tämän erosarjan kehitys antaa Fanon koneen .

\lambda=1

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

Koska mikä tahansa erotusjoukko tuottaa SBIBD:n, parametrijoukon on täytettävä Brook-Reiser-Chowl-lause , mutta jokainen SBIBD-malli ei tuota erotusjoukkoa.

Hadamard-matriisi, jonka kertaluku on m , on m × m -matriisi H , jonka alkiot ovat ±1 siten, että HH ⊤ = m E m , missä H ⊤ on H:n transposi ja E m on m × m identtisyysmatriisi . Hadamard-matriisi voidaan pelkistää standardoituun muotoon (eli muuntaa vastaavaksi Hadamard-matriisiksi), jossa ensimmäisen rivin ja ensimmäisen sarakkeen merkinnät ovat +1. Jos järjestys m > 2, niin m :n on oltava jaollinen 4:llä.

Kun annetaan Hadamard-matriisi, jonka kertaluku on 4a standardoidussa muodossa, poista ensimmäinen rivi ja ensimmäinen sarake ja korvaa sitten kaikki −1 arvolla 0. Tuloksena oleva 0-1 matriisi M on symmetrisen piirin, jota kutsutaan Hadamardin 2-piiriksi , ilmaantuvuusmatriisi [8] . Tämä rakenne on reversiibeli, joten symmetrisen 2-piirin tulomatriisia näillä parametreilla voidaan käyttää Hadamard-matriisin saamiseksi luokkaa 4a . Tapauksessa a = 2 saadaan jo tuttu Fano-taso (Hadamard 2-kaaviona).

{\näyttötyyli 2-(4a-1,2a-1,a-1)}

Parittain tasapainotettu malli (en: Pairwise Balanced Design, PBD) on joukko X yhdessä X:n osajoukkojen perheen kanssa ( ei välttämättä samankokoisia ja osajoukot voivat olla samat), niin että mikä tahansa pari X :stä erillisiä elementtejä sisältyy tarkalleen (positiiviseen määrään) osajoukkoja . Joukko X saa olla osa perhettä, ja jos kaikki osajoukot ovat kopioita joukosta X , PBD-mallin sanotaan olevan triviaali . Joukon X koko on v ja osajoukkojen lukumäärä perheessä (identtiset osajoukot lasketaan erikseen) on b . $\lambda$

Fisherin epätasa-arvo PBD-järjestelmille täyttyy [9] – minkä tahansa ei-triviaalin PBD-järjestelmän osalta .

v\leqslant b

Tämä tulos yleistää kuuluisan de Bruijn-Erdősin lauseen - mikä tahansa PBD-skeema, jossa on , jossa ei ole 1- tai v -kokoisia lohkoja , on totta ja yhtäläisyys pätee jos ja vain, jos kaavio on projektiivinen taso tai melkein nippu [10] .

\lambda=1

v\leqslant b

Muut kombinatoriset mallit

Colbournen ja Dinitzin käsikirja Combinatorial Designs [11] sisältää muun muassa 65 lukua muista kuin edellä mainituista kombinatorisista suunnitelmista. Alla on osittainen luettelo.

Parisuhdesuunnitelmat
Balanced ternary design (en: Balanced Ternary Design) on V - elementtien järjestely B - multijoukoissa (lohkot, kunkin joukon kardinaliteetti on K ( K ≤ V )), joka täyttää ehdot: $BTD(V,B;\rho _{1},\rho _{2},R;K,\Lambda )$

Jokainen elementti esiintyy kerran 1-kertoimella (1 esiintymä monijoukossa) täsmälleen lohkoissa ja 2-kertoimella täsmälleen lohkoissa. ${\displaystyle R=\rho _{1}+2\rho _{2))$ $\rho_{1}$ $\rho _{2}$
Jokainen eri elementtipari esiintyy kerran (monisuoritus huomioon ottaen). Eli jos m vb on elementin v monikerta lohkossa b , niin mille tahansa eri alkioparille v ja w . $\lambda$ $\sum _{b=1}^{B}m_{vb}m_{wb}=\Lambda$

Esimerkiksi toinen kahdesta ei-isomorfisesta kaaviosta BTD(4,8;2,3,8;4,6) (sarakkeet toimivat lohkoina) on [12]

yksi	yksi	yksi	2	2	3	yksi	yksi
yksi	yksi	yksi	2	2	3	2	2
2	3	neljä	3	neljä	neljä	3	3
2	3	neljä	3	neljä	neljä	neljä	neljä

BTD- skeeman (jonka elementit ovat elementtien monikerroinisia lohkoissa) esiintymismatriisia voidaan käyttää muodostamaan ternäärisiä virheenkorjauskoodeja samalla tavalla kuin BIBD-mallien esiintymismatriiseista muodostettaessa binäärikoodeja [13] .

Tasapainoinen turnauspiiri , jonka järjestys onn(BTD(n2n-joukonVkaikkien erillisten järjestämättömien parienn × (2ntaulukkoon siten, että

jokainen V :n elementti esiintyy täsmälleen kerran kussakin sarakkeessa
jokainen joukon V alkio esiintyy enintään kahdesti kullakin rivillä.

Esimerkki BTD(3) -skeemasta

16	3 5	2 3	4 5	24
25	4 6	neljätoista	13	3 6
3 4	12	5 6	26	viisitoista

Kaavan BTD( n ) sarakkeet antavat 1-kertoimen koko graafille , jossa on 2 n kärkeä, K 2n [14] . BTD( n ) -skeemoja voidaan käyttää round robin -turnausten ajoittamiseen - rivit edustavat paikkoja, sarakkeet kiertomatkoja (kierroksia, ympyröitä) ja taulukkomerkinnät määrittelevät pelaajia tai joukkueita.

Taivutetut toiminnot
Joukko Costasia
Täydelliset tekijäkokeet
Taajuusneliö ( F - neliö ) on latinalaisen neliön yleistys . Olkoon S = { s 1 , s 2 , ..., s m } joukko erilaisia symboleja ja positiivisten lukujen taajuusvektori . N: n kertaluvun taajuusneliö on n × n -taulukko, jossa jokainen merkki s i esiintyy kerran ( i = 1,2,...,m) jokaisella rivillä ja jokaisessa sarakkeessa. Taajuusneliöllä on vakiomuoto, jos elementit s i edeltävät s j :tä ensimmäisellä rivillä ja ensimmäisessä sarakkeessa i < j : lle . $(\lambda _{1},\lambda _{2},...,\lambda _{m})$ $(n=\lambda _{1}+\lambda _{2}+...+\lambda _{m})$ $\lambda _{i}$

Taajuusneliö F 1, jonka kertaluku on n joukossa { s 1 , s 2 , ..., s m }, jossa on taajuusvektori, ja taajuusneliö F 2 , joka on myös luokkaa n joukossa , jossa on taajuusvektori, ovat ortogonaalisia , jos sellaisia on järjestetty pari ( s i , t j ) näkyy täsmälleen kerran, kun F 1 ja F 2 menevät päällekkäin.

(\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) on Steiner Triple System (STS) (jossa lohkoja kutsutaan viivoiksi ), joiden ominaisuus on, että kahden suoran leikkauspisteestä muodostuva alirakenne on isomorfinen äärellisen affiinin tason AG(2 ,3) kanssa.

Mikä tahansa affiiniavaruus AG( n ,3) antaa esimerkin HTS-skeemasta, tällaisia skeemoja kutsutaan affiinisiksi HTS:iksi. On olemassa myös ei-affine HTS-järjestelmiä. Pisteiden määrä HTS-kaaviossa on 3 m jollekin kokonaisluvulle . Ei-affiineja HTS-järjestelmiä on olemassa kaikille, eikä niitä ole olemassa 3 :lle [15] .

m\geqslant 2

m\geqslant 4

m=2

Mikä tahansa Steinerin kolmoisjärjestelmä vastaa Steinerin kvasiryhmää ( idempotentti , kommutatiivinen ja pätee kaikille x ja y : ille ). Hallin kolmoisjärjestelmä vastaa Steinerin kvasiryhmää, jonka distributiivinen ominaisuus on, eli se pätee kvasiryhmän kaikille a,x,y:ille [16] .

{\näyttötyyli (xy)y=x}

a(xy)=(ax)(ay)

Olkoon S joukko 2n alkiota. Howell-skeema , H( s ,2 n ) (merkistössä S ) on s × s -taulukko , jossa:

Jokainen taulukon solu on joko tyhjä tai sisältää järjestämättömän parin S :stä ,
Jokainen merkki esiintyy täsmälleen kerran taulukon kullakin rivillä ja sarakkeessa,
Jokainen järjestämätön pari esiintyy enintään yhdessä taulukon solussa.

Kaavioesimerkki H(4,6)

0 4		13	25
2 3	neljätoista	0 5
	3 5	24	0 1
viisitoista	0 2		3 4

H(2 n − 1, 2 n ) on Rommin neliö , jonka sivu on 2 n − 1, joten Howellin kaaviot yleistävät Rommin neliöiden käsitteen. Howell-kaavion soluissa olevat symboliparit voidaan ajatella säännöllisen graafin , jossa on 2n kärkeä, reunoiksi s , jota kutsutaan Howell-kaavion päägraafiksi . Howellin syklisiä skeemoja käytetään Howellin liikkeinä (pelin loppuunsaattamiskaavio) kaksoissiltaturnauksissa . Kaavion rivit edustavat kierroksia (ympyröitä), sarakkeet edustavat laatikoita (ennakolta laaditut tarjoukset, katso "Silta - valmistautuminen peliin" ) ja diagonaalit taulukoita [17] .

Lineaariset tilat
Lottokaavio ( n , k , p , t ) on joukko V , jossa on n elementtiä yhdessä k - alkioisten osajoukkojen (lohkojen) kanssa siten, että jokaiselle osajoukolle P , joka koostuu joukon V p elementistä , on olemassa lohko B , jolle . L( n , k , p , t ) tarkoittaa pienintä lohkojen määrää missä tahansa lottojärjestelmässä ( n , k , p , t ). Lottokaavio (7,5,4,3) pienimmällä mahdollisella lohkomäärällä [18] : $\beeta$ $\beeta$ $|P\cap B|\geqslant t$

{1,2,3,4,7} {1,2,5,6,7} {3,4,5,6,7}. Lottomalli mallintaa mitä tahansa lottoa seuraavilla säännöillä: Pelaaja ostaa liput , jotka sisältävät k numeroa, jotka valitaan n numeroa sisältävästä sarjasta . Jossain vaiheessa lipunmyynti pysähtyy ja valitaan satunnainen joukko p -numeroita, jotka sisältyvät alkuperäiseen n numeron joukkoon. Nämä ovat voittonumerot . Jos myyty lippu sisältää t tai useampia voittonumeroita, palkinto luovutetaan lipun haltijalle. Mitä enemmän otteluita, sitä suurempi voitto. Luku L( n , k , p , t ) kiinnostaa sekä pelaajia että tutkijoita, koska se edustaa pienintä määrää lippuja, jotka on ostettava voiton takaamiseksi. Unkarilainen lotto on lottojärjestelmä (90,5,5, t ) ja tiedetään, että L(90,5,5,2) = 100. Arpajaiset parametreillä (49,6,6, t ) ovat suosittuja kaikkialla maailman ja tunnetaan , että L(49,6,6,2) = 19. Yleensä näitä lukuja on vaikea laskea ja ne pysyvät tuntemattomina [19] . Yhden näistä kaavioista geometrinen rakenne on esitetty artikkelissa " Transilvanian Lottery ".

maagisia neliöitä
Mendelssohn-skeema ( ) on joukko V , jossa on v elementtejä ja joukko järjestettyjä k - sarjoja joukon V erillisistä elementeistä (kutsutaan lohkoiksi ) siten, että kukin järjestetyt pari ( x , y ) V :stä ( x ≠ y ) on jaksollisesti vierekkäinen lohkoissa ( erillisten elementtien järjestetty pari ( x , y ) on jaksollisesti vierekkäinen lohkossa, jos elementit esiintyvät lohkossa vierekkäin — joko (..., x , y ,...) tai ( y ,..., x )). Järjestelmä on Mendelssohnin kolminkertainen järjestelmä , nimeltään MTS . MTS(4,1) esimerkki V = {0,1,2,3}: $(\mathbf {v} ,\mathbf {k} ,{\boldsymbol {\lambda )))$ $MD(\mathbf {v} ,\mathbf {k} ,{\boldsymbol {\lambda )))$ $\beeta$ $\lambda$ $MD(\mathbf {v} ,\mathbf {3} ,{\boldsymbol {\lambda )))$ $(\mathbf {v} ,{\boldsymbol {\lambda )))$

(0.1.2) (1.0.3) (2.1.3) (0.2.3) Mikä tahansa kolmoisjärjestelmä voidaan muuntaa Mendelssohnin kolmoisjärjestelmäksi korvaamalla järjestämätön kolmio { a , b , c } parilla järjestetyillä kolmioilla ( a , b , c ) ja ( a , c , b ), mutta päinvastoin ei pidä paikkaansa, kuten esimerkki osoittaa. Olkoon ( Q ,∗) idempotentti puolisymmetrinen kvasiryhmä , eli x ∗ x = x (idempotentti) ja x ∗ ( y ∗ x ) = y (puolisymmetrinen) pätee siinä kaikille x , y Q :sta . Anna . Sitten on Mendelssohnin kolminkertainen järjestelmä MTS(| Q |,1). Tämä rakenne on käännettävissä [20] .

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

(Q,\beta )

Ortogonaaliset taulukot
Kvasi -3-piiri on symmetrinen piiri (SBIBD), jossa jokainen lohkokolmoinen leikkaa joko x- tai y -pisteissä kiinteillä x- ja y -luvuilla , joita kutsutaan kolminkertaisiksi leikkausluvuiksi ( x < y ). Mikä tahansa symmetrinen piiri, jossa on , on kvasi-3-piiri, jossa on ja . Geometrian PG ( n , q ) piste-hypertasokaavio on kvasi-3-kaavio, jossa ja . Jos kyseessä on kvasi-3-piiri, piiri on isomorfinen PG :n ( n , q ) tai projektiivitason kanssa [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$
Piiri on kvasisymmetrinen leikkausnumeroiden x ja y kanssa ( x < y ), jos kahdella erillisellä lohkolla on joko x tai y pisteet leikkauspisteessä. Nämä skeemat syntyvät luonnollisesti tutkittaessa kaksoisskeemoja . Epäsymmetrinen piiri ( b > v ) 2-( v , k ,1) on kvasisymmetrinen, kun x = 0 ja y = 1. Useita (lohkoja toistetaan tietty määrä kertoja) symmetriset 2 -piirit ovat kvasi- symmetrinen ja y = k . Hadamard 3 -skeemat ( Hadamard 2 -skeemojen laajennus ) ovat kvasisymmetrisiä [22] . $Dt-(v,k,\lambda )$ $\lambda=1$ $(v,k,\lambda )$ $x=\lambda$

Mikä tahansa kvasisymmetrinen lohkokaavio generoi vahvasti säännöllisen graafin (kuten sen lohkokaavio ), mutta kaikkia SRG-piirejä ei generoida tällä tavalla [23] . Kvasisymmetrisen piirin 2- ilmaantuvuusmatriisi k ≡ x ≡ y (mod 2) muodostaa binaarisen itseortogonaalisen koodin [24] .

(v,k,\lambda )

Rommin neliöt
Pallomalli on äärellinen joukkoXpisteitä a (d − 1)-ulotteisellapallollasiten, että jollekin kokonaisluvulletpolynominkeskiarvoX

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

jonka aste ei ylitä t on yhtä suuri kuin f :n keskiarvo koko pallolla (eli funktion f integraali jaettuna pallon pinta-alalla).

Turan-järjestelmät
Toscanan r × n k -suorakulmiossa n merkin päällä on r riviä ja n saraketta , kun taas

jokainen rivi on n merkin permutaatio
kahdelle erilliselle merkille a ja b ja jokaiselle luvulle m välillä 1 - k on enintään yksi rivi, jossa b on m askelta a :n oikealla puolella .

Jos r = n ja k = 1, kaavioita kutsutaan Toscanan neliöiksi , kun taas tapauksissa r = n ja k = n - 1 niitä kutsutaan Firenzen neliöiksi . Roomalainen neliö on Toscanan neliö, joka on myös latinalainen neliö (tällaisia neliöitä kutsutaan myös rivin täydellisiksi latinalaisiksi neliöiksi ). Vatikaanin aukio on Firenzen aukio, joka on myös Latinalainen aukio. Esimerkki Toscanan 1-neliöstä, jossa on 7 merkkiä, joka ei ole 2-neliö [25] :

6	yksi	5	2	neljä	3	7
2	6	3	5	neljä	7	yksi
5	7	2	3	yksi	neljä	6
neljä	2	5	yksi	6	7	3
3	6	2	yksi	7	neljä	5
yksi	3	2	7	5	6	neljä
7	6	5	3	neljä	yksi	2

Toscanan neliö n symbolilla vastaa n pisteen täydellisten graafien hajottamista n Hamiltonin suuntaisiksi poluiksi [26] .

Tyypin t - t-kertainen tasapainotettu piiri (tai t - BD) on v -elementtien joukko X yhdessä X:n osajoukkojen perheen kanssa ( kutsutaan lohkoiksi ), joiden koot sisältyvät joukkoon K siten, että mikä tahansa t -osajoukko X :n elementit sisältyvät täsmälleen lohkoihin. Jos K on joukko positiivisia kokonaislukuja tiukasti välillä t ja v , niin kaaviota t BD kutsutaan oikeaksi . Jos kaikki X :n k -osajoukot joillekin k :lle ovat lohkoja, niin kaaviota t BD kutsutaan triviaaliksi [27] . $(v,K,\lambda )$ $\lambda$

Huomaa, että esimerkin 3-{12,{4,6},1) kaavioissa joukossa X = {1,2,...,12} jotkut parit esiintyvät neljä kertaa (esimerkiksi pari {1, 2}), kun taas toiset esiintyvät viisi kertaa (esimerkiksi pari {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

Epätäydellinen latinalainen neliö on k × v suorakaiteen muotoinen taulukko ( k < v ) v , jossa on merkkejä siten , että jokainen merkki esiintyy täsmälleen kerran kullakin rivillä ja missä tahansa sarakkeessa esiintyvät merkit muodostavat symmetrisen piirin lohkoja , joiden kaikki lohkot esiintyvät täsmälleen kerran . Epätäydellinen latinalainen neliö on latinalainen suorakulmio. Otsikon termi "neliö" tulee vanhemmasta määritelmästä, jossa käytettiin neliötaulukkoa [29] . Esimerkki epätäydellisestä latinalaisesta 4×7 neliöstä: $(v,k,\lambda )$

yksi	2	3	neljä	5	6	7
2	3	neljä	5	6	7	yksi
3	neljä	5	6	7	yksi	2
5	6	7	yksi	2	3	neljä

Seitsemän lohkoa (saraketta) muodostaa kaksitasoisen kertaluvun 2 (symmetrinen kaavio (7,4,2)).

Muistiinpanot

↑ Stinson, 2003 , s. yksi.
↑ 1 2 3 Rybnikov, 1972 , s. 130.
↑ Stinson, 2003 , s. IX.
↑ Beth, Jungnickel, Lenz, 1999 , s. 40 Esimerkki 5.8.
↑ Ryser, 1963 , s. 52 Lause 3.1.
↑ Jos G on Abelin ryhmä (tai kirjoitetaan summausoperaatiolla), määritelmä saa muotoa d 1 –d 2 , josta termierojoukko syntyi .
↑ Beth, Jungnickel, Lenz, 1999 , s. 262 Lause 1.6.
↑ Stinson, 2003 , s. 74 Lause 4.5.
↑ Stinson, 2003 , s. 193 Lause 8.20.
↑ Stinson, 2003 , s. 183, Lause 8.5.
↑ Colbourn, Dinitz, 2007 .
↑ Colbourn, Dinitz, 2007 , s. 331 Esimerkki 2.2.
↑ Colbourn, Dinitz, 2007 , s. 331 Huomautus 2.8.
↑ Colbourn, Dinitz, 2007 , s. 333, huomautus 3.3.
↑ Colbourn, Dinitz, 2007 , s. 496 Lause 28.5.
↑ Colbourn, Dinitz, 2007 , s. 497 Lause 28.15.
↑ Colbourn, Dinitz, 2007 , s. 503 Huomautus 29.38.
↑ Colbourn, Dinitz, 2007 , s. 512 Esimerkki 32.4.
↑ Colbourn, Dinitz, 2007 , s. 512, huomautus 32.3.
↑ Colbourn, Dinitz, 2007 , s. 530 Lause 35.15.
↑ Colbourn, Dinitz, 2007 , s. 577 Lause 47.15.
↑ Colbourn, Dinitz, 2007 , s. 578-579.
↑ Colbourn, Dinitz, 2007 , s. 579 Lause 48.10.
↑ Colbourn, Dinitz, 2007 , s. 580 Lemma 48.22.
↑ Colbourn, Dinitz, 2007 , s. 652 Esimerkit 62.4.
↑ Colbourn, Dinitz, 2007 , s. 655 Lause 62.24.
↑ Colbourn, Dinitz, 2007 , s. 657.
↑ Colbourn, Dinitz, 2007 , s. 658 Esimerkki 63.5.
↑ Colbourn, Dinitz, 2007 , s. 669 Huomautus 65.3.

Kirjallisuus

Rybnikov K.A. Johdatus kombinatoriseen analyysiin. - Moskovan valtionyliopisto, 1972.
Tarannikov Yu. V. Erillisten rakenteiden kombinatoriset ominaisuudet ja sovellukset kryptologiassa. - MTSNMO, 2011. - ISBN 978-5-94057-812-3 .
Hall M. Kombinatoriikka. - MIR, 1966.
Assmus EF, keskeiset JD- mallit ja niiden koodit. - Cambridge: Cambridge University Press, 1992. - ISBN 0-521-41361-3 .
Beth T., Jungnickel D., Lenz H. Suunnitteluteoria. - Cambridge: Cambridge University Press , 1999. - ISBN 978-0-521-44432-3 .
Bose RC Huomautus Fisherin epätasa-arvosta tasapainoisille epätäydellisille lohkomalleille // 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. - (Luentomuistiinpanot tilastoista). — 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 Ongelman eri mahdollisten ratkaisujen tarkastelu epätäydellisissä lohkoissa // Annals of Eugenics . - 1940. - T. 10 . - S. 52-75 .
Hall Marshall Jr. kombinatorinen teoria. – 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 Symmetric Designs: 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. Rakenteet ja kombinatoriset ongelmat kokeiden suunnittelussa. – korjattu uusintapainos vuoden 1971 Wileystä. – New York: Dover, 1988.
Raghavarao D., Padgett LV Block Designs: analyysi, kombinatoriikka ja sovellukset. – World Scientific, 2005.
Ryser Herbert John. Luku 8: Kombinatoriset mallit // Kombinatorinen matematiikka (Carus Monograph #14). - Mathematical Association of America, 1963.
Shrikhande SS, Vasanti NB-N. Joidenkin tasapainotettujen epätäydellisten lohkosuunnitelmien ei-isomorfiset ratkaisut I – // Journal of Combinatorial Theory . – 1970.
Stinson Douglas R. Kombinatoriset mallit: Rakenteet ja analyysi. - New York: Springer, 2003. - ISBN 0-387-95487-2 .
Street Anne Penfold, Street Deborah J. Combinatoriics of Experimental Design. - Oxford UP [Clarendon], 1987. - P. 400+xiv. — ISBN 0-19-853256-3 .
van Lint, JH ja R.M. Wilson. Kombinatorian kurssi. - Cambridge, Eng.: Cambridge University Press, 1992.