U literaturi se mogu pronaći brojni primjeri takozvanih numeričkih trokutova. Riječ je o rasporedu brojeva u trokutastu formu prema određenim zakonitostima. Takvi rasporedi sadržavaju zanimljive pravilnosti i često su povezani s rekreativnom matematikom, ali se mogu pojaviti i u ozbiljnim matematičkim teorijama i njihovim primjenama.

Pascalov trokut za binomne koeficijente vjerojatno je najpoznatija takva shema. Njegova konstrukcija, ilustrirana Slikom 1, temelji se na poznatoj rekurziji {\binom{{n}}{{k}}}={\binom{n{-1}}{k{-1}}+\binom{n{-1}}{k} }, gdje su n i k nenegativni cijeli brojevi. Pascalov trokut za binomne koeficijente ima mnoge zanimljive pravilnosti i primjene. O tome postoje brojni tekstovi, kakvi su primjerice [3], [7] ili [8]. Ovdje govorimo o jednoj njegovoj analogiji vezanoj uz kombinatorne dizajne.

Kombinatorna teorija dizajna, ili kraće teorija dizajna, je grana diskretne matematike. Za njen nastanak povijesno je važan primjer poznat kao Kirkmanov problem 15 učenica iz 1850. godine, a glasi ovako: Učitelj svakog dana šalje u šetnju svojih 15 učenica. One šeću u 5 grupa, u svakoj po 3. Može li se napraviti raspored šetnji za tjedan dana tako da svaka učenica u tih 7 dana bude točno jedanput u grupi sa svakom od preostalih učenica? U rješavanju ovog i niza drugih zanimljivih i praktičnih problema, u kojima postoje određeni prirodni zahtjevi o pravilnom rasporedu u konačnim skupovima, iskristalizirao se pojam blokovnih dizajna. Generalizaciju Kirkmanova problema riješili su neovisno Lu, Ray-Chaduri i Wilson [6], tek oko 110 godina kasnije.

Temeljni pojam teorije dizajna je konačna incidencijska struktura.  Definiramo je kao trojku \mathcal{S}=(\mathcal{P} ,\mathcal{B},\mathcal{I}), koja se sastoji od dva disjunktna konačna skupa \mathcal{P} i \mathcal{B}, te skupa \mathcal{I}\subseteq \mathcal{P}\times\mathcal{B}. Elementi skupa \mathcal{P} nazivaju se točkama i obično ih označavamo malim latiničnim slovima. Elementi skupa \mathcal{B} nazivaju se blokovima i označavat ćemo ih velikim latiničnim slovima. Ako se uređeni par (p,B) nalazi u skupu \mathcal{I}, kažemo da je točka p incidentna s blokom B ili da blok B sadržava točku p ili da se točka p nalazi na bloku B. Od posebnog interesa su incidencijske strukture s određenim stupnjem pravilnosti, koje se tradicionalno nazivaju blokovnim dizajnima ili jednostavno dizajnima.



Brojeve t, v, k i \lambda nazivamo parametrima dizajna. Moguće je da različiti blokovi dizajna budu incidentni s istim skupom točaka, pa imamo takozvane ponovljene blokove. t-dizajn koji nema ponovljenih blokova nazivamo jednostavnimt-dizajnom} (engl. simple t-design). Za jednostavne t-dizajne ponekad je uputno poistovjetiti blok sa skupom točaka s kojima je incidentan. U tom slučaju možemo pisati p\in B ili B\ni p umjesto (p,B)\in\mathcal{I} i skraćujemo oznaku \mathcal{D}=(\mathcal{P},\mathcal{B}). Dizajni koje ovdje razmatramo su jednostavni, pa ćemo to razumijevati u daljnjem tekstu i izostavljati taj atribut. Također ćemo, iako u definiciji nije navedeno, razumijevati da je 0\leq t\leq k.

