Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI TEORIJA SKUPOVA

Broj relacija (refleksivnih, simetričnih, antisimetričnih...) nad skupom od n elemenata

[inlmath]C\backslash\left(A\cap B\right)=\left(C\backslash A\right)\cup\left(C\backslash B\right)[/inlmath]
  • +1

Broj relacija (refleksivnih, simetričnih, antisimetričnih...) nad skupom od n elemenata

Postod Daniel » Ponedeljak, 03. Septembar 2018, 22:15

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:

proizvoljne.png
proizvoljne.png (1.99 KiB) Pogledano 8100 puta

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]
š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:

refleksivne.png
refleksivne.png (2.02 KiB) Pogledano 8100 puta

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):

simetricne.png
simetricne.png (1.46 KiB) Pogledano 8100 puta

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]
š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].

Način preko grafova:
Pošto je relacija refleksivna, svi čvorovi imaju petlje, tako da njih ne razmatramo (označene su zato plavom bojom):

refleksivne, simetricne.png
refleksivne, simetricne.png (1.47 KiB) Pogledano 8100 puta

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]
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Re: Broj relacija (refleksivnih, simetričnih, antisimetričnih...) nad skupom od n elemenata

Postod Daniel » Ponedeljak, 03. Septembar 2018, 22:19

U prethodnom postu ispitivali smo slučajeve kada su relacije (ili kada nisu) refleksivne ili simetrične, pri čemu se nismo bavili osobinom antisimetričnosti. Sada „u igru“ uvodimo i tu osobinu – u ovom delu tutorijala prvo ćemo ispitivati relacije koje su antisimetrične i razmatraćemo razne slučajeve u zavisnosti od toga da li su (ili nisu) istovremeno i refleksivne i simetrične, a nakon toga ćemo se na isti način pozabaviti i relacijama koje nisu antisimetrične.

Formalnu definiciju antisimetričnosti, [inlmath](\forall a,b\in S)(a\rho b\;\land\;b\rho a\;\Longrightarrow\;a=b)[/inlmath], možemo pravilom kontrapozicije [inlmath](p\;\Longrightarrow\;q)\iff(\lnot q\;\Longrightarrow\;\lnot p)[/inlmath] svesti na iskaz [inlmath](\forall a,b\in S)\bigl(a\ne b\;\Longrightarrow\;\lnot(a\rho b\;\land\;b\rho a)\bigr)[/inlmath], koji nam sasvim jasno kaže da kod antisimetrične relacije dva različita elementa ne smeju biti u obostranoj relaciji. Znači, dozvoljena su tri slučaja, 1) da ni prvi nije u relaciji s drugim ni drugi s prvim, 2) da je prvi u relaciji s drugim ali ne i drugi s prvim, 3) da je drugi u relaciji s prvim ali ne i prvi s drugim. Ali, nije dozvoljen slučaj da je prvi u relaciji s drugim i drugi u relaciji s prvim. Ukoliko postoji bar jedan par različitih elemenata koji su u međusobnoj relaciji, ta relacija ne može biti antisimetrična. Ovaj podatak koristićemo pri određivanju broja antisimetričnih relacija. Prvo ćemo odrediti ukupan broj antisimetričnih relacija nezavisno od njihovih ostalih osobina (refleksivnost, simetričnost), a nakon toga ćemo određivati broj antisimetričnih relacija koje ispunjavaju i druge osobine.



BROJ ANTISIMETRIČNIH RELACIJA

Tabelarni način:
Budući da relacija ne mora biti refleksivna, polja na glavnoj dijagonali mogu biti proizvoljno (ne)popunjena (što na glavnoj dijagonali tabele označavamo znakovima pitanja), a to možemo učiniti na [inlmath]2^n[/inlmath] načina (videti prethodna poglavlja). Broj načina na koje možemo popuniti preostala polja određujemo na sledeći način – posmatramo parove polja koja su simetrična u odnosu na glavnu dijagonalu (u tabeli su polja istog para označena znakovima pitanja iste boje, dok su različiti parovi označeni znakovima pitanja različitih boja):
[dispmath]\begin{array}{c|c|c|c|c|c|c|}
& 1 & 2 & 3 & \cdots & n-1 & n\\ \hline
1 & ? & \color{purple}? & \color{orange}? & \cdots & \color{gray}? & \color{green}?\\ \hline
2 & \color{purple}? & ? & \color{cyan}? & \cdots & \color{red}? & \color{yellow}?\\ \hline
3 & \color{orange}? & \color{cyan}? & ? & \cdots & \color{brown}? & \color{magenta}?\\ \hline
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ \hline
n-1 & \color{gray}? & \color{red}? & \color{brown}? & \cdots & ? & \color{pink}?\\ \hline
n & \color{green}? & \color{yellow}? & \color{magenta}? & \cdots & \color{pink}? & ?\\ \hline
\end{array}[/dispmath]
Ni u jednom paru ne smeju oba polja biti popunjena, jer tada relacija ne bi bila antisimetrična. Znači, dozvoljena su tri slučaja po svakom paru – da nijedno od polja iz tog para nije popunjeno, zatim da je polje ispod glavne dijagonale popunjeno a polje iznad nepopunjeno, kao i da je polje ispod glavne dijagonale nepopunjeno a polje iznad popunjeno. Takvih parova ima [inlmath]\frac{n^2-n}{2}[/inlmath] (od ukupnog broja polja tabele oduzmemo broj polja na glavnoj dijagonali i zatim to podelimo sa dva). Prema tome, broj popunjavanja polja van glavne dijagonale određujemo kao broj varijacija s ponavljanjem od [inlmath]3[/inlmath] elementa klase [inlmath]\frac{n^2-n}{2}[/inlmath], tj. [inlmath]\overline V_3^\frac{n^2-n}{2}=3^\frac{n^2-n}{2}[/inlmath].
Nakon što pomnožimo broj načina popunjavanja glavne dijagonale i broj načina popunjavanja polja van glavne dijagonale, dobićemo broj antisimetričnih relacija, koji iznosi [inlmath]2^n3^\frac{n^2-n}{2}[/inlmath].

