Pozdrav svima, pripremam se za kolokvijum iz predmeta "Diskretna matematika 1", pa imam neke zadatke u cijem cete mi rjesavanju, nadam se, pomoci.

Na koliko načina tri studenta studijskog programa matematika, tri studenta studijskog programa računarske nauke i tri studijskog programa fizika možemo poređati u vrstu, ali tako da ne postoje dva studenta istog studijskog programa koji stoje jedan pored drugog?

Uradio sam zadatak, medjutim nisam siguran da li je to pravo rjesenje. Evo kako sam radio:

[inlmath]A[/inlmath] - Ne postoje dva studenta smjera matematika koji su susjedi.
[inlmath]B[/inlmath] - Ne postoje dva studenta smjera racunarske nauke koji su susjedi.
[inlmath]C[/inlmath] - Ne postoje dva studenta smjera fizika koji su susjedi.

Prema formuli ukljucenja-iskljucenja imamo da je [inlmath]|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|[/inlmath]

E sad da izracunamo kardinalnost skupa [inlmath]A[/inlmath]. Posto nas interesuju samo studenti smjera Matematika, ostale rasporedjujemo na [inlmath]6![/inlmath] nacina. Sada za studente matematike imamo sljedece opcije [inlmath]\_X\_X\_X\_X\_X\_X\_[/inlmath] ([inlmath]X[/inlmath] su vec rasporedjeni studenti), odnosno od [inlmath]7[/inlmath] mogucih pozicija mi biramo [inlmath]3[/inlmath] (i time obezbjedjujemo da ne bude susjednih), a zatim medjusobno permutujemo, znaci kardinalnost skupa [inlmath]A[/inlmath] je [inlmath]6!\cdot{7\choose3}\cdot3![/inlmath].

Postupak je isti i za skupove [inlmath]B[/inlmath] i [inlmath]C[/inlmath]. Sada trazimo [inlmath]|A\cap B|[/inlmath], odnosno situacije u kojima ni medju studentima matematike ni medju studentima racunarskih nauka nema susjeda. Odmah rasporedimo studente fizike na [inlmath]3![/inlmath] nacina, pa imamo sljedecu situaciju [inlmath]\_X\_X\_X\_[/inlmath] . Biramo [inlmath]3[/inlmath] od potencijalna [inlmath]4[/inlmath] mjesta i na njih rasporedjujemo studente matematika, i na kraju studente racunarskih nauka rasporedjujemo kao kada smo trazili kardinalnost skupa [inlmath]A[/inlmath]. Sve to zajedno je [inlmath]3!\cdot{4\choose3}\cdot3!\cdot{7\choose3}\cdot3![/inlmath].

Proces je isti i za ostale presjeke, sada trazimo [inlmath]|A\cap B\cap C|[/inlmath]. Postavimo [inlmath]3[/inlmath] studenta matematike na [inlmath]3![/inlmath] nacina, i imamo sljedecu situaciju [inlmath]\_X{\color{red}\_}X{\color{red}\_}X\_[/inlmath] , medjutim za razliku od prethodnih situacija obje crvene crtice moramo popuniti sa studentima (npr.) Racunarskih nauka da ne bi bilo susjednih studenata matematike, pa nam se shodno tome izbor crtica sveo na [inlmath]2[/inlmath]. U konacnom to je [inlmath]3!\cdot2\cdot3!\cdot{7\choose3}\cdot3![/inlmath].

Na kraju sve ovo uvrstimo u formulu (prvi put se susrijecem sa Latexom pa sam malo izgubio strpljenje da dalje kucam ). Da li je ovo ispravno rjesenje zadatka?

Nažalost, pretpostavljam da je kolokvijum prošao , ali sa druge strane, pretpostavljam da nekome kolokvijum tek sledi, pa ću postaviti rešenje ovog zadatka, nadam se da će nekome koristiti.
Rešenje koje je izneo Shonewizard nije tačno.

Prvo ćemo odrediti broj permutacija u kojima stoje zajedno:
a) [inlmath]2[/inlmath] studenta jednog smera: [inlmath]3\cdot{3\choose2}\cdot2!\cdot8![/inlmath];
b) po [inlmath]2[/inlmath] studenta [inlmath]2[/inlmath] smera (ne nužno sva četvorica zajedno): [inlmath]{3\choose2}^3\cdot(2!)^2\cdot7![/inlmath];
c) po [inlmath]2[/inlmath] studenta sva [inlmath]3[/inlmath] smera: [inlmath]{3\choose2}^3\cdot(2!)^3\cdot6![/inlmath];
d) [inlmath]3[/inlmath] studenta jednog smera: [inlmath]3\cdot3!\cdot7![/inlmath];
e) po [inlmath]3[/inlmath] studenta [inlmath]2[/inlmath] smera: [inlmath]{3\choose2}\cdot(3!)^2\cdot5![/inlmath];
f) po [inlmath]3[/inlmath] studenta sva [inlmath]3[/inlmath] smera: [inlmath](3!)^4[/inlmath];
g) [inlmath]3[/inlmath] studenta jednog smera i [inlmath]2[/inlmath] studenta drugog smera: [inlmath]3\cdot2\cdot{3\choose2}\cdot3!\cdot2!\cdot6![/inlmath];
h) [inlmath]3[/inlmath] studenta jednog smera i po [inlmath]2[/inlmath] studenta drugog i trećeg smera: [inlmath]3\cdot{3\choose2}^2\cdot3!\cdot(2!)^2\cdot5![/inlmath];
i) po [inlmath]3[/inlmath] studenta [inlmath]2[/inlmath] smera i [inlmath]2[/inlmath] studenta trećeg smera: [inlmath]3\cdot{3\choose2}\cdot(3!)^2\cdot2!\cdot4![/inlmath];
Potom ovo uvrstimo u formulu uključivanja i isključivanja:
[dispmath]9!-9\cdot2!\cdot8!+27\cdot(2!)^2\cdot7!-27\cdot(2!)^3\cdot6!+3\cdot3!\cdot7!+3\cdot(3!)^2\cdot5!+\\
+(3!)^4-18\cdot3!\cdot2!\cdot6!+27\cdot3!\cdot(2!)^2\cdot5!-9\cdot(3!)^2\cdot2!\cdot4!=37584[/dispmath]
Zadatak je malo naporan . Nadam se da je rešenje tačno, proverio sam i u jednoj zbirci sa vrlo sličnim zadatkom, tako da se nadam da nisam pogrešio.

