MATEMANIJA

Odrediti broj permutacija brojeva [inlmath]1,2,3,4,5,6,7,8,9,10[/inlmath] tako da [inlmath]i+1[/inlmath] ne bude neposredno nakon [inlmath]i[/inlmath] za svako [inlmath]i[/inlmath] iz skupa [inlmath]\{1,2,3,4,5,6,7,8,9\}[/inlmath].

Od [inlmath]10![/inlmath] trebam oduzeti sve permutacije kada postoje dva neka uzastopna broja, postoji [inlmath]9[/inlmath] parova brojeva koji nisu dozvoljeni i to su: [inlmath](1,2)[/inlmath] [inlmath](2,3)[/inlmath] [inlmath](3,4)[/inlmath] [inlmath](4,5)[/inlmath] [inlmath](5,6)[/inlmath] [inlmath](6,7)[/inlmath] [inlmath](7,8)[/inlmath] [inlmath](8,9)[/inlmath] [inlmath](9,10)[/inlmath]

Sada bih vjerovatno ovaj jedan par mogao posmatrati kao jedan broj i od [inlmath]10![/inlmath] oduzimati sve mogucnosti kada su dva uzastopna broja jedan pored drugog, medjutim problem nastaje jer moze biti [inlmath]1,2,3[/inlmath] i [inlmath]1,2,5,6[/inlmath] u oba slucaja imam [inlmath]2[/inlmath] ova uredjena para ali u jednom slucaju sam iskoristio [inlmath]3[/inlmath] elementa za [inlmath]1,2[/inlmath] i [inlmath]2,3[/inlmath] a u drugom slucaju [inlmath]4[/inlmath]

Ispravno ti je razmišljanje. Upravo zbog svega što si naveo, ovde treba upotrebiti FUI (formulu uključivanja i isključivanja).

[inlmath]10!-(9\cdot9!-36\cdot7!-168\cdot6!-756\cdot5!-\cdots-1)[/inlmath] ovako bi mi izgledalo logicno jer u prvom slucaju izaberem jedan uredjeni par koji nije dozvoljen i vrstim permutacije ostalih ne gledajuci da li ce se opet pojaviti negdje nedozvoljeni par, ali s obzirom da ne vodim racuna o tome i zbog svih mogucih dupliranja trebao bih oduzeti (tj dodati ukupnom rezultatu) slucajeve kada se pojavljuju [inlmath]2,3,4,\ldots[/inlmath] uredjenih parova... medjutim buni me dio gdje [inlmath]2[/inlmath] uredjena para mogu biti sacinjeni od [inlmath]3[/inlmath] i od [inlmath]4[/inlmath] elementa u zavisnosti od rasporeda.

Sinisa je napisao:[inlmath]10!-(9\cdot9!-36\cdot7!-168\cdot6!-756\cdot5!-\cdots-1)[/inlmath]

Blizu si, ali obrati pažnju na znake, ne treba svuda da budu minusi (kod FUI minusi i plusevi idu naizmenično).
Takođe, ispustio si [inlmath]8![/inlmath].
Činioci [inlmath]9[/inlmath] i [inlmath]36[/inlmath] su ti u redu, ali [inlmath]168[/inlmath] i [inlmath]756[/inlmath] ti ne valjaju, proveri da nisi napravio grešku u računu.

Sinisa je napisao:medjutim buni me dio gdje [inlmath]2[/inlmath] uredjena para mogu biti sacinjeni od [inlmath]3[/inlmath] i od [inlmath]4[/inlmath] elementa u zavisnosti od rasporeda.

Ako sam te dobro razumeo, buni te npr. razlika između slučaja [inlmath]5,8,{\color{red}3,4},9,2,10,{\color{red}6,7},1[/inlmath] i slučaja [inlmath]8,2,1,3,10,{\color{red}4,5,6},9,7[/inlmath]. Možeš uočiti da i u jednom i u drugom slučaju možeš taj skup tretirati kao skup od [inlmath]8[/inlmath] elemenata (u prvom se [inlmath]3[/inlmath] i [inlmath]4[/inlmath] posmatraju kao jedan element, [inlmath]6[/inlmath] i [inlmath]7[/inlmath] se posmatraju kao drugi element i ima još [inlmath]6[/inlmath] elemenata, dok se u drugom [inlmath]4[/inlmath], [inlmath]5[/inlmath] i [inlmath]6[/inlmath] posmatraju kao jedan element i ima još [inlmath]7[/inlmath] elemenata). U oba slučaja ukupno [inlmath]8[/inlmath] elemenata, tako da ne moraš praviti razliku između ova dva slučaja.

