Zadaci s kuglicama

[kiko1804]

Imamo 12 kuglica crvene boje, 14 kuglica zute boje, 16 kuglica plave boje i 18 kuglica zelene boje. Na koliko nacina navedene kuglice mozemo razvrstati u 5 kutija?

[Optimum]

Kuglice crvene boje možemo prvo razvrstati na [tex]{12+4 \choose 4}[/tex] načina.
Kuglice žute boje na [tex]{14+4 \choose 4}[/tex] načina.
itd itd...

Na kraju je rješenje:
[tex]{12+4 \choose 4}\cdot {14+4 \choose 4} \cdot {16+4 \choose 4} \cdot {18+4 \choose 4}[/tex].

[kiko1804]

[Optimum]

OK. Preko multiskupova:

Imamo multiskup: [tex]S=\{C^{12}, Z^{14}, P^{16}, L^{18}\}[/tex]
Sveukupno očito imamo 60 kuglica.
Njih na 5 kutija možemo dijeliti ovako:
Prvu od 60 možemo staviti u bilo koju od 5 kutija.
Drugu od 60 kuglica možemo staviti u bilo koju od 5 kutija.
...
...
Zadnju od 60 kuglica možemo staviti u bilo koju od 5 kutija.
Očito je raspred kuglica u kutije: [tex]5^{60}[/tex].
Ali, pošto imamo 12 istih (koje ne razlikujemo) crvenih kuglica, 14 istih žutih, ... itd... moramo podijeliti s brojem mogućih premutacija svih crvenih kuglica, brojem permutacija svih žutih kuglica itd... jer mi međusobno crvene kuglice ne razlikujemo!

Konačno: [dtex]\frac{5^{60}}{12!\cdot14!\cdot16!\cdot18!}[/dtex].

[kiko1804]

Ok, meni treba ovo prvo što si rješio..al me zanima zašto npr. crvene kuglice možemo razvrstati baš na 12+4 povrh 4 načina..zašto zbrajam 12 i 4 i onda povrh 4?? Hvala!

[Optimum]

Preporučujem ti da objašnjenje toga potražiš u skipti "Vježbe iz diskretne matematike" od asistenta Bašića.
To je primjer 3.5. koji taj problem objašnjava tako da:

Jednostavno zapamtiš formulu da [tex]m[/tex] kuglica u [tex]n[/tex] kutija možeš rasporediti na [tex]{m+n-1 \choose m}[/tex] načina.

Zašto? (Kratko objašnjenje) Zamisli da umjesto [tex]n[/tex] kutija stavimo [tex]n-1[/tex] štapić... svaki prostor između dva štapića predstavlja jednu kutiju... prostor prije prvog štapića je prva kutija, prostor između prvog i drugog štapića je druga kutija itd... prostor iza zadnjeg štapića je n-ta kutija.
Kuglice su jednake, ne razlikujemo ih!
Pošto kuglice ne razlikujemo, sve ih poredamo u jedan red. Sada odlučimo postavljati štapiće između njih... pošto imamo [tex]n-1[/tex] štapić i [tex]m[/tex] kuglica, sveukupno imamo [tex]m+n-1[/tex] pozicija, a nama je dovoljno da samo štapiće raspoređujemo.
Zapostavu tih [tex]n-1[/tex] štapića imamo:
[tex]{m+n-1 \choose n-1}[/tex]
mogućih načina za kombinirati.
Primjeti da vrijedi: [tex]{m+n-1 \choose n-1} = {m+n-1 \choose m}[/tex]