Potvrđujem tačnost rezultata, a proveru sam izvršio na skroz primitivan način – prebrojavanjem slučajeva. Naravno, ne sva [inlmath]37584[/inlmath] slučaja, tol'ko prso nisam, nego sam prvo posmatrao niz od [inlmath]9[/inlmath] cifara, sastavljen od cifara [inlmath]1[/inlmath], [inlmath]2[/inlmath] i [inlmath]3[/inlmath], od kojih se svaka ponavlja [inlmath]3[/inlmath] puta. Pošto se u originalnom problemu mogu razlikovati dva slučaja – u prvom slučaju se na prva tri mesta nalaze studenti tri različita smera, a u drugom slučaju se na prvom i na trećem mestu nalaze studenti istog smera dok je na drugom mestu student nekog od preostala dva smera – ovde sam prebrojavao slučajeve nizova koji počinju na [inlmath]123[/inlmath] i nizova koji počinju na [inlmath]121[/inlmath] (i kod kojih nikoje dve iste cifre ne mogu stajati jedna do druge):
[dispmath]\begin{array}{lll}
121231323 & 123121323 & 123212313\\
121232313 & 123123123 & 123213123\\
121312323 & 123123132 & 123213132\\
121313232 & 123123213 & 123213213\\
121321323 & 123123231 & 123213231\\
121323123 & 123131232 & 123231213\\
121323132 & 123132123 & 123231231\\
121323213 & 123132132 & 123231312\\
121323231 & 123132312 & 123231321\\
& 123132321 & 123232131
\end{array}[/dispmath] Znači, ukupno [inlmath]29[/inlmath]. Budući da postoji [inlmath]3![/inlmath] načina na koji svakoj od cifara [inlmath]1[/inlmath], [inlmath]2[/inlmath] i [inlmath]3[/inlmath] možemo pridružiti svaki od smerova matematika, računarske nauke i fizika, to [inlmath]29[/inlmath] množimo sa [inlmath]3![/inlmath]. I, pošto [inlmath]3[/inlmath] studenta unutar svakog od smerova možemo međusobno rasporediti na [inlmath]3![/inlmath] načina, to proizvod [inlmath]29\cdot3![/inlmath] još pomnožimo sa [inlmath]3!\cdot3!\cdot3![/inlmath] i dobijemo [inlmath]29\cdot(3!)^4[/inlmath], a to je [inlmath]37584[/inlmath], kao što je Corba248 i dobio.

Opet naglašavam, ovaj postupak ne bi mogao biti priznat kao validan budući da se svodi na prebrojavanje mogućnosti, ali može poslužiti za proveru rezultata koji je Corba248 dobio. Corba248, svaka čast za rešenje.

---

U Shonewizardovom postupku greška je u tome što je traženi broj načina računat kao [inlmath]|A\cup B\cup C|[/inlmath] (što predstavlja broj slučajeva u kojima za bar jedan smer važi da njegova tri studenta nisu jedan do drugog), a zapravo je trebalo da bude računat kao [inlmath]|A\cap B\cap C|[/inlmath] (dakle, broj slučajeva u kojima za sva tri smera važi da studenti istog smera nisu jedan do drugog).

Takođe, greška je i u ovom delu:

Shonewizard je napisao:Sada trazimo [inlmath]|A\cap B|[/inlmath], odnosno situacije u kojima ni medju studentima matematike ni medju studentima racunarskih nauka nema susjeda. Odmah rasporedimo studente fizike na [inlmath]3![/inlmath] nacina, pa imamo sljedecu situaciju [inlmath]\_X\_X\_X\_[/inlmath] . Biramo [inlmath]3[/inlmath] od potencijalna [inlmath]4[/inlmath] mjesta i na njih rasporedjujemo studente matematika, i na kraju studente racunarskih nauka rasporedjujemo kao kada smo trazili kardinalnost skupa [inlmath]A[/inlmath]. Sve to zajedno je [inlmath]3!\cdot{4\choose3}\cdot3!\cdot{7\choose3}\cdot3![/inlmath].

Zapravo, mogli smo sva tri studenta matematike da raspodelimo na samo dve, pa čak i na samo jednu poziciju, a da potom po jednog studenta računarske nauke umetnemo između dva studenta matematike koji su jedan do drugog, čime se postiže razdvajanje studenata matematike.