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 KOMBINATORIKA

Permutacije u kojima nijedan element nije na svom mestu

[inlmath]{n\choose k}=\frac{n!}{\left(n-k\right)!k!}[/inlmath]

Permutacije u kojima nijedan element nije na svom mestu

Postod markonikolic23 » Ponedeljak, 29. Mart 2021, 14:59

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?
 
Postovi: 24
Zahvalio se: 11 puta
Pohvaljen: 1 puta

Sharuj ovu temu na:

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

Re: Permutacije u kojima nijedan element nije na svom mestu

Postod Daniel » Utorak, 30. Mart 2021, 23:18

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.
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: Permutacije u kojima nijedan element nije na svom mestu

Postod markonikolic23 » Petak, 02. April 2021, 22:14

Hvala puno na detaljnom i vrlo jasnom objasnjenju, vrlo lako sam na kraju resio. Sve pohvale za odgovor!
 
Postovi: 24
Zahvalio se: 11 puta
Pohvaljen: 1 puta


Povratak na KOMBINATORIKA

Ko je OnLine

Korisnici koji su trenutno na forumu: Google [Bot] i 35 gostiju


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