Uobičajeno je broj blokova dizajna označiti s b. Dizajn nazivamo trivijalnim ako je svakih k točaka incidentno s nekim blokom, odnosno ako je b={\binom{v}{k}}. Netrivijalni 2-dizajn poznat je pod nazivom uravnoteženi nepotpuni blok dizajn (engl. balanced incomplete block design) ili kraće BIBD. Za 2-dizajn se često koristi i oznaka koja uključuje više parametara. Tada govorimo o 2-(b,v,r,k,\lambda) dizajnu. Parametar r označava broj blokova incidentnih jednoj točki dizajna. Parametri koje smo naveli nisu posve neovisni, a to ćemo naknadno i objasniti. Broj n=r-\lambda nazivamo redom 2-dizajna. Ako je t=\lambda=1, dizajn je particija skupa točaka u podskupove kardinalnosti k. Stoga su u ovom slučaju parametri ograničeni uvjetom da k mora dijeliti v. Od posebnog su interesa simetrični dizajni, u literaturi poznati pod kraticom SBIBD. Simetrični dizajn je 2-(v,k,\lambda) dizajn kod kojeg je b=v (iz čega, kako ćemo naknadno vidjeti, slijedi da je r=k). Svaki njegov blok sadržava k točaka, a svaka točka sadržana je u točno k blokova.

Za t-(v,k,\lambda) dizajn ponekad se koristi oznaka, odnosno naziv, S_{\lambda}(t,k,v) dizajn. Ako je t\geq2 i \lambda=1, onda se t-dizajn naziva Steinerovim sustavom ili Steinerovim t-dizajnom, i umjesto S_{1}(t,k,v) pišemo S(t,k,v). Kada se radi o S(2,k,v) dizajnu, često se za blok koristi naziv pravac zbog geometrij\-ske analogije, jer bilo koje 2 točke određuju jedinstven blok.



\begin{Dokaz} Neka je S skup od s točaka, gdje je 0\leq s\lt t, i m broj blokova koji sadržavaju svaku točku iz S. Neka je \mathcal{T}=\lbrace (T,B)|S\subset T\subseteq B,|T|=t,B\in\mathcal{B}\rbrace. Prebrojimo \mathcal{T} na dva načina. Označimo s N broj parova (T,B). Skup T može se odabrati na {\binom{{v-s}}{{t-s}}} načina, a svaki T je podskup od točno \lambda blokova B\in\mathcal{B}. Stoga je N=\lambda {\binom{{v-s}}{{t-s}}}. S druge strane, neka je m broj blokova koji sadržavaju S. Svaki blok B koji sadržava S sadržava {\binom{{k-s} }{{t-s}}}t-članih skupova T za koje je S\subset T, pa je N=m{\binom{{k-s}}{{t-s}}}. Stoga dobivamo što pokazuje da je m neovisan o S i dan je formulom (1 ). \end{Dokaz}

Primijetimo da je \lambda_{0}=b,\lambda_{1}=r. Ako za \lambda uvedemo oznaku \lambda_{t}, pokaže se da brojeve \lambda_{s} jednostavno dobijemo koristeći se rekurzijom Odavde za s=0 dobivamo a za t=2 i s=1  iz čega zbog (4) slijedi
Dakle, parametri v, k, \lambda, b i r nisu neovisni. Specijalno, za simetrični dizajn vrijedi k=r i v=\frac{k(k-1)}{\lambda}+1.
Najmanji netrivijalni blokovni dizajn za t=2 imamo kada je \lambda=1 i k=3. To je sustav trojki, takav da je svaki par točaka sadržan u točno jednoj trojci. Zbog (5) i (6) za t=2 općenito vrijedi pa se odmah vidi da za \lambda=1 i k=3 dobivamo v\equiv1\pmod{6} ili v\equiv3\pmod{6}. Stoga v mora biti iz skupa \lbrace 3,7,9,13,15,19,21,25,27,31,\ldots\rbrace. Da za svaki takav v postoji blokovni dizajn tipa 2-(v,3,1) dokazao je J. P. Kirkman još 1847. godine. Ovi dizajni poznati su pod nazivom Steinerovi sustavi trojki. Naziv se može činiti pomalo nepravednim jer je J. Steiner do Kirkmanova rezultata došao nekoliko godina poslije njega.

Već smo spomenuli Fanovu ravninu, koja je Steinerov sustav trojki za v=7. Kirkmanov problem 15 učenica ekvivalentan je problemu egzistencije Steinerovog sustava trojki za v=15, uz dodatni uvjet 'rastavljivosti' (engl. resolvable), tj. blokovi dizajna trebaju biti rasporedivi u klase tako da svaka točka pripada točno jednom bloku iz svake klase. Kod dizajna s ovim svojstvom v mora biti djeljiv s k, što u slučaju 2-(v,3,1) dizajna daje v\equiv3\pmod{6}. Naravno, v=15 zadovoljava taj uvjet.


