| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
Gia
Forumaš(ica)
Pridružen/a: 20. 06. 2004. (00:46:02)
Postovi: (1D)16
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol: 
Lokacija: /sbin/init
|
 Postano: 14:27 čet, 1. 7. 2004 Naslov: |
    |
|
|
Broj binarnih rekacija: 2^(n^2) (dva na (na na kvadrat))
Zasto? :-k Matricna reprezentacija (0 ili 1). 8)
Broj simetricnih = broj antisimetricnih je 2^(n*(n+1)/2)
Zasto? :-k Opet matricna reprezentacija, s tim da jedan trokut (kad podijelis matricu po dijagonali) mozes zadati proizvoljno (sto je n*(n+1)/2 elemenata), a ostatak je onda jednoznacno definiran! :)
Rezultat: oduzmes ukupno - br_simetricnih - br_antisimetricnih = ukupno - 2 * br_sim
2^(n^2) - 2 * 2^(n*(n+1)/2)
Nadam se da nisam fulao... :oops: Kombinatorika mi je nekad bila jako draga, ali sam dosta ispao iz toga... :(
Broj binarnih rekacija: 2^(n^2) (dva na (na na kvadrat))
Zasto?  Matricna reprezentacija (0 ili 1). 
Broj simetricnih = broj antisimetricnih je 2^(n*(n+1)/2)
Zasto? Opet matricna reprezentacija, s tim da jedan trokut (kad podijelis matricu po dijagonali) mozes zadati proizvoljno (sto je n*(n+1)/2 elemenata), a ostatak je onda jednoznacno definiran! 
Rezultat: oduzmes ukupno - br_simetricnih - br_antisimetricnih = ukupno - 2 * br_sim
2^(n^2) - 2 * 2^(n*(n+1)/2)
Nadam se da nisam fulao...  Kombinatorika mi je nekad bila jako draga, ali sam dosta ispao iz toga... 
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.  |
|
| [Vrh] |
|
ahri
Forumaš(ica)
Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
|
|
| [Vrh] |
|
veky
Forumaš(ica)
Pridružen/a: 09. 12. 2002. (19:59:43)
Postovi: (5B0)16
Lokacija: negdje daleko...
|
| Postano: 13:17 pet, 9. 7. 2004 Naslov: Re: Pitanje-binarne relacije |
|
|
|
[quote="Gia"]Koliko razlicitih binarnih relacija postoji na skupu od n elemenata koje nisu ni simetricne ni antisimetricne?[/quote]
FUI. Koliko ih ima ukupno minus koliko ih ima simetričnih, minus koliko
ih ima antisimetričnih, plus koliko ih ima koje su oboje.
Pri svakom brojenju efektivno brojiš tablice nulā i jedinicā
veličine nxn , koje predstavljaju karakteristične funkcije tih
relacijā.
Ukupno: svaka tablica je preslikavanje :n^2->2 , dakle
svih tablica ima 2^n^2 .
Simetričnih: na dijagonali i u gornjem trokutu može stajati bilo što.
Onda je donji trokut jednoznačno određen (jednako izgleda kao i
gornji). Dakle, možemo slobodno 2-birati n(n+1)/2 elemenata, pa je
odgovor 2^(n(n+1)/2) .
Za antisimetrične: dijagonalu ( n elemenata) 2-biramo slobodno. Ostalih
n^2-n elemenata čine (n povrh 2) parova. Za svaki od tih parova ok su
tri mogućnosti: ili je jedan u relaciji, ili drugi, ili nijedan (samo
ne smiju biti oba, jer bi onda po antisimetričnosti stvar morala biti
na dijagonali). So, odgovor je 2^n*3^(n povrh 2) .
Oboje: ako je relacija i simetrična i antisimerična, opet dijagonalu
možemo birati po volji, ali lako se vidi da je sve osim dijagonale
fiksirano na 0 ( kad bi bilo a(!=)b&aRB , po simetričnosti bi bilo i bRa ,
a tada bi po antisimetričnosti bilo a=b , što nije). Dakle, tu je
odgovor 2^n .
Final answer je 2^n^2+2^n-2^(n(n+1)/2)-2^n*3^(n(n-1)/2) .
| Gia (napisa): | | Koliko razlicitih binarnih relacija postoji na skupu od n elemenata koje nisu ni simetricne ni antisimetricne? |
FUI. Koliko ih ima ukupno minus koliko ih ima simetričnih, minus koliko
ih ima antisimetričnih, plus koliko ih ima koje su oboje.
Pri svakom brojenju efektivno brojiš tablice nulā i jedinicā
veličine nxn , koje predstavljaju karakteristične funkcije tih
relacijā.
Ukupno: svaka tablica je preslikavanje :n^2→2 , dakle
svih tablica ima 2^n^2 .
Simetričnih: na dijagonali i u gornjem trokutu može stajati bilo što.
Onda je donji trokut jednoznačno određen (jednako izgleda kao i
gornji). Dakle, možemo slobodno 2-birati n(n+1)/2 elemenata, pa je
odgovor 2^(n(n+1)/2) .
Za antisimetrične: dijagonalu ( n elemenata) 2-biramo slobodno. Ostalih
n^2-n elemenata čine (n povrh 2) parova. Za svaki od tih parova ok su
tri mogućnosti: ili je jedan u relaciji, ili drugi, ili nijedan (samo
ne smiju biti oba, jer bi onda po antisimetričnosti stvar morala biti
na dijagonali). So, odgovor je 2^n*3^(n povrh 2) .
Oboje: ako je relacija i simetrična i antisimerična, opet dijagonalu
možemo birati po volji, ali lako se vidi da je sve osim dijagonale
fiksirano na 0 ( kad bi bilo a(!=)b&aRB , po simetričnosti bi bilo i bRa ,
a tada bi po antisimetričnosti bilo a=b , što nije). Dakle, tu je
odgovor 2^n .
Final answer je 2^n^2+2^n-2^(n(n+1)/2)-2^n*3^(n(n-1)/2) .
|
|
| [Vrh] |
|
krcko
Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
|
| [Vrh] |
|
krcko
Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
|
|
| [Vrh] |
|
|
a hvala i vsegi i ahriju na dobrim namjerama. 
Zbilja bi bilo steta da je zavrsilo 
Prije ili poslije ce ih stici tvoja pravda... 