Način preko grafova:
Pošto relacija ne mora biti refleksivna, svaki od [inlmath]n[/inlmath] čvorova grafa može a i ne mora imati petlju. Petlje na čvorove možemo rasporediti na [inlmath]2^n[/inlmath] načina.
Zbog antisimetričnosti, tj. zbog uslova da dva različita čvora ne smeju biti u međusobnoj (dvosmernoj) relaciji, između svaka dva čvora moguća su tri različita slučaja: 1) da nijedan od dva čvora nije u relaciji s onim drugim, 2) da prvi jeste u relaciji s drugim ali ne i drugi s prvim, 3) da prvi nije u relaciji s drugim ali jeste drugi s prvim. Pošto par čvorova možemo izabrati na [inlmath]n\choose2[/inlmath] načina (kombinacije bez ponavljanja od [inlmath]n[/inlmath] elemenata [inlmath]2.[/inlmath] klase), ukupan broj mogućnosti unutar grafa za postavljanje veza između različitih čvorova iznosi [inlmath]3^{n\choose2}[/inlmath] (varijacije s ponavljanjem od [inlmath]3[/inlmath] elementa klase [inlmath]n\choose2[/inlmath]).
Prema tome, ukupan način raspoređivanja veza u tom grafu (kad se uzmu u obzir i petlje) biće [inlmath]2^n3^{n\choose2}[/inlmath], što je jednako [inlmath]2^n3^\frac{n^2-n}{2}[/inlmath], rezultatu dobijenom tabelarno.



BROJ RELACIJA KOJE SU I REFLEKSIVNE I ANTISIMETRIČNE

Tabelarni način:
Pošto zbog refleksivnosti polja na glavnoj dijagonali moraju biti popunjena (što je u tabeli obeleženo plavim kružićima), posmatraju se samo načini popunjavanja polja van glavne dijagonale.
[dispmath]\begin{array}{c|c|c|c|c|c|c|}
& 1 & 2 & 3 & \cdots & n-1 & n\\ \hline
1 & \color{blue}\Large\bullet & \color{purple}? & \color{orange}? & \cdots & \color{gray}? & \color{green}?\\ \hline
2 & \color{purple}? & \color{blue}\Large\bullet & \color{cyan}? & \cdots & \color{red}? & \color{yellow}?\\ \hline
3 & \color{orange}? & \color{cyan}? & \color{blue}\Large\bullet & \cdots & \color{brown}? & \color{magenta}?\\ \hline
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ \hline
n-1 & \color{gray}? & \color{red}? & \color{brown}? & \cdots & \color{blue}\Large\bullet & \color{pink}?\\ \hline
n & \color{green}? & \color{yellow}? & \color{magenta}? & \cdots & \color{pink}? & \color{blue}\Large\bullet\\ \hline
\end{array}[/dispmath]
U prethodnom poglavlju je pokazano da broj tih načina iznosi [inlmath]3^\frac{n^2-n}{2}[/inlmath], što ujedno predstavlja i broj relacija koje su refleksivne i antisimetrične.

Način preko grafova:
Zbog simetričnosti, svi čvorovi grafa kojim predstavljamo ovakvu relaciju imaće petlje, tako da pri računanju broja načina postavljanja veza unutar grafa ne razmatramo petlje, već samo veze između različitih čvorova, koje se, kako je pokazano u prethodnom poglavlju, mogu postaviti na [inlmath]3^{n\choose2}[/inlmath], tj. na [inlmath]3^\frac{n^2-n}{2}[/inlmath] načina.



BROJ RELACIJA KOJE SU I SIMETRIČNE I ANTISIMETRIČNE

Kako je ranije pokazano, da bi relacija bila simetrična, potrebno je da između bilo koja dva elementa ili ne postoji nikakva relacija, ili da postoji dvosmerna relacija. Međutim, da bi relacija bila antisimetrična, ne sme postojati nijedan par elemenata koji su u dvosmernoj relaciji. To znači da kod relacija koje su istovremeno i simetrične i antisimetrične jedino kao mogućnosti preostaje da nikoja dva različita elementa nisu ni u kakvoj relaciji. Elementi jedino smeju, ali i ne moraju biti u vezi sa samim sobom (jer relacija ne mora biti refleksivna).
Do prethodnog zaključka moguće je doći i na osnovu formalnih definicija simetričnosti i antisimetričnosti. Pošto iz definicije simetričnosti, [inlmath](\forall a,b\in S)(a\rho b\;\Longrightarrow\;b\rho a)[/inlmath] vidimo da iz [inlmath]a\rho b[/inlmath] sledi [inlmath]b\rho a[/inlmath], to u definiciji antisimetričnosti,
[dispmath](\forall a,b\in S)(a\rho b\;\land\;b\rho a\;\Longrightarrow\;a=b)[/dispmath]
možemo [inlmath]a\rho b[/inlmath] zameniti sa [inlmath]b\rho a[/inlmath], čime dobijamo iskaz
[dispmath](\forall a,b\in S)(b\rho a\;\land\;b\rho a\;\Longrightarrow\;a=b)[/dispmath]
a odatle iskaz
[dispmath](\forall a,b\in S)(b\rho a\;\Longrightarrow\;a=b)[/dispmath]
a zatim, koristeći pravilo kontrapozicije [inlmath](p\;\Longrightarrow\;q)\iff(\lnot q\;\Longrightarrow\;\lnot p)[/inlmath], odatle dobijamo iskaz
[dispmath](\forall a,b\in S)\bigl(a\ne b\;\Longrightarrow\;\lnot(b\rho a)\bigr)[/dispmath]
iz kojeg jasno vidimo da nijedan element ne sme biti u relaciji s nekim drugim elementom (izuzev, eventualno, sa samim sobom).
Koristeći ovaj zaključak, odredićemo broj relacija koje su i simetrične i antisimetrične.

Tabelarni način:
Polja na glavnoj dijagonali tabele mogu biti proizvoljno (ne)popunjena (što označavamo znakovima pitanja), jer relacija ne mora biti refleksivna. Ali, pošto polja van glavne dijagonale predstavljaju relacije između različitih elemenata, a zaključili smo da različiti elementi ne smeju biti u relaciji, to ova polja moraju biti prazna:
[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]
Dakle, određivanje broja ovakvih relacija svodi se na određivanje načina na koji se mogu popuniti polja na glavnoj dijagonali, a pošto polja na glavnoj dijagonali ima [inlmath]n[/inlmath] i svako od njih može biti popunjeno ili nepopunjeno, broj ovih načina dobija se kao broj varijacija s ponavljanjem od [inlmath]2[/inlmath] elementa [inlmath]n[/inlmath]-te klase, [inlmath]\overline V_2^n=2^n[/inlmath], što predstavlja i broj relacija koje su simetrične i antisimetrične.