I, hajmo onda da ovo i privedemo kraju.
Od ukupnog broja permutacija ([inlmath]10![/inlmath]) treba oduzeti broj onih s uzastopnim brojevima. Od [inlmath]10![/inlmath] oduzimamo [inlmath]{9\choose1}9![/inlmath] (par uzastopnih možemo odabrati na [inlmath]9\choose1[/inlmath] načina i posmatramo ga kao jedan element, tako da imamo [inlmath]9![/inlmath] načina za raspoređivanje [inlmath]9[/inlmath] elemenata). Međutim, ovime smo od [inlmath]10![/inlmath] oduzeli više nego što treba, jer smo dvaput obuhvatili one permutacije kod kojih se pojavljuju dva para uzastopnih brojeva (npr. pri posmatranju [inlmath]3[/inlmath] i [inlmath]4[/inlmath] jedan do drugog obuhvatili smo i slučaj kad su [inlmath]3[/inlmath] i [inlmath]4[/inlmath] jedan do drugog i npr. [inlmath]6[/inlmath] i [inlmath]7[/inlmath] jedan do drugog, ali ćemo istu tu permutaciju obuhvatiti i kad posmatramo [inlmath]6[/inlmath] i [inlmath]7[/inlmath] jedan do drugog). Zato sada, da bismo to kompenzovali, treba na dosadašnji rezultat dodati broj onih permutacija koje sadrže dva para uzastopnih brojeva, tj. na [inlmath]10!-{9\choose1}9![/inlmath] dodajemo [inlmath]{9\choose2}8![/inlmath] (na [inlmath]9\choose2[/inlmath] načina možemo odabrati dva para uzastopnih brojeva, nakon čega svaki od ta dva para posmatramo kao jedan element, a broj permutacija ukupno [inlmath]8[/inlmath] elemenata je [inlmath]8![/inlmath]). Međutim, sad smo ovime dodali više nego što treba, pa treba oduzeti... itd...
To je princip uključenja i isključenja.
Konačan odgovor treba da glasi
[dispmath]10!-{9\choose1}9!+{9\choose2}8!-{9\choose3}7!+{9\choose4}6!-{9\choose5}5!+{9\choose6}4!-{9\choose7}3!+{9\choose8}2!-{9\choose9}[/dispmath] što se može zapisati u obliku sume,
[dispmath]\sum_{k=0}^9(-1)^k{9\choose k}(10-k)![/dispmath] Za neki uopšten slučaj, kada imamo skup [inlmath]\{1,2,3,\ldots,n-1,n\}[/inlmath] a traži se broj permutacija kao u ovom zadatku, rešenje bi bilo
[dispmath]\sum_{k=0}^{n-1}(-1)^k{n-1\choose k}(n-k)![/dispmath]

Daniel je napisao:

Sinisa je napisao:[inlmath]10!-(9\cdot9!-36\cdot7!-168\cdot6!-756\cdot5!-\cdots-1)[/inlmath]

Blizu si, ali obrati pažnju na znake, ne treba svuda da budu minusi (kod FUI minusi i plusevi idu naizmenično).

Ako i dalje postoji zabuna zbog čega minusi i plusevi idu naizmenično, možda je očiglednije ako se [inlmath]10!-9\cdot9!+36\cdot8!-84\cdot7!+\cdots+9\cdot2!-1[/inlmath] napiše kao [inlmath]10!-\biggl(9\cdot9!-\Bigl(36\cdot8!-\bigl(84\cdot7!-\cdots-(9\cdot2!-1)\cdots\bigr)\Bigr)\biggr)[/inlmath].