U proučavanju t-dizajna od interesa su neka finija prebrojavanja blokova dizajna s obzirom na incidentnost s točkama zadanog skupa.


\begin{Dokaz} Jednakosti (7) i (8) dokazat ćemo indukcijom po j. Provjerimo jednakost za j=0. Ako je |I|\leq t,\lambda_{i}^{0} =\lambda_{i}, tada po Teoremu 3 imamo Ako je \lambda=1 i t\lt |I|\leq k, onda je \lambda_{i}^{0}=1. Neka je sada j\geq1 i pretpostavimo da jednakosti vrijede za sve vrijednosti do j-1. Odaberimo točku p\in J i neka je B blok koji sadržava I i disjunktan je s J\mathcal{\setminus}\lbrace p\rbrace. Tada je ili p\in B ili p\notin B i stoga Po pretpostavci indukcije slijedi Time smo dokazali jednakosti (7) i (8).
Da bismo dokazali jednakost (9), dovoljno je uočiti da vrijednost c(i,j) ne ovisi ni o zadanom dizajnu ni o vrijednosti \lambda. Dakle, dovoljno je promotriti trivijalni t-(v,k,\lambda) dizajn čiji su blokovi svi k-podskupovi od \mathcal{P}. Tada je očito čime je jednakost dokazana. \end{Dokaz}
Vrijednosti \lambda_{i}^{j} nazivamo (i,j) presječni brojevi t-(v,k,\lambda) dizajna. Naglasimo da je \lambda_{0}^{0}=b,\lambda _{1}^{0}=r,\ \lambda_{s}^{0}=\lambda_{s}, za 0\leq s\leq t, i\ \lambda _{t}=\lambda. U slučaju kada je \mathcal{D} Steinerov sustav, dakle t\geq2 i \lambda_{t}=\lambda=1, vrijedi \lambda_{i}^{0}=1 za t\leq i\leq k.

Brojevi \lambda_{i}^{j}, 0\leq i,j\leq t i i+j\leq t mogu se posložiti u Pascalov trokut prikazan na Slici 4. Za Steinerov sustav trokut se može proširiti do (k+1)-og retka. Zadnji redak čine presječni brojevi \lambda_{i}^{j},i+j=k, dakle, \lambda _{k}^{0}=1,\lambda_{k-1}^{1},\lambda_{k-2}^{2},\ldots,\lambda_{0}^{k}, i znače broj blokova koji imaju točno i zajedničkih točaka.

Jednostavan način konstrukcije Pascalova trokuta za određeni dizajn započinje od donjeg lijevog vrha trokuta i ide prema gornjem vrhu rekurzijom \lambda_{s}^{0}=\lambda_{s}=\lambda_{s+1}(v-s)/(k-s). Potom se trokut popuni korištenjem rekurzije (11), tj. \lambda_{i} ^{j}=\lambda_{i}^{j-1}-\lambda_{i+1}^{j-1}.

Primjerice, za Fanovu ravninu, koja jest Steinerov sustav, trokut ima k+1=4 retka koje dajemo u sljedećoj shemi.

                                7
                              3   4
                            1   2   2
                          1   0   2   0

Za dvoravninu 2-(16,6,2) imamo trokut

                              16
                            6    10
                          2    4    6,

odnosno za bilo koji simetrični dizajn:
                                        v

                                 k      \ \ \ \ \ \ v-k

                           \lambda          n         v-k-n .
Kao ilustraciju pogledajmo još Pascalov trokut za 5-(24,8,1) dizajn, prikazan na Slici 5. Za sada na slici treba zanemariti isprekidanu crtu čije ćemo značenje objasniti poslije, vezano uz derivirani dizajn. Iz zadnjeg retka vidimo da se u bilo kojem dizajnu s parametrima 5-(24,8,1) dva bloka sijeku u 0, 2 ili 4 točke.

Za dani t-dizajn postoje s njim prirodno povezane strukture, koje u nekim slučajevima vode novom dizajnu. Spomenut ćemo neke od njih vezano uz presječne brojeve.

