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

Kuglice i kutije

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

Kuglice i kutije

Postod diopo » Utorak, 16. April 2019, 16:29

Na koliko razlicitih nacina se [inlmath]15[/inlmath] razlicitih kuglica mogu rasporediti u [inlmath]10[/inlmath] razlicitih kutija tako da tacno [inlmath]3[/inlmath] kutije budu prazne?

Izracunam na koliko nacina mogu da od [inlmath]10[/inlmath] kutija odaberem [inlmath]3[/inlmath] koje ce biti prazne i problem se sada svodi na to kako da [inlmath]15[/inlmath] kuglica rasporedim u [inlmath]7[/inlmath] kutija tako da ni jedna kutija ne bude prazna... ako moze pomoc
diopo  OFFLINE
 
Postovi: 58
Zahvalio se: 35 puta
Pohvaljen: 18 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+
  • +1

Re: Kuglice i kutije

Postod Daniel » Utorak, 16. April 2019, 16:33

Evo pomoć ovde :) – kombinuj razmišljanje pod a) i pod b).
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: Kuglice i kutije

Postod diopo » Utorak, 16. April 2019, 17:00

Ne znam koliko je slicno posto su u tom zadatku identicni elementi, ovde su kuglice razlicite. U svakom slucaju, [inlmath]3[/inlmath] kutije koje ce biti prazne mogu da odaberem na [inlmath]10\choose3[/inlmath] nacina. Ostaje mi [inlmath]7[/inlmath] kutija i [inlmath]15[/inlmath] razlicitih kuglica koje moram da rasporedim u te kutije, ali tako da ni jedna kutija ne bude prazna, eh sad, ne pada mi nista bolje na pamet nego da za pocetak u svaku kutiju stavim po jednu kuglicu, da bih zadovoljio taj uslov. Treba da odaberem [inlmath]7[/inlmath] kuglica i to mogu na [inlmath]15\choose7[/inlmath] nacina. Sada sam sve kutije popunio po jednom kuglicom, medjutim kuglice su razlicite, te mogu da permutuju pa je zapravo broj mogucnosti [inlmath]{15\choose7}\cdot7![/inlmath]... bas mi se ne dopada ova logika i ne znam kako dalje .. :/
diopo  OFFLINE
 
Postovi: 58
Zahvalio se: 35 puta
Pohvaljen: 18 puta

  • +2

Re: Kuglice i kutije

Postod Daniel » Utorak, 16. April 2019, 21:38

Sorry, prevideh to različite, čitah na brzinu (što svakako nije opravdanje).
Svakako prvo treba odabrati tri kutije koje će biti prazne (što si već učinio). Zatim tih [inlmath]15[/inlmath] različitih kuglica treba rasporediti u preostalih [inlmath]7[/inlmath] kutija, što je identično problemu u kojem svaku od [inlmath]15[/inlmath] različitih kuglica treba numerisati nekim brojem od [inlmath]1[/inlmath] do [inlmath]7[/inlmath] (zavisno od toga u koju kutiju je ubacujemo), pri čemu svih sedam brojeva moraju biti iskorišćeni (jer nijedna od tih [inlmath]7[/inlmath] kutija ne sme biti prazna). Tu moramo koristiti formulu uključenja i isključenja: broj načina raspoređivanja različitih kuglica pri čemu kutije smeju biti i prazne iznosi [inlmath]n^k[/inlmath], gde je [inlmath]n[/inlmath] broj kutija a [inlmath]k[/inlmath] broj kuglica (u našem slučaju [inlmath]n=7[/inlmath] i [inlmath]k=15[/inlmath]). Zatim od tog broja treba oduzeti broj načina s jednom praznom kutijom, [inlmath]{n\choose1}(n-1)^k[/inlmath]. Zatim tom broju dodajemo broj načina s dve prazne kutije, [inlmath]{n\choose2}(n-2)^k[/inlmath]. Zatim od tog broja treba oduzeti broj načina s tri prazne kutije, [inlmath]{n\choose3}(n-3)^k[/inlmath] itd. dok se ne dođe do slučaja sa [inlmath]n-1[/inlmath] praznih kutija, pri čemu se dodaje [inlmath](-1)^{n-1}{n\choose n-1}1^k[/inlmath]. To jest,
[dispmath]\sum_{i=0}^{n-1}(-1)^i{n\choose i}(n-i)^k[/dispmath] i to onda, naravno, još pomnožiš brojem mogućih odabira [inlmath]3[/inlmath] prazne kutije, a što si uradio još na početku...
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: Kuglice i kutije

Postod diopo » Utorak, 16. April 2019, 22:02

Hmm, okej, jasno mi je do principa ukljucenja i iskljucenja... na osnovu cega znam da treba to da iskoristim?
diopo  OFFLINE
 
Postovi: 58
Zahvalio se: 35 puta
Pohvaljen: 18 puta

Re: Kuglice i kutije

Postod 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
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta


Povratak na KOMBINATORIKA

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 31 gostiju

cron

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