Način preko grafova:
Slično kao i kod tabele – zbog toga što relacija ne mora biti refleksivna, čvorovi mogu ali i ne moraju imati petlje (označeno žutom bojom). Ali ono što znamo, to je da između različitih čvorova ne smeju postojati grane.

simetricne, antisimetricne.png
simetricne, antisimetricne.png (956 Bajta) Pogledano 8099 puta

Prema tome, broj ovakvih mogućih grafova svodi se na broj mogućih raspoređivanja petlji, a njega određujemo kao broj varijacija s ponavljanjem od [inlmath]2[/inlmath] elementa [inlmath]n[/inlmath]-te klase (jer čvorova ima [inlmath]n[/inlmath] a svaki od njih ili ima petlju ili nema petlju), čime se dobije [inlmath]\overline V_2^n=2^n[/inlmath].



BROJ RELACIJA KOJE SU I REFLEKSIVNE I SIMETRIČNE I ANTISIMETRIČNE

Tabelarni način:
Kod ovih relacija, zbog simetričnosti i antisimetričnosti, nijedan element ne sme biti u relaciji ni s jednim drugim elementom (kako je pokazano u prethodnom poglavlju), što predstavljamo praznim poljima van glavne dijagonale. Istovremeno, zbog refleksivnosti, svaki element mora biti u relaciji sa samim sobom, što predstavljamo popunjenim poljima (plavim kružićima) na glavnoj dijagonali.
[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]
Očigledno je da je ovo jedinstven slučaj kada broj relacija sa zadatim osobinama ne zavisi od broja elemenata [inlmath]n[/inlmath], i ovaj broj relacija iznosi [inlmath]1[/inlmath]. Dakle, postoji samo jedna relacija nad skupom od [inlmath]n[/inlmath] elemenata koja istovremeno zadovoljava osobine i refleksivnosti, i simetričnosti, i antisimetričnosti.

Način preko grafova:
Pošto zbog refleksivnosti svaki element mora biti u relaciji sa samim sobom, na grafu svaki čvor mora imati petlju (obeležene plavom bojom). Pošto nijedan element ne sme biti u relaciji ni s jednim drugim elementom, graf ne sme imati grane između različitih čvorova.

refleksivne, simetricne, antisimetricne.png
refleksivne, simetricne, antisimetricne.png (956 Bajta) Pogledano 8099 puta

Očigledno je da postoji samo jedan graf koji se može nacrtati uz ove uslove, što znači da je broj relacija koje su i refleksivne i simetrične i antistimetrične jednak jedinici, tj. postoji samo jedna relacija koja zadovoljava te tri osobine.



BROJ ANTISIMETRIČNIH RELACIJA KOJE NISU REFLEKSIVNE

Broj ovih relacija može se dobiti na dva načina:
  • Od ranije izračunatog broja antisimetričnih relacija ([inlmath]2^n3^\frac{n^2-n}{2}[/inlmath]) oduzme se ranije izračunat broj relacija koje su i refleksivne i antisimetrične ([inlmath]3^\frac{n^2-n}{2}[/inlmath]):
    [dispmath]2^n3^\frac{n^2-n}{2}-3^\frac{n^2-n}{2}=\left(2^n-1\right)3^\frac{n^2-n}{2}[/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]\frac{n^2−n}{2}[/inlmath] parova polja tabele:
    [dispmath]\left(2^n-1\right)3^\frac{n^2-n}{2}[/dispmath]



BROJ ANTISIMETRIČNIH RELACIJA KOJE NISU SIMETRIČNE

Dobija se tako što se od ranije izračunatog broja antisimetričnih relacija ([inlmath]2^n3^\frac{n^2-n}{2}[/inlmath]) oduzme ranije izračunat broj relacija koje su i simetrične i antisimetrične ([inlmath]2^n[/inlmath]):
[dispmath]2^n3^\frac{n^2-n}{2}-2^n=2^n\left(3^\frac{n^2-n}{2}-1\right)[/dispmath]


BROJ RELACIJA KOJE SU I REFLEKSIVNE I ANTISIMETRIČNE A NISU SIMETRIČNE

Dobija se tako što se od ranije izračunatog broja relacija koje su i refleksivne i antisimetrične ([inlmath]3^\frac{n^2-n}{2}[/inlmath]) oduzme ranije izračunat broj relacija koje su i refleksivne i simetrične i antisimetrične ([inlmath]1[/inlmath]):
[dispmath]3^\frac{n^2-n}{2}-1[/dispmath]


BROJ RELACIJA KOJE SU I SIMETRIČNE I ANTISIMETRIČNE A NISU REFLEKSIVNE

Broj ovih relacija može se dobiti na dva načina:
  • Od ranije izračunatog broja relacija koje su i simetrične i antisimetrične ([inlmath]2^n[/inlmath]) oduzme se ranije izračunat broj relacija koje su i refleksivne i simetrične i antisimetrične ([inlmath]1[/inlmath]):
    [dispmath]2^n-1[/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). Kako zbog istovremene simetričnosti i antisimetričnosti postoji samo jedan način popunjavanja polja van glavne dijagonale, a to je da sva polja ostanu nepopunjena, dobijena vrednost [inlmath]2^n-1[/inlmath] ujedno je i broj traženih relacija.



BROJ ANTISIMETRIČNIH RELACIJA KOJE NISU NI REFLEKSIVNE NI SIMETRIČNE

Broj ovih relacija može se dobiti na dva načina:
  • Od ranije izračunatog broja antisimetričnih relacija koje nisu refleksivne ([inlmath]\left(2^n-1\right)3^\frac{n^2-n}{2}[/inlmath]) oduzme se ranije izračunat broj relacija koje su i simetrične i antisimetrične a nisu refleksivne ([inlmath]2^n-1[/inlmath]):
    [dispmath]\left(2^n-1\right)3^\frac{n^2-n}{2}-\left(2^n-1\right)=\left(2^n-1\right)\left(3^\frac{n^2-n}{2}-1\right)[/dispmath]
  • Od ranije izračunatog broja antisimetričnih relacija koje nisu simetrične ([inlmath]2^n\left(3^\frac{n^2-n}{2}-1\right)[/inlmath]) oduzme se ranije izračunat broj relacija koje su i refleksivne i antisimetrične a nisu simetrične ([inlmath]3^\frac{n^2-n}{2}-1[/inlmath]):
    [dispmath]2^n\left(3^\frac{n^2-n}{2}-1\right)-\left(3^\frac{n^2-n}{2}-1\right)=\left(2^n-1\right)\left(3^\frac{n^2-n}{2}-1\right)[/dispmath]





