MATEMANIJA

Koliko ima permutacija [inlmath](a_1,a_2,\ldots,a_n)[/inlmath] skupa [inlmath](1,2,\ldots,n)[/inlmath] takvih da ni jedan od elemenata [inlmath]a_1,a_2,\ldots,a_n[/inlmath] nije "na svom mestu" tj, takvih da za svako [inlmath]i\in(1,2,\ldots,n)[/inlmath] vazi da [inlmath]a_i\ne i[/inlmath]?
Odgovor:

[inlmath]A)\;n!-(n-1)!+(n-2)!-\cdots(-1)^n(n-n)![/inlmath]

[inlmath]B)\;(n-1)!-(n-2)!+\cdots+(-1)^{n-1}(n-n)![/inlmath]

[inlmath]C)\;n!-{n\choose1}(n-1)!+{n\choose2}(n-2)!-\cdots+(-1)^n{n\choose n}(n-n)![/inlmath]

[inlmath]D)\;{n\choose1}(n-1)!+{n\choose2}(n-2)!+\cdots+{n\choose n}(n-n)![/inlmath]

[inlmath]E)\;{n\choose1}(n-1)!-{n\choose2}(n-2)!+\cdots+(-1)^{n-1}{n\choose n}(n-n)![/inlmath]

E sad sto se tice ovog zadatka, ja uopste ni ne znam sta se trazi od mene.
Kako "nije na svom mestu"?
Pitao sam i rekli su mi da koristim neku metodu vezanu samo za tu oblast.
Ali mi niti smo to u srednjoj radili niti pomenuli, a zadatak je stavljen medju prvih nekoliko iz kombinatorike sto znaci da je jednostavniji, pa moze li neko objasnjenje za postupak?

Prvo, što se tiče obeležavanja. Skup se ne obeležava [inlmath](1,2,\ldots,n)[/inlmath], već [inlmath]\{1,2,\ldots,n\}[/inlmath] (vitičaste zagrade). O tome više možeš pročitati ovde. Oblim zagradama se predstavljaju uređene [inlmath]n[/inlmath]-torke elemenata (kod kojih je redosled bitan). Zbog toga su upravo za obeležavanje permutacija [inlmath](a_1,a_2,\ldots,a_n)[/inlmath] i korišćene oble zagrade, jer kod permutacija redosled jeste bitan.

U tekstu je objašnjeno šta znači da element u nekoj permutaciji nije „na svom mestu“. To znači da tražimo takve permutacije u kojoj nit je jedinica na prvom mestu, nit je dvojka na drugom mestu, nit je trojka na trećem mestu... nit je [inlmath]n[/inlmath] na [inlmath]n[/inlmath]-tom mestu. Npr. za skup gde je [inlmath]n=5[/inlmath], neke od permutacija koje ne bismo uzimali u razmatranje bile bi [inlmath]32451[/inlmath] (jer je dvojka na drugom mestu), ili [inlmath]41325[/inlmath] (jer su trojka i petica na svojim mestima)... U razmatranje bismo npr. uzeli permutaciju [inlmath]35124[/inlmath], jer u njoj nijedan element nije na svom mestu (trojka je na prvom, petica na drugom...)

Ako hoćeš da rešiš zadatak „na kvarno“ (bez regularnog postupka), možeš jednostavnim uvrštavanjem [inlmath]n=2[/inlmath] i [inlmath]n=3[/inlmath], sistemom eliminacije, doći do tačnog odgovora (lako se prebroji koliko imamo željenih permutacija za slučajeve od [inlmath]2[/inlmath] i od [inlmath]3[/inlmath] elementa, i to se uporedi s ponuđenim odgovorima).

Ako ne želiš da rešiš „na kvarno“ već želiš da proučiš postupak (što se iskreno nadam ), ovaj zadatak je potpuno analogan s problemom trapavog konobara koji izmeša narudžbine od [inlmath]n[/inlmath] ljudi za istim stolom (koji su svi naručili različita jela) i onda se postavlja pitanje na koliko načina im može servirati jela tako da niko ne dobije ono što je naručio. E upravo taj zadatak smo imali u ovoj temi, pa možeš pogledati postupak. Radi se preko formule uključivanja i isključivanja (FUI).

markonikolic23 je napisao:a zadatak je stavljen medju prvih nekoliko iz kombinatorike sto znaci da je jednostavniji,

Daleko od toga da je ovaj zadatak među jednostavnijima.

Hvala puno na detaljnom i vrlo jasnom objasnjenju, vrlo lako sam na kraju resio. Sve pohvale za odgovor!