Budući da je dosad na forumu bilo dosta interesovanja za zadatke u kojima se tražio broj binarnih relacija (refleksivnih, simetričnih, ovih, onih) nad nekim skupom, mislio sam da bi bilo dobro imati sve na jednom mestu. Sve relacije o kojima u ovom tutorijalu bude bilo reči biće posmatrane nad skupom od [inlmath]n[/inlmath] elemenata, pa će, samim tim, i broj odgovarajućih binarnih relacija biti izražen preko [inlmath]n[/inlmath]. Pored broja proizvoljnih relacija nad nekim skupom (što će biti razmatrano na samom početku), biće razmatrani i brojevi relacija koje su refleksivne, simetrične, antisimetrične, zatim koje nisu refleksivne, nisu simetrične, nisu antisimetrične, kao i kombinacije prethodno nabrojanih osobina relacija (npr. broj relacija koje su refleksivne a nisu simetrične itd.).
Najpre, nekoliko osnovnih podsećanja u vezi s binarnim relacijama (podrazumeva se da je čitalac ovog tutorijala odranije s time upoznat):
- Binarna relacija [inlmath]\rho[/inlmath] na skupu [inlmath]S[/inlmath] predstavlja podskup Dekartovog proizvoda [inlmath]S\times S[/inlmath]. Ako je element [inlmath]a[/inlmath] u relaciji s elementom [inlmath]b[/inlmath], to zapisujemo kao [inlmath]a\rho b[/inlmath].
- Tabelarni prikaz binarne relacije – svaku binarnu relaciju nad skupom od [inlmath]n[/inlmath] elemenata možemo predstaviti tabelom [inlmath]n\times n[/inlmath], u kojoj, ako važi [inlmath]a\rho b[/inlmath], tada je polje u [inlmath]a[/inlmath]-toj vrsti i [inlmath]b[/inlmath]-toj koloni popunjeno, a ako ne važi [inlmath]a\rho b[/inlmath], tada je polje u [inlmath]a[/inlmath]-toj vrsti i [inlmath]b[/inlmath]-toj koloni nepopunjeno (prazno).
- Prikaz pomoću grafa – svakom elementu skupa [inlmath]S[/inlmath] odgovara po jedan čvor grafa. Grane tog grafa predstavljaju relacije između elemenata, tako da je strelica na grani usmerena od čvora [inlmath]a[/inlmath] do čvora [inlmath]b[/inlmath] ukoliko važi [inlmath]a\rho b[/inlmath].
- Refleksivna relacija je ona binarna relacija kod koje važi [inlmath](\forall x\in S)x\rho x[/inlmath], tj. svaki element je u relaciji sa samim sobom (u tabelarnom prikazu relacije sva polja na glavnoj dijagonali su popunjena, a u odgovarajućem grafu na svakom od čvorova postoji petlja).
- Simetrična relacija je ona binarna relacija kod koje važi [inlmath](\forall x,y\in S)(x\rho y\;\Longrightarrow\;y\rho x)[/inlmath], tj. ako je jedan element u relaciji s nekim drugim elementom, tada je i taj drugi element u relaciji s prvim (u tabelarnom prikazu polja tabele su simetrično (ne)popunjena u odnosu na glavnu dijagonalu, a graf koji predstavlja ovakvu relaciju je neorijentisan).
- Antisimetrična relacija je ona binarna relacija kod koje važi [inlmath](\forall x,y\in S)(x\rho y\;\land\;y\rho x\;\Longrightarrow\;x=y)[/inlmath], tj. nikoja dva različita elementa ne mogu biti u obostranoj relaciji (u tabelarnom prikazu ne postoji par polja simetričnih u odnosu na glavnu dijagonalu takvih da su oba popunjena, a u odgovarajućem grafu nikoja dva različita čvora ne mogu biti povezana dvosmernom vezom).
- Tranzitivna relacija je ona binarna relacija kod koje važi [inlmath](\forall x,y,z\in S)(x\rho y\;\land\;y\rho z\;\Longrightarrow\;x\rho z)[/inlmath], tj. ako je jedan element u relaciji s drugim, a drugi u relaciji s trećim, tada je i prvi element u relaciji s trećim.
- Relacija koja ispunjava osobine refleksivnosti, simetričnosti i tranzitivnosti predstavlja relaciju ekvivalencije.
- Relacija koja ispunjava osobine refleksivnosti, antisimetričnosti i tranzitivnosti predstavlja relaciju poretka.
BROJ PROIZVOLJNIH RELACIJA
Tabelarni način:
Broj proizvoljnih relacija nad skupom od [inlmath]n[/inlmath] elemenata jednak je broju načina na koji možemo popuniti tabelu:
[dispmath]\begin{array}{c|c|c|c|c|c|c|}& 1 & 2 & 3 & \cdots & n-1 & n\\ \hline
1 & ? & ? & ? & \cdots & ? & ?\\ \hline
2 & ? & ? & ? & \cdots & ? & ?\\ \hline
3 & ? & ? & ? & \cdots & ? & ?\\ \hline
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ \hline
n-1 & ? & ? & ? & \cdots & ? & ?\\ \hline
n & ? & ? & ? & \cdots & ? & ?\\ \hline
\end{array}[/dispmath]
Ukupan broj polja tabele je [inlmath]n^2[/inlmath], a svako polje može biti popunjeno ili nepopunjeno (tj. moguća su po dva slučaja za svako polje), što označavamo znakom pitanja ([inlmath]?[/inlmath]). Zbog toga broj načina na koje tabelu možemo popuniti određujemo kao broj varijacija s ponavljanjem od [inlmath]2[/inlmath] elementa klase [inlmath]n^2[/inlmath], tj. [inlmath]\overline V_2^{n^2}=2^{n^2}[/inlmath], što predstavlja i traženi broj proizvoljnih relacija.
Način preko grafova:
Svaki od [inlmath]n[/inlmath] čvorova može, a i ne mora biti u relaciji sa samim sobom. To je na grafu prikazano žutim petljama na svakom od čvorova, koje se mogu, ali i ne moraju tu nalaziti. Pošto za svaki od [inlmath]n[/inlmath] čvorova imamo [inlmath]2[/inlmath] moguća slučaja, broj mogućih načina na koji možemo postaviti petlje na čvorove računamo kao broj varijacija s ponavljanjem od [inlmath]2[/inlmath] elementa [inlmath]n[/inlmath]-te klase, tj. [inlmath]\overline V_2^n=2^n[/inlmath].
Zatim posmatramo relacije između svaka dva različita čvora. Između svaka dva različita čvora moguća su četiri slučaja: 1) ni prvi čvor nije u relaciji s drugim, ni drugi u relaciji s prvim; 2) prvi čvor je u relaciji s drugim, ali drugi nije u relaciji s prvim; 3) prvi čvor nije u relaciji s drugim, ali drugi jeste u relaciji s prvim; 4) i prvi čvor je u relaciji s drugim, i drugi u relaciji s prvim. Pošto bilo koja [inlmath]2[/inlmath] od ukupno [inlmath]n[/inlmath] čvorova možemo odabrati na [inlmath]n\choose2[/inlmath] načina (broj kombinacija bez ponavljanja od [inlmath]n[/inlmath] elemenata [inlmath]2.[/inlmath] klase), a između svaka dva čvora moguća su četiri slučaja (ne)povezivanja, ukupan broj raspoređivanja ovih relacija bio bi jednak broju varijacija s ponavljanjem od [inlmath]4[/inlmath] elementa klase [inlmath]n\choose2[/inlmath]: [inlmath]\overline V_4^{n\choose2}=4^{n\choose2}[/inlmath].
Broj proizvoljnih relacija dobijamo tako što pomnožimo prethodna dva rezultata (jer svakom od [inlmath]2^n[/inlmath] načina na koji smo rasporedili petlje odgovara po [inlmath]4^{n\choose2}[/inlmath] načina za raspoređivanje relacija između dva različita čvora). Prema tome, broj proizvoljnih relacija iznosi [inlmath]2^n4^{n\choose2}[/inlmath].
Logično je da ovaj rezultat mora da se poklapa s rezultatom koji smo dobili tabelarno. I, zaista, ako prethodni rezultat malo sredimo, dobićemo
[dispmath]2^n4^{n\choose2}=2^n\left(2^2\right)^\frac{n(n-1)}{2}=2^n2^{\cancel2\frac{n(n-1)}{\cancel2}}=2^n2^{n^2-n}=2^{\cancel n+n^2-\cancel n}=2^{n^2}[/dispmath] Zatim posmatramo relacije između svaka dva različita čvora. Između svaka dva različita čvora moguća su četiri slučaja: 1) ni prvi čvor nije u relaciji s drugim, ni drugi u relaciji s prvim; 2) prvi čvor je u relaciji s drugim, ali drugi nije u relaciji s prvim; 3) prvi čvor nije u relaciji s drugim, ali drugi jeste u relaciji s prvim; 4) i prvi čvor je u relaciji s drugim, i drugi u relaciji s prvim. Pošto bilo koja [inlmath]2[/inlmath] od ukupno [inlmath]n[/inlmath] čvorova možemo odabrati na [inlmath]n\choose2[/inlmath] načina (broj kombinacija bez ponavljanja od [inlmath]n[/inlmath] elemenata [inlmath]2.[/inlmath] klase), a između svaka dva čvora moguća su četiri slučaja (ne)povezivanja, ukupan broj raspoređivanja ovih relacija bio bi jednak broju varijacija s ponavljanjem od [inlmath]4[/inlmath] elementa klase [inlmath]n\choose2[/inlmath]: [inlmath]\overline V_4^{n\choose2}=4^{n\choose2}[/inlmath].
Broj proizvoljnih relacija dobijamo tako što pomnožimo prethodna dva rezultata (jer svakom od [inlmath]2^n[/inlmath] načina na koji smo rasporedili petlje odgovara po [inlmath]4^{n\choose2}[/inlmath] načina za raspoređivanje relacija između dva različita čvora). Prema tome, broj proizvoljnih relacija iznosi [inlmath]2^n4^{n\choose2}[/inlmath].
Logično je da ovaj rezultat mora da se poklapa s rezultatom koji smo dobili tabelarno. I, zaista, ako prethodni rezultat malo sredimo, dobićemo
što je jednako rezultatu dobijenom tabelarno.
BROJ REFLEKSIVNIH RELACIJA
Tabelarni način:
[dispmath]\begin{array}{c|c|c|c|c|c|c|}
& 1 & 2 & 3 & \cdots & n-1 & n\\ \hline
1 & \color{blue}\Large\bullet & ? & ? & \cdots & ? & ?\\ \hline
2 & ? & \color{blue}\Large\bullet & ? & \cdots & ? & ?\\ \hline
3 & ? & ? & \color{blue}\Large\bullet & \cdots & ? & ?\\ \hline
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ \hline
n-1 & ? & ? & ? & \cdots & \color{blue}\Large\bullet & ?\\ \hline
n & ? & ? & ? & \cdots & ? & \color{blue}\Large\bullet\\ \hline
\end{array}[/dispmath]
Pošto je, po definiciji refleksivne relacije, svaki element u relaciji sa samim sobom, u tabelarnom prikazu relacije sva polja na glavnoj dijagonali moraju biti popunjena (što je u gornjoj tabeli obeleženo plavim kružićima). Takvih polja ima ukupno [inlmath]n[/inlmath]. Pošto je ukupan broj polja tabele jednak [inlmath]n^2[/inlmath], to znači da će broj onih polja koja nisu na glavnoj dijagonali (i koja mogu i da budu i da ne budu popunjena) iznositi [inlmath]n^2-n[/inlmath] (ovo smo mogli dobiti i kao broj varijacija bez ponavljanja od [inlmath]n[/inlmath] elemenata [inlmath]2.[/inlmath] klase – jer od [inlmath]n[/inlmath] elemenata biramo [inlmath]2[/inlmath] pri čemu redosled jeste bitan; takođe, mogli smo do toga doći i uočavanjem da u svakoj od [inlmath]n[/inlmath] vrsta imamo po [inlmath]n-1[/inlmath] takvih polja). Broj ovakvih mogućih tabela tada iznosi [inlmath]2^{n^2-n}[/inlmath] – što je jednako broju varijacija s ponavljanjem od [inlmath]2[/inlmath] elementa (popunjeno ili nepopunjeno) klase [inlmath]n^2-n[/inlmath] (broj polja u tabeli koja mogu uzeti neku od ove dve vrednosti). To je, ujedno, i traženi broj refleksivnih relacija.
Način preko grafova:
Na sledećem grafu petlje oko čvorova označene su plavom bojom, što znači da se one tu moraju nalaziti, kako bi relacija bila refleksivna:
Preostalo je još naći broj načina na koje se mogu rasporediti strelice između dva različita čvora (na grafu označene žutom bojom), a što je detaljno objašnjeno u prethodnom odeljku o broju proizvoljnih relacija, te ovde taj postupak nećemo ponavljati. Kao rezultat je dobijeno [inlmath]4^{n\choose2}[/inlmath], ili, nakon sređivanja, [inlmath]2^{n^2-n}[/inlmath], što se poklapa s rezultatom dobijenim tabelarno.
Preostalo je još naći broj načina na koje se mogu rasporediti strelice između dva različita čvora (na grafu označene žutom bojom), a što je detaljno objašnjeno u prethodnom odeljku o broju proizvoljnih relacija, te ovde taj postupak nećemo ponavljati. Kao rezultat je dobijeno [inlmath]4^{n\choose2}[/inlmath], ili, nakon sređivanja, [inlmath]2^{n^2-n}[/inlmath], što se poklapa s rezultatom dobijenim tabelarno.
BROJ SIMETRIČNIH RELACIJA
Tabelarni način:
Zbog simetričnosti relacije, [inlmath](\forall x,y\in S)(x\rho y\;\Longrightarrow\;y\rho x)[/inlmath], tj. zbog osobine da iz [inlmath]a\rho b[/inlmath] sledi [inlmath]b\rho a[/inlmath], polja tabele su simetrično popunjena u odnosu na glavnu dijagonalu. Drugim rečima, onako kako su popunjena polja u jednoj polovini izvan glavne dijagonale, tako isto moraju biti popunjena i odgovarajuća polja u drugoj polovini izvan glavne dijagonale. Zbog toga, pri određivanju broja simetričnih relacija, polja u jednoj polovini izvan glavne dijagonale ne uzimamo u razmatranje. U sledećoj tabeli posmatramo proizvoljno popunjavanje polja na glavnoj dijagonali (jer relacija ne mora biti refleksivna) i ispod glavne dijagonale, dok će, zbog simetričnosti, polja iznad glavne dijagonale (obeležena zeleno) biti popunjena na isti način kao i polja ispod glavne dijagonale (npr. ukoliko je polje [inlmath](3,1)[/inlmath] popunjeno, mora biti popunjeno i polje [inlmath](1,3)[/inlmath]; ili, ako je polje [inlmath](5,2)[/inlmath] nepopunjeno, tada mora biti nepopunjeno i polje [inlmath](2,5)[/inlmath]).
[dispmath]\begin{array}{c|c|c|c|c|c|c|}& 1 & 2 & 3 & \cdots & n-1 & n\\ \hline
1 & ? & \color{green}\Large\bullet & \color{green}\Large\bullet & \cdots & \color{green}\Large\bullet & \color{green}\Large\bullet\\ \hline
2 & ? & ? & \color{green}\Large\bullet & \cdots & \color{green}\Large\bullet & \color{green}\Large\bullet\\ \hline
3 & ? & ? & ? & \cdots & \color{green}\Large\bullet & \color{green}\Large\bullet\\ \hline
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ \hline
n-1 & ? & ? & ? & \cdots & ? & \color{green}\Large\bullet\\ \hline
n & ? & ? & ? & \cdots & ? & ?\\ \hline
\end{array}[/dispmath]
Ukupan broj polja tabele je [inlmath]n^2[/inlmath], broj polja na glavnoj dijagonali je [inlmath]n[/inlmath]. Dakle, broj polja van glavne dijagonale je [inlmath]n^2-n[/inlmath], dok je broj polja u svakoj od polovina van glavne dijagonale jednak [inlmath]\frac{n^2-n}{2}[/inlmath] (ovaj broj smo mogli dobiti i kao broj kombinacija bez ponavljanja od [inlmath]n[/inlmath] elemenata [inlmath]2.[/inlmath] klase, jer od [inlmath]n[/inlmath] elemenata biramo [inlmath]2[/inlmath] pri čemu redosled nije bitan; takođe, broj smo mogli dobiti tako što bismo, idući po vrstama odozgo nadole sabirali polja u svakoj vrsti: [inlmath]0+1+2+\cdots+(n-2)+(n-1)[/inlmath], pa zatim upotrebimo formulu za sumu aritmetičkog niza). Broj polja koja proizvoljno popunjavamo jednak je, dakle, zbiru [inlmath]n[/inlmath] (broj polja na glavnoj dijagonali) i [inlmath]\frac{n^2-n}{2}[/inlmath], tj. jednak je [inlmath]\frac{n^2+n}{2}[/inlmath] (i ovaj broj smo, uostalom, mogli direktno dobiti kao sumu aritmetičkog niza, prebrojavajući polja po vrstama odozgo nadole, [inlmath]1+2+\cdots+(n-1)+n[/inlmath], a mogli smo ga dobiti i kao broj kombinacija s ponavljanjem od [inlmath]n[/inlmath] elemenata [inlmath]2.[/inlmath] klase, jer se sad elementi mogu i ponavljati zbog glavne dijagonale). Znači, broj načina na koje takvu tabelu možemo popuniti, tj. broj simetričnih relacija, jednak je broju varijacija s ponavljanjem od [inlmath]2[/inlmath] elementa klase [inlmath]\frac{n^2+n}{2}[/inlmath], tj. [inlmath]\overline V_2^\frac{n^2+n}{2}=2^\frac{n^2+n}{2}[/inlmath].
Način preko grafova:
Za razliku od slučaja kada smo tražili broj proizvoljnih relacija, i kada su za svaki par čvorova postojala četiri različita slučaja (čvorovi nisu u relaciji, prvi je u relaciji s drugim, drugi je u relaciji s prvim i oba su u međusobnoj relaciji) – sada, zbog simetričnosti, imamo samo dva moguća slučaja: ili su dva čvora u međusobnoj relaciji, ili nisu u međusobnoj relaciji. Na grafu to predstavljamo po jednom granom između dva čvora, koja ne sadrži strelice (graf je neorijentisan), i koja se tu može ali i ne mora nalaziti (što obeležavamo žutom bojom):
Pošto za svaki od [inlmath]n\choose2[/inlmath] neuređenih parova čvorova imamo, dakle, dve mogućnosti, broj načina na koji možemo rasporediti relacije između dva različita čvora sada dobijamo kao broj varijacija s ponavljanjem od [inlmath]2[/inlmath] elementa klase [inlmath]n\choose2[/inlmath], tj. [inlmath]\overline V_2^{n\choose2}=2^{n\choose2}[/inlmath]. Nakon što to pomnožimo brojem načina na koji možemo postaviti petlje oko čvorova, a koji iznosi [inlmath]2^n[/inlmath] (objašnjeno je zašto u poglavlju o računanju broja proizvoljnih relacija), dobijamo broj mogućih simetričnih relacija:
[dispmath]2^n2^{n\choose2}=2^n2^\frac{n(n-1)}{2}=2^{n+\frac{n^2-n}{2}}=2^\frac{n^2+n}{2}[/dispmath] Pošto za svaki od [inlmath]n\choose2[/inlmath] neuređenih parova čvorova imamo, dakle, dve mogućnosti, broj načina na koji možemo rasporediti relacije između dva različita čvora sada dobijamo kao broj varijacija s ponavljanjem od [inlmath]2[/inlmath] elementa klase [inlmath]n\choose2[/inlmath], tj. [inlmath]\overline V_2^{n\choose2}=2^{n\choose2}[/inlmath]. Nakon što to pomnožimo brojem načina na koji možemo postaviti petlje oko čvorova, a koji iznosi [inlmath]2^n[/inlmath] (objašnjeno je zašto u poglavlju o računanju broja proizvoljnih relacija), dobijamo broj mogućih simetričnih relacija:
što je isti rezultat kao onaj dobijen tabelarnim načinom.
BROJ RELACIJA KOJE SU I REFLEKSIVNE I SIMETRIČNE
Tabelarni način:
Pošto je relacija refleksivna, polja na glavnoj dijagonali moraju biti popunjena, što je u tabeli označeno plavom bojom:
[dispmath]\begin{array}{c|c|c|c|c|c|c|}
& 1 & 2 & 3 & \cdots & n-1 & n\\ \hline
1 & \color{blue}\Large\bullet & \color{green}\Large\bullet & \color{green}\Large\bullet & \cdots & \color{green}\Large\bullet & \color{green}\Large\bullet\\ \hline
2 & ? & \color{blue}\Large\bullet & \color{green}\Large\bullet & \cdots & \color{green}\Large\bullet & \color{green}\Large\bullet\\ \hline
3 & ? & ? & \color{blue}\Large\bullet & \cdots & \color{green}\Large\bullet & \color{green}\Large\bullet\\ \hline
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ \hline
n-1 & ? & ? & ? & \cdots & \color{blue}\Large\bullet & \color{green}\Large\bullet\\ \hline
n & ? & ? & ? & \cdots & ? & \color{blue}\Large\bullet\\ \hline
\end{array}[/dispmath]
Takođe, u zavisnosti od toga kako su (ili kako nisu) popunjena polja ispod glavne dijagonale, na isti način, zbog simetričnosti relacije, moraju biti popunjena i polja iznad glavne dijagonale (što je u tabeli označeno zelenom bojom). To jest, razmatramo samo načine na koje možemo popuniti deo ispod glavne dijagonale, a ne i iznad glavne dijagonale, jer polja iznad glavne dijagonale automatski „prate“ svoje parnjake ispod glavne dijagonale.
Broj polja ispod glavne dijagonale je [inlmath]\frac{n^2-n}{2}[/inlmath], kao što je pokazano u prethodnom poglavlju. Za razliku od prethodnog poglavlja, kada je trebalo popunjavati i polja na glavnoj dijagonali, ovaj put zbog refleksivnosti popunjavamo samo polja ispod glavne dijagonale. Prema tome, broj načina na koji to možemo učiniti jednak je broju varijacija s ponavljanjem od [inlmath]2[/inlmath] elementa klase [inlmath]\frac{n^2-n}{2}[/inlmath], tj. [inlmath]\overline V_2^\frac{n^2-n}{2}=2^\frac{n^2-n}{2}[/inlmath].
Broj polja ispod glavne dijagonale je [inlmath]\frac{n^2-n}{2}[/inlmath], kao što je pokazano u prethodnom poglavlju. Za razliku od prethodnog poglavlja, kada je trebalo popunjavati i polja na glavnoj dijagonali, ovaj put zbog refleksivnosti popunjavamo samo polja ispod glavne dijagonale. Prema tome, broj načina na koji to možemo učiniti jednak je broju varijacija s ponavljanjem od [inlmath]2[/inlmath] elementa klase [inlmath]\frac{n^2-n}{2}[/inlmath], tj. [inlmath]\overline V_2^\frac{n^2-n}{2}=2^\frac{n^2-n}{2}[/inlmath].
Način preko grafova:
Pošto je relacija refleksivna, svi čvorovi imaju petlje, tako da njih ne razmatramo (označene su zato plavom bojom):
Zbog simetričnosti relacije graf je neorijentisan (objašnjeno u prethodnom poglavlju), tako da za svaka dva čvora grafa imamo dve mogućnosti – ili će se između njih nalaziti grana, ili se neće nalaziti grana (potencijalne grane označene su žutom bojom). Pošto čvorova ima [inlmath]n[/inlmath] a neuređenih parova čvorova ima [inlmath]n\choose2[/inlmath], pri čemu čvorovi unutar svakog neuređenog para mogu ili biti povezani ili ne biti povezani granom, broj tih mogućnosti je [inlmath]\overline V_2^{n\choose2}[/inlmath], tj. [inlmath]2^\frac{n^2-n}{2}[/inlmath], što odgovara tabelarno dobijenom rezultatu.
Zbog simetričnosti relacije graf je neorijentisan (objašnjeno u prethodnom poglavlju), tako da za svaka dva čvora grafa imamo dve mogućnosti – ili će se između njih nalaziti grana, ili se neće nalaziti grana (potencijalne grane označene su žutom bojom). Pošto čvorova ima [inlmath]n[/inlmath] a neuređenih parova čvorova ima [inlmath]n\choose2[/inlmath], pri čemu čvorovi unutar svakog neuređenog para mogu ili biti povezani ili ne biti povezani granom, broj tih mogućnosti je [inlmath]\overline V_2^{n\choose2}[/inlmath], tj. [inlmath]2^\frac{n^2-n}{2}[/inlmath], što odgovara tabelarno dobijenom rezultatu.
BROJ RELACIJA KOJE NISU REFLEKSIVNE
Broj ovih relacija može se dobiti na dva načina:
- Od ranije izračunatog broja proizvoljnih relacija ([inlmath]2^{n^2}[/inlmath]) oduzme se ranije izračunat broj refleksivnih relacija ([inlmath]2^{n^2-n}[/inlmath]):
[dispmath]2^{n^2}-2^{n^2-n}=2^{n^2-n}\left(2^n-1\right)[/dispmath] - Od broja mogućnosti popunjavanja glavne dijagonale tabele ([inlmath]2^n[/inlmath]) oduzme se onaj jedan slučaj koji bi odgovarao refleksivnoj relaciji (tj. kada bi sva polja glavne dijagonale bila popunjena), a zatim se [inlmath]2^n-1[/inlmath] pomnoži brojem mogućnosti popunjavanja preostalih [inlmath]n^2-n[/inlmath] polja tabele:
[dispmath]\left(2^n-1\right)2^{n^2-n}[/dispmath]
BROJ RELACIJA KOJE NISU SIMETRIČNE
Dobija se tako što se od ranije izračunatog broja proizvoljnih relacija ([inlmath]2^{n^2}[/inlmath]) oduzme ranije izračunat broj simetričnih relacija ([inlmath]2^\frac{n^2+n}{2}[/inlmath]):
[dispmath]2^{n^2}-2^\frac{n^2+n}{2}[/dispmath]BROJ REFLEKSIVNIH RELACIJA KOJE NISU SIMETRIČNE
Dobija se tako što se od ranije izračunatog broja refleksivnih relacija ([inlmath]2^{n^2-n}[/inlmath]) oduzme ranije izračunat broj relacija koje su i refleksivne i simetrične ([inlmath]2^\frac{n^2-n}{2}[/inlmath]):
[dispmath]2^{n^2-n}-2^\frac{n^2-n}{2}[/dispmath]BROJ SIMETRIČNIH RELACIJA KOJE NISU REFLEKSIVNE
Broj ovih relacija može se dobiti na dva načina:
- Od ranije izračunatog broja simetričnih relacija ([inlmath]2^\frac{n^2+n}{2}[/inlmath]) oduzme se ranije izračunat broj relacija koje su i refleksivne i simetrične ([inlmath]2^\frac{n^2-n}{2}[/inlmath]):
[dispmath]2^\frac{n^2+n}{2}-2^\frac{n^2-n}{2}=2^\frac{n^2-n}{2}\left(2^n-1\right)[/dispmath] - Od broja mogućnosti popunjavanja glavne dijagonale tabele ([inlmath]2^n[/inlmath]) oduzme se onaj jedan slučaj koji bi odgovarao refleksivnoj relaciji (tj. kada bi sva polja glavne dijagonale bila popunjena), a zatim se [inlmath]2^n-1[/inlmath] pomnoži brojem mogućnosti popunjavanja polja ispod glavne dijagonale tabele:
[dispmath]\left(2^n-1\right)2^\frac{n^2-n}{2}[/dispmath]
BROJ RELACIJA KOJE NISU NI REFLEKSIVNE NI SIMETRIČNE
Broj ovih relacija može se dobiti na dva načina:
- Od ranije izračunatog broja relacija koje nisu refleksivne ([inlmath]\left(2^n-1\right)2^{n^2-n}[/inlmath]) oduzme se ranije izračunat broj simetričnih relacija koje nisu refleksivne ([inlmath]\left(2^n-1\right)2^\frac{n^2-n}{2}[/inlmath]):
[dispmath]\left(2^n-1\right)2^{n^2-n}-\left(2^n-1\right)2^\frac{n^2-n}{2}=\left(2^n-1\right)\left(2^{n^2-n}-2^\frac{n^2-n}{2}\right)[/dispmath] - Od ranije izračunatog broja relacija koje nisu simetrične ([inlmath]2^{n^2}-2^\frac{n^2+n}{2}[/inlmath]) oduzme se ranije izračunat broj refleksivnih relacija koje nisu simetrične ([inlmath]2^{n^2-n}-2^\frac{n^2-n}{2}[/inlmath]):
[dispmath]2^{n^2}-2^\frac{n^2+n}{2}-2^{n^2-n}+2^\frac{n^2-n}{2}=2^{n^2-n}\left(2^n-1\right)-2^\frac{n^2-n}{2}\left(2^n-1\right)=\left(2^{n^2-n}-2^\frac{n^2-n}{2}\right)\left(2^n-1\right)[/dispmath]