od Daniel » Utorak, 16. April 2019, 23:35
Formulu uključenja i isključenja koristimo kad računamo broj elemenata unije skupova koji nisu disjunktni, tj. imaju međusobne preseke. Npr. kad imamo skupove [inlmath]A[/inlmath], [inlmath]B[/inlmath] i [inlmath]C[/inlmath], prostim sabiranjem njihovih brojeva elemenata [inlmath]|A|+|B|+|C|[/inlmath] ne bismo dobili broj elemenata njihove unije, već bismo dobili veći broj, jer smo brojeve elemenata njihovih preseka, [inlmath]|A\cup B|[/inlmath], [inlmath]|B\cup C|[/inlmath] i [inlmath]|A\cup C|[/inlmath], računali dvaput, tako da sad treba oduzeti te brojeve. Međutim, pošto smo ovim oduzimanjem poništili broj elemenata preseka sva tri skupa, [inlmath]|A\cup B\cup C|[/inlmath], sada još treba dodati taj broj.
To je neka osnovna ideja formule uključenja i isključenja, a ovaj primer se odnosio na tri skupa. Naravno, broj skupova može biti proizvoljan.
Slično je i u ovom konkretnom zadatku, [inlmath]{n\choose1}(n-1)^k[/inlmath] ne predstavlja tačan broj slučajeva u kojima je bar jedna kutija prazna, jer neke slučajeve obuhvata i dvaput ili više puta. Npr. ako smo izabrali [inlmath]3.[/inlmath] kutiju da bude prazna, a onda se u jednom slučaju raspoređivanja desilo da bude prazna i [inlmath]5.[/inlmath] kutija, to će se računati kao jedan slučaj. Ali, ako smo izabrali [inlmath]5.[/inlmath] kutiju da bude prazna, a onda se u jednom slučaju raspoređivanja desilo da bude prazna i [inlmath]3.[/inlmath] kutija, to će se sad računati kao novi slučaj, što on zapravo nije, čime smo dobili jedan slučaj koji je računat dva puta, a samim tim i veći broj od stvarnog. Zbog toga smo, oduzimanjem ovog broja [inlmath]{n\choose1}(n-1)^k[/inlmath] od početnog [inlmath]n^k[/inlmath], oduzeli i veći broj slučaja nego što je trebalo, oduzeli smo dvaput umesto jednom sve one slučajeve u kojima se pojavljuju dve prazne kutije. Zato sad treba dodati broj [inlmath]{n\choose2}(n-2)^k[/inlmath], kojim su računati slučajevi s bar dve prazne kutije. Međutim, pošto i ovaj broj iz istog razloga predstavlja veći broj od stvarnog, onda je sad potrebno oduzeti [inlmath]{n\choose3}(n-3)^k[/inlmath]. Dakle, slično kao kod unija i preseka skupova.
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