Sledi deo tutorijala u kojem će biti obrađivani slučajevi relacija koje nisu antisimetrične, u zavisnosti od njihove refleksivnosti i simetričnosti.
Pošto je već rečeno da antisimetrične relacije moraju ispunjavati uslov da nikoja dva različita elementa nisu u međusobnoj (dvosmernoj) relaciji, možemo zaključiti da je uslov da relacija ne bude antisimetrična upravo taj, da postoji bar jedan par različitih elemenata koji su u međusobnoj (dvosmernoj) relaciji.



BROJ RELACIJA KOJE NISU ANTISIMETRIČNE

Dobija se tako što se od ranije izračunatog broja proizvoljnih relacija ([inlmath]2^{n^2}[/inlmath]) oduzme ranije izračunat broj antisimetričnih relacija ([inlmath]2^n3^\frac{n^2-n}{2}[/inlmath]):
[dispmath]2^{n^2}-2^n3^\frac{n^2-n}{2}[/dispmath]


BROJ REFLEKSIVNIH RELACIJA KOJE NISU ANTISIMETRIČ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 antisimetrične ([inlmath]3^\frac{n^2-n}{2}[/inlmath]):
[dispmath]2^{n^2-n}-3^\frac{n^2-n}{2}[/dispmath]


BROJ SIMETRIČNIH RELACIJA KOJE NISU ANTISIMETRIČNE

Dobija se tako što se od ranije izračunatog broja simetričnih relacija ([inlmath]2^\frac{n^2+n}{2}[/inlmath]) oduzme ranije izračunat broj relacija koje su i simetične i antisimetrične ([inlmath]2^n[/inlmath]):
[dispmath]2^\frac{n^2+n}{2}-2^n[/dispmath]


BROJ RELACIJA KOJE SU I REFLEKSIVNE I SIMETRIČNE A NISU ANTISIMETRIČNE

Dobija se tako što se od ranije izračunatog broja relacija koje su i refleksivne i simetrične ([inlmath]2^\frac{n^2-n}{2}[/inlmath]) oduzme ranije izračunat broj relacija koje su i refleksivne i simetične i antisimetrične ([inlmath]1[/inlmath]):
[dispmath]2^\frac{n^2-n}{2}-1[/dispmath]
Ovaj rezultat je sasvim logičan. Pošto je zbog refleksivnosti glavna dijagonala tabele popunjena, nju ne posmatramo. Zbog simetričnosti, polja van glavne dijagonale moraju biti popunjena simetrično u odnosu na glavnu dijagonalu (dakle, svaki par takvih polja mora biti ili popunjen ili nepopunjen), ali jedini nedozvoljen slučaj bio bi taj da su sva polja van glavne dijagonale nepopunjena, jer bi tada relacija bila i antisimetrična (a traži se da ne bude antisimetrična). To jest, potrebno je da postoji bar jedan par polja simetričnih u odnosu na glavnu dijagonalu koja su popunjena. Dakle, od ukupno [inlmath]2^\frac{n^2-n}{2}[/inlmath] načina na koje možemo popuniti polja van glavne dijagonale tako da relacija bude simetrična, oduzimamo onaj jedan slučaj kada su sva polja van glavne dijagonale prazna.



BROJ RELACIJA KOJE NISU NI REFLEKSIVNE NI ANTISIMETRIČNE

Broj ovih relacija može se dobiti na dva načina:
  • Od ranije izračunatog broja relacija koje nisu antisimetrične ([inlmath]2^{n^2}-2^n3^\frac{n^2-n}{2}[/inlmath]) oduzme se ranije izračunat broj refleksivnih relacija koje nisu antisimetrične ([inlmath]2^{n^2-n}-3^\frac{n^2-n}{2}[/inlmath]):
    [dispmath]2^{n^2}-2^n3^\frac{n^2-n}{2}-2^{n^2-n}+3^\frac{n^2-n}{2}=2^{n^2-n}\left(2^n-1\right)-\left(2^n-1\right)3^\frac{n^2-n}{2}=\left(2^n-1\right)\left(2^{n^2-n}-3^\frac{n^2-n}{2}\right)[/dispmath]
  • 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 antisimetričnih relacija koje nisu refleksivne ([inlmath]\left(2^n-1\right)3^\frac{n^2-n}{2}[/inlmath]):
    [dispmath]\left(2^n-1\right)2^{n^2-n}-\left(2^n-1\right)3^\frac{n^2-n}{2}=\left(2^n-1\right)\left(2^{n^2-n}-3^\frac{n^2-n}{2}\right)[/dispmath]



BROJ RELACIJA KOJE NISU NI SIMETRIČNE NI ANTISIMETRIČNE