Neka je \mathcal{S}=(\mathcal{P},\mathcal{B},\mathcal{I}) incidencijska struktura. Tada strukturu \overline{\mathcal{S}}=(\overline{\mathcal{P} },\overline{\mathcal{B}},\overline{\mathcal{I}}), gdje je \overline{\mathcal{P}}=\mathcal{P}, \overline{\mathcal{B}}=\mathcal{B} i \overline{\mathcal{I}}=\mathcal{P}\times\mathcal{B\setminus I} nazivamo komplementom od \mathcal{S}. Ako je polazna struktura t-dizajn \mathcal{D}=(\mathcal{P},\mathcal{B}) i incidencija standardna, onda je njegov komplement \overline{\mathcal{D}}=(\mathcal{P},\overline{\mathcal{B} }) gdje je \overline{\mathcal{B}}=\left\lbrace \mathcal{P\setminus}B\mid B\in\mathcal{B}\right\rbrace.


\begin{Dokaz} Očito za presječne brojeve \overline{\lambda_{i}^{j}}\ dizajna\ \overline{\mathcal{D}}\ i presječne brojeve\ dizajna \mathcal{D} vrijedi \overline{\lambda_{i}^{j}}=\lambda_{j}^{i}. Broj blokova dizajna \overline{\mathcal{D}} koji sadržavaju t-podskup točaka je \end{Dokaz}
Za 2-dizajne imamo \overline{\lambda}=b-2r+\lambda. Komplement Fanove ravnine je simetrični 2-(7,4,2) dizajn, dvoravnina reda 2. Općenito, komplement simetričnog dizajna je simetrični dizajn.

Neka je \mathcal{D}=(\mathcal{P},\mathcal{B})\ t-(v,k,\lambda) dizajn i p\in\mathcal{P}. Njegov derivirani dizajn s obzirom na p je struktura \mathcal{D}_{p}=(\mathcal{P}_{p},\mathcal{B}_{p}), gdje je \mathcal{P}_{p}=\mathcal{P\setminus}\left\lbrace p\right\rbrace i \
\mathcal{B}_{p}=\left\lbrace B\mathcal{\setminus}\left\lbrace p\right\rbrace \mid B\in\mathcal{B},\text{ }B\ni p\right\rbrace .

Lako se vidi da je \mathcal{D}_{p} dizajn s parametrima  (t-1)-(v-1,k-1,\lambda). Označimo s \mu_{i}^{j}  presječne brojeve dizajna \mathcal{D}_{p};i+j\leq t-1, odnosno i+j\leq k-1 za Steinerove sustave. Iz Teorema 4 slijedi \mu_{i}^{j} =\lambda_{i+1}^{j}.

Ova veza presječnih brojeva dizajna \mathcal{D} i\ \mathcal{D}_{p} ima za korisnu praktičnu posljedicu lako dobivanje Pascalovog trokuta dizajna \mathcal{D}_{p} iz onoga za dizajn \mathcal{D}. Potrebno je iz trokuta za dizajn \mathcal{D} jednostavno izostaviti brojeve \lambda_{0}^{j}, tj. brisati njegovu "desnu stranicu".

Vratimo se 5-(24,8,1) dizajnu \mathcal{D}. Derivirani dizajn \mathcal{D}_{p} ima parametre 4-(23,7,1). Na Slici 5 naznačeno je isprekidanom crtom kako se iz Pascalova trokuta dizajna \mathcal{D} dobije Pascalov trokut dizajna \mathcal{D}_{p}. Vidi se, među ostalim, da je broj blokova 4-(23,7,1) dizajna \mu_{0} ^{0}=|\mathcal{B}_{p}|=253. Uočimo li da je 253={\binom{{23}}{2},} možemo zaključiti da 4-(23,7,1) dizajn pripada skupini takozvanih gustih (eng. tight) dizajna. Naime, 2l-dizajn (\mathcal{P},\mathcal{B}) naziva se 2l-gustim ako ima svojstvo |\mathcal{B}|={\binom{{v}}{l}.}

Koncept presječnih brojeva u teoriji dizajna ima relativno dugu povijest, počevši od ranih radova iz 70-ih godina dvadesetog stoljeća [4], [5]. Pored onih o kojima je ovdje bilo govora, postoje i drugi tipovi presječnih brojeva, odnosno različite modifikacije i generalizacije definicije koju smo naveli.

Ovaj koncept pokazao se korisnim u istraživanju t-dizajna, posebice Steinerovih sustava, ali i srodnih struktura kao što su kodovi i grafovi. Informacije o tome mogu se pronaći u standardnoj literaturi iz ovih područja, primjerice [1] i [2].
Napomena. Članak je nastao pri izradi diplomskog rada D. Šarac na studiju Matematike i informatike PMF-a u Splitu.

Bibliografija