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].