Broj ovih relacija može se dobiti na dva načina:
  • Od ranije izračunatog broja relacija koje nisu antisimetrične ([inlmath]2^{n^2}-2^n3^\frac{n^2-n}{2}[/inlmath]) oduzme se ranije izračunat broj simetričnih relacija koje nisu antisimetrične ([inlmath]2^\frac{n^2+n}{2}-2^n[/inlmath]):
    [dispmath]2^{n^2}-2^n3^\frac{n^2-n}{2}-2^\frac{n^2+n}{2}+2^n[/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 antisimetričnih relacija koje nisu simetrične ([inlmath]2^n\left(3^\frac{n^2-n}{2}-1\right)[/inlmath]):
    [dispmath]2^{n^2}-2^\frac{n^2+n}{2}-2^n\left(3^\frac{n^2-n}{2}-1\right)[/dispmath]



BROJ REFLEKSIVNIH RELACIJA KOJE NISU NI SIMETRIČNE NI ANTISIMETRIČNE

Broj ovih relacija može se dobiti na dva načina:
  • Od ranije izračunatog broja refleksivnih relacija koje nisu simetrične ([inlmath]2^{n^2-n}-2^\frac{n^2-n}{2}[/inlmath]) oduzme se ranije izračunat broj relacija koje su i refleksivne i antisimetrične a nisu simetrične ([inlmath]3^\frac{n^2-n}{2}-1[/inlmath]):
    [dispmath]2^{n^2-n}-2^\frac{n^2-n}{2}-3^\frac{n^2-n}{2}+1[/dispmath]
  • Od ranije izračunatog broja refleksivnih relacija koje nisu antisimetrične ([inlmath]2^{n^2-n}-3^\frac{n^2-n}{2}[/inlmath]) oduzme se ranije izračunat broj relacija koje su i refleksivne i simetrične a nisu antisimetrične ([inlmath]2^\frac{n^2-n}{2}-1[/inlmath]):
    [dispmath]2^{n^2-n}-3^\frac{n^2-n}{2}-2^\frac{n^2-n}{2}+1[/dispmath]



BROJ SIMETRIČNIH RELACIJA KOJE NISU NI REFLEKSIVNE NI ANTISIMETRIČNE

Broj ovih relacija može se dobiti na dva načina:
  • Od ranije izračunatog broja simetričnih relacija koje nisu refleksivne ([inlmath]\left(2^n-1\right)2^\frac{n^2-n}{2}[/inlmath]) oduzme se ranije izračunat broj relacija koje su i simetrične i antisimetrične a nisu refleksivne ([inlmath]2^n-1[/inlmath]):
    [dispmath]\left(2^n-1\right)2^\frac{n^2-n}{2}-\left(2^n-1\right)=\left(2^n-1\right)\left(2^\frac{n^2-n}{2}-1\right)[/dispmath]
  • Od ranije izračunatog broja simetričnih relacija koje nisu antisimetrične ([inlmath]2^\frac{n^2+n}{2}-2^n[/inlmath]) oduzme se ranije izračunat broj relacija koje su i refleksivne i simetrične a nisu antisimetrične ([inlmath]2^\frac{n^2-n}{2}-1[/inlmath]):
    [dispmath]2^\frac{n^2+n}{2}-2^n-2^\frac{n^2-n}{2}+1=2^n\left(2^\frac{n^2-n}{2}-1\right)-\left(2^\frac{n^2-n}{2}-1\right)=\left(2^n-1\right)\left(2^\frac{n^2-n}{2}-1\right)[/dispmath]



BROJ RELACIJA KOJE NISU NI REFLEKSIVNE NI SIMETRIČNE NI ANTISIMETRIČNE

Broj ovih relacija može se dobiti na tri načina:
  • Od ranije izračunatog broja relacija koje nisu ni refleksivne ni simetrične ([inlmath]\left(2^{n^2-n}-2^\frac{n^2-n}{2}\right)\left(2^n-1\right)[/inlmath]) oduzme se ranije izračunat broj antisimetričnih relacija koje nisu ni refleksivne ni simetrične ([inlmath]\left(2^n-1\right)\left(3^\frac{n^2-n}{2}-1\right)[/inlmath]):
    [dispmath]\left(2^{n^2-n}-2^\frac{n^2-n}{2}\right)\left(2^n-1\right)-\left(2^n-1\right)\left(3^\frac{n^2-n}{2}-1\right)=\left(2^n-1\right)\left(2^{n^2-n}-2^\frac{n^2-n}{2}-3^\frac{n^2-n}{2}+1\right)[/dispmath]
  • Od ranije izračunatog broja relacija koje nisu ni refleksivne ni antisimetrične ([inlmath]\left(2^n-1\right)\left(2^{n^2-n}-3^\frac{n^2-n}{2}\right)[/inlmath]) oduzme se ranije izračunat broj simetričnih relacija koje nisu ni refleksivne ni antisimetrične ([inlmath]\left(2^n-1\right)\left(2^\frac{n^2-n}{2}-1\right)[/inlmath]):
    [dispmath]\left(2^n-1\right)\left(2^{n^2-n}-3^\frac{n^2-n}{2}\right)-\left(2^n-1\right)\left(2^\frac{n^2-n}{2}-1\right)=\left(2^n-1\right)\left(2^{n^2-n}-3^\frac{n^2-n}{2}-2^\frac{n^2-n}{2}+1\right)[/dispmath]
  • Od ranije izračunatog broja relacija koje nisu ni simetrične ni antisimetrične ([inlmath]2^{n^2}-2^n3^\frac{n^2-n}{2}-2^\frac{n^2+n}{2}+2^n[/inlmath]) oduzme se ranije izračunat broj refleksivnih relacija koje nisu ni simetrične ni antisimetrične ([inlmath]2^{n^2-n}-3^\frac{n^2-n}{2}-2^\frac{n^2-n}{2}+1[/inlmath]):
    [dispmath]\left(2^{n^2}-2^n3^\frac{n^2-n}{2}-2^\frac{n^2+n}{2}+2^n\right)-\left(2^{n^2-n}-3^\frac{n^2-n}{2}-2^\frac{n^2-n}{2}+1\right)=\\
    =2^n\left(2^{n^2-n}-3^\frac{n^2-n}{2}-2^\frac{n^2-n}{2}+1\right)-\left(2^{n^2-n}-3^\frac{n^2-n}{2}-2^\frac{n^2-n}{2}+1\right)=\\
    =\left(2^n-1\right)\left(2^{n^2-n}-3^\frac{n^2-n}{2}-2^\frac{n^2-n}{2}+1\right)[/dispmath]
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta

Re: Broj relacija (refleksivnih, simetričnih, antisimetričnih...) nad skupom od n elemenata

Postod Daniel » Ponedeljak, 03. Septembar 2018, 22:28

Osobina tranzitivnosti je nešto složenija od prethodno obrađenih, i za broj tranzitivnih funkcija ne postoji način (bar ne razumno jednostavan) da se izvede opšta formula, tako da se postupak svodi na puko prebrojavanje (u slučaju da broj elemenata skupa nije preveliki). Međutim, postoji formula (doduše, rekurentna) za broj relacija koje su istovremeno i refleksivne i simetrične i tranzitivne (tj. relacije ekvivalencije), a za relacije koje su istovremeno simetrične i tranzitivne postupak se može svesti na relacije ekvivalencije.



BROJ RELACIJA EKVIVALENCIJE

Relacija ekvivalencije je relacija koja ispunjava osobine refleksivnosti, simetričnosti i tranzitivnosti.
Za relaciju ekvivalencije vezuje se pojam klase ekvivalencije. Svi elementi koji su u međusobnoj relaciji formiraju po jednu klasu ekvivalencije. Svaki element pripada tačno jednoj klasi ekvivalencije.

Ako relaciju ekvivalencije predstavimo grafom, možemo uočiti sledeće:
  • Zbog refleksivnosti, svi čvorovi imaju petlju (jer je svaki element u relaciji sa sobom);
  • Zbog simetričnosti, graf je neusmeren (jer relacija između dva različita elementa mora biti obostrana);
  • Zbog tranzitivnosti (a i zbog simetričnosti), svaki čvor koji je povezan s drugim čvorom mora biti povezan sa svim čvorovima s kojima je taj drugi čvor povezan. Na taj način čvorovi se grupišu, formirajući kompletne podgrafove koji su međusobno disjunktni i tako da svaki čvor grafa pripada tačno jednom od tih kompletnih podgrafova. Svaki od tih kompletnih podgrafova odgovara jednoj klasi ekvivalencije.
Primer jedne relacije ekvivalencije, prikazan je na sledećem grafu.
[inlmath]\bigl\{(1,1),(2,2),(3,3),(3,4),(3,7),(4,3),(4,4),(4,7),(5,5),(6,6),(6,10),(7,3),(7,4),(7,7),(8,8),(8,9),(8,11),(8,12),(9,8),(9,9),(9,11),(9,12),(10,6),(10,10),(11,8),(11,9),(11,11),(11,12),(12,8),(12,9),(12,11),(12,12)\bigr\}[/inlmath]:

refleksivne, simetricne, tranzitivne.png
refleksivne, simetricne, tranzitivne.png (1.9 KiB) Pogledano 8099 puta

Može se uočiti analogija između načina na koje se graf može podeliti na kompletne podgrafove i načina na koje se neki skup može izdeliti na svoje disjunktne podskupove čija je unija upravo taj skup. Svaka podela skupa na takve podskupove predstavlja jednu particiju skupa. Gornji primer bi odgovarao particiji [inlmath]\bigl\{\{1\},\{2\},\{3,4,7\},\{5\},\{6,10\},\{8,9,11,12\}\bigr\}[/inlmath] skupa [inlmath]\{1,2,3,4,5,6,7,8,9,10,11,12\}[/inlmath], a svaki od disjunktnih podskupova [inlmath]\{1\},\{2\},\{3,4,7\},\{5\},\{6,10\},\{8,9,11,12\}[/inlmath] odgovara po jednoj klasi ekvivalencije posmatrane relacije. Prema tome, broj načina na koje graf s [inlmath]n[/inlmath] čvorova možemo izdeliti na kompletne podgrafove kao na gornjoj slici jednak je broju particija skupa sa [inlmath]n[/inlmath] elemenata. A to je, opet, jednako broju relacija ekvivalencije na skupu od [inlmath]n[/inlmath] elemenata. Ovaj broj se naziva Bellov broj (Eric Temple Bell, 1883–1960) i obeležava se sa [inlmath]B_n[/inlmath]. U daljem tekstu će biti izvedena formula (rekurentna, doduše) za izračunavanje [inlmath]B_n[/inlmath].

Za prazan skup ([inlmath]n=0[/inlmath]) važi da ima samo jednu relaciju, i ta relacija je relacija ekvivalencije (jer su i refleksivnost i simetričnost i tranzitivnost zadovoljene, budući da su leve strane implikacija u formalnim definicijama uvek netačne zbog nepostojanja nijednog elementa), što znači da je [inlmath]B_0=1[/inlmath]. Na sledećim grafovima možemo videti sve moguće relacije ekvivalencije za primere skupova od: jednog elementa ([inlmath]B_1=1[/inlmath]), od dva elementa ([inlmath]B_2=2[/inlmath]) i od tri elementa ([inlmath]B_3=5[/inlmath]):

B1.png
B1.png (377 Bajta) Pogledano 8099 puta

B2.png
B2.png (680 Bajta) Pogledano 8099 puta

B3.png
B3.png (1.83 KiB) Pogledano 8099 puta



BROJ RELACIJA KOJE SU I SIMETRIČNE I TRANZITIVNE

Kao i kod relacija ekvivalencije, i kod ovih relacija imamo grupisanje elemenata koji su u međusobnoj relaciji. Zbog toga što ovde sada ne mora važiti refleksivnost, ne moraju svi čvorovi u grafovima imati petlju. Imaće petlju oni čvorovi koji su povezani bar s jednim drugim čvorom, što direktno sledi iz simetričnosti i tranzitivnosti. Neka su [inlmath]x[/inlmath] i [inlmath]y[/inlmath] dva različita čvora i neka je [inlmath]x[/inlmath] u relaciji sa [inlmath]y[/inlmath], tj [inlmath]x\rho y[/inlmath]. Na osnovu simetričnosti sledi [inlmath]y\rho x[/inlmath]. Zatim, na osnovu tranzitivnosti, [inlmath]x\rho y\;\land\;y\rho x\;\Longrightarrow\;x\rho x[/inlmath], čije je pokazano da svaki element koji je u relaciji s bar jednim drugim elementom, mora biti u relaciji sa samim sobom.
Međutim, oni elementi koji nisu u relaciji ni s jednim drugim elementom, za razliku od relacije ekvivalencije kada su morali biti u relaciji sa samim sobom, sada ne moraju (mada i dalje mogu) biti sa sobom u relaciji. Ovi elementi predstavljaju i jedinu razliku između relacije koja je simetrična i tranzitivna i relacije ekvivalencije. Eliminisanjem tih elemenata koji nisu u relaciji sa samim sobom, ovakva relacija bi postala relacija ekvivalencije. To znači da i broj relacija koje su simetrične i tranzitivne možemo izraziti preko Bellovih brojeva. Neka je od ukupno [inlmath]n[/inlmath] elemenata skupa, njih [inlmath]k[/inlmath] u relaciji makar sa samim sobom (i koji, dakle, zadovoljavaju uslov relacije ekvivalencije). Postoji [inlmath]n\choose k[/inlmath] slučajeva u kojima se elementi skupa mogu naći među ovih [inlmath]k[/inlmath] elemenata (kombinacije bez ponavljanja od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase). Za svaki od tih [inlmath]n\choose k[/inlmath] slučajeva, relacija ekvivalencije se može formirati na [inlmath]B_k[/inlmath] načina. Kako [inlmath]k[/inlmath] može da ide od [inlmath]0[/inlmath] (slučaj kad nijedan od elemenata skupa nije u relaciji sa samim sobom) pa sve do [inlmath]n[/inlmath] (slučaj kada su svi elementi skupa u relaciji sa samim sobom i kada svi elementi skupa zadovoljavaju relaciju ekvivalencije), zaključujemo da broj relacija koje su i simetrične i tranzitivne iznosi
[dispmath]{n\choose0}B_0+{n\choose1}B_1+{n\choose2}B_2+\cdots+{n\choose n-1}B_{n-1}+{n\choose n}B_n[/dispmath] to jest
[dispmath]\sum_{k=0}^n{n\choose k}B_k[/dispmath] Posmatrajmo sada graf koji predstavlja jedan slučaj relacije koja je i simetrična i tranzitivna a nije refleksivna:

simetricne, tranzitivne.png
simetricne, tranzitivne.png (1.83 KiB) Pogledano 8099 puta

Kao što je prethodno rečeno, kod ovakve relacije svi čvorovi grafa koji su granama povezani s bar još nekim drugim čvorom, moraju imati petlju. Oni čvorovi koji nisu povezani granama ni s jednim drugim čvorom, mogu, ali ne moraju imati petlju. U gornjem primeru imamo dva čvora koja su bez petlje (čvor [inlmath]2[/inlmath] i čvor [inlmath]5[/inlmath]).
Dodajmo sada jedan novi čvor, koji će biti povezan sam sa sobom, i povežimo ga sa svim onim čvorovima koji su bez petlje, a zatim i tim čvorovima dodajmo petlju:

simetricne, tranzitivne - prosirivanje.png
simetricne, tranzitivne - prosirivanje.png (2.35 KiB) Pogledano 8099 puta

Na ovaj način, uvođenjem tog novog elementa u skup, izgradili smo klasu ekvivalencije (na gornjem grafu nacrtanu narandžasto) od elemenata koji nisu ispunjavali uslove relacije ekvivalencije. Ovime smo postigli da svi elementi pripadaju nekoj od klasa ekvivalencije, čime je relacija postala relacija ekvivalencije nad skupom od [inlmath](n+1)[/inlmath] elemenata, računajući i taj element koji smo dodali. Time je pokazano da svakoj relaciji nad skupom od [inlmath]n[/inlmath] elemenata koja je simetrična i tranzitivna odgovara neka od relacija ekvivalencije nad skupom od [inlmath](n+1)[/inlmath] elemenata, a kojih ima [inlmath]B_{n+1}[/inlmath]. Dakle, postoji ukupno [inlmath]B_{n+1}[/inlmath] relacija nad skupom od [inlmath]n[/inlmath] elemenata koje su simetrične i tranzitivne.

A kako smo malopre takođe pokazali da takvih relacija ima i [inlmath]\sum\limits_{k=0}^n{n\choose k}B_k[/inlmath], odatle dobijamo rekurentnu vezu za računanje Bellovih brojeva:
[dispmath]\enclose{box}{B_{n+1}=\sum_{k=0}^n{n\choose k}B_k}[/dispmath] pri čemu je, kao što je gore objašnjeno, [inlmath]B_0=1[/inlmath]. U sledećoj tabeli prikazano je prvih [inlmath]11[/inlmath] Bellovih brojeva:
[dispmath]\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\ \hline
B_n & 1 & 1 & 2 & 5 & 15 & 52 & 203 & 877 & 4140 & 21147 & 115975\\ \hline
\end{array}[/dispmath]



BROJ RELACIJA KOJE SU I SIMETRIČNE I TRANZITIVNE A NISU REFLEKSIVNE

Dobija se tako što se od broja relacija koje su i simetrične i tranzitivne ([inlmath]B_{n+1}[/inlmath]) oduzme broj relacija koje su i refleksivne i simetrične i tranzitivne, tj. broj relacija ekvivalencije ([inlmath]B_n[/inlmath]):
[dispmath]B_{n+1}-B_n[/dispmath]



BROJ RELACIJA KOJE SU I SIMETRIČNE I ANTISIMETRIČNE I TRANZITIVNE

Ranije je pokazano da nad nekim skupom od [inlmath]n[/inlmath] elemenata postoji tačno [inlmath]2^n[/inlmath] relacija koje su i simetrične i antisimetrične. To su relacije kod kojih nijedan element nije u relaciji ni s jednim drugim elementom (u tabeli su sva polja van glavne dijagonale prazna, dok na glavnoj dijagonali mogu biti proizvoljno (ne)popunjena). Odatle sledi da leva strana implikacije u formalnoj definiciji tranzitivnosti, [inlmath]x\rho y\;\land\;y\rho z[/inlmath], može biti tačna jedino onda kada je [inlmath]x=y=z[/inlmath], a ako je tada tačna to znači da je element [inlmath]x(=y=z)[/inlmath] u relaciji sam sa sobom, pa će tada biti tačna i desna strana implikacije, [inlmath]x\rho z[/inlmath]. U ostalim slučajevima, kada je leva strana implikacije netačna, implikacija će biti tačna bez obzira na tačnost desne strane. Prema tome, implikacija je uvek tačna, što znači da je tranzitivnost zadovoljena. Ovime je pokazano da je relacija koja je i simetrična i antisimetrična istovremeno i tranzitivna, što znači da je broj relacija koje su i simetrične i antisimetrične i tranzitivne jednak ranije dobijenom broju relacija koje su i simetrične i antisimetrične, a koji iznosi [inlmath]2^n[/inlmath].



BROJ RELACIJA KOJE SU I RELACIJE EKVIVALENCIJE I RELACIJE PORETKA

Da bi neka relacija bila istovremeno i relacija ekvivalencije i relacija poretka, neophodan (ne i dovoljan) uslov je da bude i refleksivna, i simetrična, i antisimetrična. Ranije je pokazano da nad nekim skupom od [inlmath]n[/inlmath] elemenata postoji tačno jedna relacija koja ima ove tri osobine. To je relacija kod koje je svaki element u relaciji sa samim sobom, i nijedan element nije u relaciji ni s jednim drugim elementom. Odatle sledi da je leva strana implikacije u formalnoj definiciji tranzitivnosti, [inlmath]x\rho y\;\land\;y\rho z[/inlmath], tačna jedino onda kada je [inlmath]x=y=z[/inlmath], a tada će biti tačna i desna strana implikacije, [inlmath]x\rho z[/inlmath]. U ostalim slučajevima, kada je leva strana implikacije netačna, implikacija će biti tačna bez obzira na tačnost desne strane. Prema tome, implikacija je uvek tačna, što znači da je tranzitivnost zadovoljena. Pošto je takva relacija i refleksivna i simetrična i antisimetrična i tranzitivna, sledi da je to i relacija ekvivalencije i relacija poretka, i broj takvih relacija nad bilo kojim skupom jeste [inlmath]1[/inlmath].



BROJ RELACIJA KOJE SU I SIMETRIČNE I ANTISIMETRIČNE I TRANZITIVNE A NISU REFLEKSIVNE

Dobija se tako što se od ranije izračunatog broja relacija koje su i simetrične i antisimetrične i tranzitivne ([inlmath]2^n[/inlmath]) oduzme ranije izračunat broj relacija koje su i refleksivne i simetrične i antisimetrične i tranzitivne ([inlmath]1[/inlmath]):
[dispmath]2^n-1[/dispmath] [inlmath]2^n[/inlmath] predstavlja zapravo broj onih relacija kod kojih su u tabelarnom prikazu sva polja van glavne dijagonale prazna a polja na glavnoj dijagonali mogu biti proizvoljno (ne)popunjena. Od ovog broja se oduzima broj jedan, zbog toga što postoji samo jedna relacija kod koje su u tabelarnom prikazu sva polja van glavne dijagonale prazna, a na glavnoj dijagonali sva polja popunjena.



ZAKLJUČAK

U sledećoj tabeli biće navedene formule za brojeve relacija u zavisnosti od njihovih osobina, a do kojih smo došli u okviru ovog tutorijala.
[inlmath]R[/inlmath] – refleksivnost
[inlmath]S[/inlmath] – simetričnost
[inlmath]A[/inlmath] – antisimetričnost
[inlmath]T[/inlmath] – tranzitivnost
[dispmath]\begin{array}{|c|c|c|} \hline
\text{Zadovoljava osobinu} & \text{Ne zadovoljava osobinu} & \text{Broj relacija s navedenim osobinama}\\ \hline
- & - & \displaystyle2^{n^2}\\ \hline
R & - & \displaystyle2^{n^2-n}\\ \hline
S & - & \displaystyle2^\frac{n^2+n}{2}\\ \hline
RS & - & \displaystyle2^\frac{n^2-n}{2}\\ \hline
- & R & \displaystyle\left(2^n-1\right)2^{n^2-n}\\ \hline
- & S & \displaystyle2^{n^2}-2^\frac{n^2+n}{2}\\ \hline
R & S & \displaystyle2^{n^2-n}-2^\frac{n^2-n}{2}\\ \hline
S & R & \displaystyle\left(2^n-1\right)2^\frac{n^2-n}{2}\\ \hline
- & RS & \displaystyle\left(2^n-1\right)\left(2^{n^2-n}-2^\frac{n^2-n}{2}\right)\\ \hline
A & - & \displaystyle2^n3^\frac{n^2-n}{2}\\ \hline
RA & - & \displaystyle3^\frac{n^2-n}{2}\\ \hline
SA & - & \displaystyle2^n\\ \hline
RSA & - & \displaystyle1\\ \hline
A & R & \displaystyle\left(2^n-1\right)3^\frac{n^2-n}{2}\\ \hline
A & S & \displaystyle2^n\left(3^\frac{n^2-n}{2}-1\right)\\ \hline
RA & S & \displaystyle3^\frac{n^2-n}{2}-1\\ \hline
SA & R & \displaystyle2^n-1\\ \hline
A & RS & \displaystyle\left(2^n-1\right)\left(3^\frac{n^2-n}{2}-1\right)\\ \hline
- & A & \displaystyle2^{n^2}-2^n3^\frac{n^2-n}{2}\\ \hline
R & A & \displaystyle2^{n^2-n}-3^\frac{n^2-n}{2}\\ \hline
S & A & \displaystyle2^\frac{n^2+n}{2}-2^n\\ \hline
RS & A & \displaystyle2^\frac{n^2-n}{2}-1\\ \hline
- & RA & \displaystyle\left(2^n-1\right)\left(2^{n^2-n}-3^\frac{n^2-n}{2}\right)\\ \hline
- & SA & \displaystyle2^{n^2}-2^n3^\frac{n^2-n}{2}-2^\frac{n^2+n}{2}+2^n\\ \hline
R & SA & \displaystyle2^{n^2-n}-2^\frac{n^2-n}{2}-3^\frac{n^2-n}{2}+1\\ \hline
S & RA & \displaystyle\left(2^n-1\right)\left(2^\frac{n^2-n}{2}-1\right)\\ \hline
- & RSA & \displaystyle\left(2^n-1\right)\left(2^{n^2-n}-2^\frac{n^2-n}{2}-3^\frac{n^2-n}{2}+1\right)\\ \hline
RST & - & \displaystyle B_n=\sum_{k=0}^{n-1}{n-1\choose k}B_k,\;B_0=1\\ \hline
ST & - & \displaystyle B_{n+1}=\sum_{k=0}^n{n\choose k}B_k,\;B_0=1\\ \hline
ST & R & \displaystyle B_{n+1}-B_n\\ \hline
SAT & - & \displaystyle2^n\\ \hline
RSAT & - & \displaystyle1\\ \hline
SAT & R & \displaystyle2^n-1\\ \hline
\end{array}[/dispmath]


Uputio bih čitaoca i na online program za ispitivanje relacija, u kojem se za relaciju unetu u vidu skupa uređenih parova prikazuje koje od osobina (refleksivnost, simetričnost itd.) jesu, a koje nisu zadovoljene.
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta


Povratak na TEORIJA SKUPOVA

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 27 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 10:35 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs