MATEMANIJA

Zdravo iz zbirke

Diskretna matematika
Osnove kombinatorike i teorije grafova
-Zbirka resenih zadataka-

Glasi:
Koliko se binarnih relacija moze definisati na skupu sa [inlmath]n[/inlmath] elemenata? Koliko postoji:
a) refleksivnih
b) simetricnih
c) refleksivnih i simetricnih

---

Resenje za opste pitanje:
Neka je [inlmath]X_{n,n}=\{1,2,\ldots,n\}\times\{1,2,\ldots,n\}[/inlmath].
Binarna relacija [inlmath]p[/inlmath] na skupu [inlmath]\{1,2,\ldots,n\}[/inlmath] je svaki podskup skupa [inlmath]X[/inlmath], pa je ukupan broj binarnih relacija jednak [inlmath]2^{\left(n^2\right)}[/inlmath]

Razumem odgovor za, koliko se binarnih relacija moze definisati na skupu sa [inlmath]n[/inlmath] elementa
Pa jel moze da se preformulise moje pitanje
Koliko postoji relacija na skupu od [inlmath]n[/inlmath] elemenata koje su:
a) refleksivne
b) simetricne
c) refleksivne i simetricne

Ima i resenje
1) Relacija [inlmath]p[/inlmath] je refleksivna ako sadrzi skup [inlmath]\{(1,1),(2,2),\ldots,(n,n)\}[/inlmath]. Od preostalih [inlmath]n^2-n[/inlmath] uredjenih parova iz skupa [inlmath]X_{n,n}[/inlmath] moze se izabrati proizvoljan podskup, pa je ukupan broj refleksivnih relacija jednak [inlmath]2^{\left(n^2-n\right)}[/inlmath].

Pitanje:
ne razumem sta smo ovde radili, jasno mi je da je skup
[inlmath]\{(1,1),(2,2)\ldots(n,n)\}[/inlmath]
refleksivna relacija, i da takvih elementa ima [inlmath]n[/inlmath], i po mojoj logici
tu bih stao, rekao bih da ih ima [inlmath]2^n[/inlmath]?
Ne razumem sta se krije iza resenja [inlmath]2^{\left(n^2-n\right)}[/inlmath]

b) Relacija [inlmath]p[/inlmath] je simetricna ako za svaki uredjeni par [inlmath](x,y)[/inlmath] sadrzi i uredjeni par [inlmath](y,x)[/inlmath]. Zato je simetricna relacija [inlmath]p[/inlmath] u potpunosti odredjena ako znamo koji uredjeni parovi [inlmath](x,y)[/inlmath], kod kojih je [inlmath]x\le y[/inlmath] pripadaju [inlmath]p[/inlmath]. Takvih parova ima [inlmath]\frac{n(n+1)}{2}[/inlmath]
pa je ukupan broj simetricnih relacija jednak [inlmath]2^{\left(\frac{n(n+1)}{2}\right)}[/inlmath]

Pitanje:
Ne razumem sta se krije iza [inlmath]\frac{n(n+1)}{2}[/inlmath]
Jel ima ovo neke logike
imamo [inlmath]n[/inlmath] elementa i treba da ih spojimo sa ostalima (tu racunamo i prazan skup otuda [inlmath]n+1[/inlmath])
pa posto smo ih racunali kao [inlmath](x,y)[/inlmath] i kao [inlmath](y,x)[/inlmath], nama to nista ne znaci pa delimo sve sa [inlmath]2[/inlmath]

c) Refleksivna i simetricna relacija [inlmath]p[/inlmath] sadrzi skup [inlmath]\{(1,1),\ldots,(n,n)\}[/inlmath]
a u potpunosti je odredjena ako znamo koji uredjeni parovi [inlmath](x,y)[/inlmath], kod kojih je [inlmath]x<y[/inlmath], pripadaju [inlmath]p[/inlmath]. Ovakvih parova ima [inlmath]\frac{n(n-1)}{2}[/inlmath], pa zato je ukupan broj refleksivnih i simetricnih relacija jednak [inlmath]2^{\left(\frac{n(n-1)}{2}\right)}[/inlmath]

Pitanje:
Za ovaj imam samo neku malu predstavu da stoji [inlmath]n-1[/inlmath], posto se radi o operatoru [inlmath]<[/inlmath].

Prepravio sam ti LaTex. Pre nego što klikneš na "Pošalji" imaš opciju "Pregled" da vidiš kako će tvoj post izgledati. Za razlomak se koristi komanda \frac umesto /. Molim te da proveriš da li sam sve prepravio onako kako bi trebalo da piše.
Možda si hteo umesto [inlmath]p[/inlmath] za relaciju da koristiš oznaku [inlmath]\rho[/inlmath]?

To je to hvala, hteo sam [inlmath]\rho[/inlmath]
A za ostalo, pretisao sam "Pregled" pre "Posalji", mislio sam da onako treba...

Loophoop je napisao:1) Relacija [inlmath]p[/inlmath] je refleksivna ako sadrzi skup [inlmath]\{(1,1),(2,2),\ldots,(n,n)\}[/inlmath]. Od preostalih [inlmath]n^2-n[/inlmath] uredjenih parova iz skupa [inlmath]X_{n,n}[/inlmath] moze se izabrati proizvoljan podskup, pa je ukupan broj refleksivnih relacija jednak [inlmath]2^{\left(n^2-n\right)}[/inlmath].

Pitanje:
ne razumem sta smo ovde radili, jasno mi je da je skup
[inlmath]\{(1,1),(2,2)\ldots(n,n)\}[/inlmath]
refleksivna relacija, i da takvih elementa ima [inlmath]n[/inlmath], i po mojoj logici
tu bih stao, rekao bih da ih ima [inlmath]2^n[/inlmath]?
Ne razumem sta se krije iza resenja [inlmath]2^{\left(n^2-n\right)}[/inlmath]

Najlakše je to posmatrati tabelarno. Verovatno znaš za tabelarno prikazivanje relacija – ako je npr. [inlmath]1.[/inlmath] element u relaciji s [inlmath]3.[/inlmath] elementom, tada popunjavamo polje koje se nalazi u [inlmath]1.[/inlmath] vrsti i u [inlmath]3.[/inlmath] koloni. Kod relacija koje su refleksivne, tj. kod kojih je [inlmath]1.[/inlmath] element u relaciji s [inlmath]1.[/inlmath] elementom, [inlmath]2.[/inlmath] element u relaciji s [inlmath]2.[/inlmath] elementom itd., biće popunjena sva polja na glavnoj dijagonali, dok ćemo ostala polja popuniti znacima pitanja, jer ostali elementi mogu, ali i ne moraju, biti u relaciji s ostalim elementima:
[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] Ukupan broj polja je [inlmath]n^2[/inlmath]. Na glavnoj dijagonali imamo [inlmath]n[/inlmath] polja. Znači, kad od ukupnog broja polja oduzmemo broj polja na glavnoj dijagonali, dobijamo broj onih polja koja možemo proizvoljno (ne) popunjavati (koja su označena znacima pitanja). Takvih polja ima [inlmath]n^2-n[/inlmath], a pošto svako od njih možemo ili popuniti ili ne popuniti, broj takvih mogućnosti je [inlmath]2^{n^2-n}[/inlmath].

Loophoop je napisao:b) Relacija [inlmath]p[/inlmath] je simetricna ako za svaki uredjeni par [inlmath](x,y)[/inlmath] sadrzi i uredjeni par [inlmath](y,x)[/inlmath]. Zato je simetricna relacija [inlmath]p[/inlmath] u potpunosti odredjena ako znamo koji uredjeni parovi [inlmath](x,y)[/inlmath], kod kojih je [inlmath]x\le y[/inlmath] pripadaju [inlmath]p[/inlmath]. Takvih parova ima [inlmath]\frac{n(n+1)}{2}[/inlmath]
pa je ukupan broj simetricnih relacija jednak [inlmath]2^{\left(\frac{n(n+1)}{2}\right)}[/inlmath]

Pitanje:
Ne razumem sta se krije iza [inlmath]\frac{n(n+1)}{2}[/inlmath]

Pošto je relacija simetrična, znači da u odnosu na glavnu dijagonalu polja moraju biti simetrično popunjena. To znači, ako je polje [inlmath](1,3)[/inlmath] popunjeno, tada mora biti popunjeno i polje [inlmath](3,1)[/inlmath]. Ako polje [inlmath](2,3)[/inlmath] nije popunjeno, tada ne sme biti popunjeno ni polje [inlmath](3,2)[/inlmath] itd.
Zbog toga polja iznad glavne dijagonale ne smemo popunjavati proizvoljno, već je njihova (ne)popunjenost uslovljena (ne)popunjenošću polja ispod glavne dijagonale.
Polja na glavnoj dijagonali možemo popunjavati proizvoljno, jer nije dat uslov da je ova relacija refleksivna.
[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] I sad prebrojavamo koliko imamo polja s upitnicima (tj. polja koja možemo proizvoljno popunjavati). U prvoj vrsti imamo [inlmath]1[/inlmath] takvo polje. U drugoj vrsti ih imamo [inlmath]2[/inlmath]. U trećoj ih imamo [inlmath]3[/inlmath]. U [inlmath](n-1).[/inlmath] vrsti ih imamo [inlmath]n-1[/inlmath] i u [inlmath]n[/inlmath]-toj vrsti ih imamo [inlmath]n[/inlmath]. Njihov broj, dakle, dobijamo kao sumu aritmetičkog niza [inlmath]1+2+\cdots+n[/inlmath], a to je [inlmath]\frac{n(n+1)}{2}[/inlmath].
Ukupan broj načina da se takva tabela popuni (tj. ukupan broj simetričnih relacija na skupu od [inlmath]n[/inlmath] elemenata) iznosi, prema tome, [inlmath]2^\frac{n(n+1)}{2}[/inlmath].

(Naravno, isti rezultat bismo dobili i da smo u polja iznad glavne dijagonale upisali znake pitanja, a da smo sadržaje polja ispod glavne dijagonale uslovili sadržajima polja iznad glavne dijagonale.)

Loophoop je napisao:Jel ima ovo neke logike
imamo [inlmath]n[/inlmath] elementa i treba da ih spojimo sa ostalima (tu racunamo i prazan skup otuda [inlmath]n+1[/inlmath])
pa posto smo ih racunali kao [inlmath](x,y)[/inlmath] i kao [inlmath](y,x)[/inlmath], nama to nista ne znaci pa delimo sve sa [inlmath]2[/inlmath]

Ovo nisam razumeo, pa ne mogu ni da komentarišem.

Loophoop je napisao:c) Refleksivna i simetricna relacija [inlmath]p[/inlmath] sadrzi skup [inlmath]\{(1,1),\ldots,(n,n)\}[/inlmath]
a u potpunosti je odredjena ako znamo koji uredjeni parovi [inlmath](x,y)[/inlmath], kod kojih je [inlmath]x<y[/inlmath], pripadaju [inlmath]p[/inlmath]. Ovakvih parova ima [inlmath]\frac{n(n-1)}{2}[/inlmath], pa zato je ukupan broj refleksivnih i simetricnih relacija jednak [inlmath]2^{\left(\frac{n(n-1)}{2}\right)}[/inlmath]

Vrlo je slično kao i pod b), samo što ovde, naravno, ne smeš elemente na glavnoj dijagonali uzimati proizvoljno – glavna dijagonala mora biti popunjena, zbog refleksivnosti. Ovo ostavljam tebi da uradiš, a kao pomć, tu ti je tabela za ovaj slučaj:
[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]
Bilo bi korisno da pogledaš i ovu temu.


EDIT 24.9.2018: Postavljena tema o broju svih binarnih relacija nad skupom od [inlmath]n[/inlmath] elemenata – LINK.