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

Broj reči u rečniku – prijemni FON 2002.

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

Broj reči u rečniku – prijemni FON 2002.

Postod Nastasjaa » Četvrtak, 14. Jun 2018, 15:27

Rečnik sadrži sve reči od [inlmath]5[/inlmath] slova koje se mogu obrazovati od tri različita slova skupa [inlmath]\{A,B,C,D,E,F\}[/inlmath]. Ako je [inlmath]n[/inlmath] broj reči u tom rečniku, koliko iznosi [inlmath]n[/inlmath]?

Teško se snalazim sa kombinatorikom, problem mi je da uopšte krenem da sagledavam problem, da li bi neko mogao da mi pomogne?
 
Postovi: 7
Zahvalio se: 0 puta
Pohvaljen: 0 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Re: Broj reči u rečniku – prijemni FON 2002.

Postod Daniel » Četvrtak, 14. Jun 2018, 19:27

Tekst zadatka mi se čini prilično konfuzan i nisam siguran jesam li ga dobro razumeo, da li zaista tako glasi u originalu? Dakle, da li mi prvo iz skupa [inlmath]\{A,B,C,D,E,F\}[/inlmath] biramo tri različita slova (npr. [inlmath]A[/inlmath], [inlmath]D[/inlmath] i [inlmath]F[/inlmath]), a zatim od ta tri različita slova formiramo reči od pet slova (npr. [inlmath]AADAF[/inlmath], [inlmath]DAFFD[/inlmath], [inlmath]FAFDF[/inlmath] itd.)? Znači, ako sam dobro razumeo, svako od tri različita slova mora u svakoj reči biti bar jednom iskorišćeno, tj. nisu dozvoljene npr. reči [inlmath]AFAAF[/inlmath] ili [inlmath]DDDDD[/inlmath]?
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: Broj reči u rečniku – prijemni FON 2002.

Postod Daniel » Četvrtak, 14. Jun 2018, 19:55

Izguglah u međuvremenu taj zadatak, i zaista tako glasi. Mogli su baš malo preciznije da ga sroče. Mislim da je moja pretpostavka koju sam gore izneo tačna, jer radeći na taj način dobijem rezultat [inlmath]n=3000[/inlmath], što se uklapa u interval koji su naveli kao tačan, a koji glasi [inlmath]3000\le n<3500[/inlmath].

Haj'mo za početak, na koliko načina možemo iz skupa [inlmath]\{A,B,C,D,E,F\}[/inlmath] odabrati tri različita slova? To bi trebalo da znaš.
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: Broj reči u rečniku – prijemni FON 2002.

Postod diopo » Četvrtak, 14. Jun 2018, 20:28

Ja sam zbunjen takodje, zato nisam ni hteo da odgovorim da ne bih napravio zbrku, ali posle tvog odgovora moram da te pitam nesto.

Mozes li da objasnis sta ti je u tekstu dalo do znanja da svako slovo mora da bude upotrebljeno bar jednom, jer sam ga ja citao sto puta i i dalje me vuce da postoji mogucnost za reci tipa [inlmath]AAAAA[/inlmath], [inlmath]BBBBA[/inlmath], itd .. ? :/
diopo  OFFLINE
 
Postovi: 58
Zahvalio se: 35 puta
Pohvaljen: 18 puta

Re: Broj reči u rečniku – prijemni FON 2002.

Postod Daniel » Četvrtak, 14. Jun 2018, 20:38

To sam pretpostavio na osnovu ovog crveno obeleženog:
Nastasjaa je napisao:Rečnik sadrži sve reči od [inlmath]5[/inlmath] slova koje se mogu obrazovati od tri različita slova skupa [inlmath]\{A,B,C,D,E,F\}[/inlmath].

Ali, opet kažem, ne tvrdim sa stoprocentnom sigurnošću, jer je tekst zadatka bože sačuvaj. S ovom svojom pretpostavkom dobijam [inlmath]3000[/inlmath], što se uklapa u tačan rezultat, ali i kad bih uzeo u obzir i te primere koje si naveo, dobio bih [inlmath]3486[/inlmath], što se opet uklapa u interval koji je naveden kao tačan.
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: Broj reči u rečniku – prijemni FON 2002.

Postod piglet993 » Sreda, 13. April 2022, 18:17

Da li može neko da objasni ideju kako ovo treba da se reši?
 
Postovi: 1
Zahvalio se: 0 puta
Pohvaljen: 0 puta

  • +2

Re: Broj reči u rečniku – prijemni FON 2002.

Postod Mia » Petak, 24. Jun 2022, 19:23

Ja bih ovo radila tako sto prvo od [inlmath]6[/inlmath] ponudjenih slova izaberem [inlmath]3[/inlmath] to je moguće uraditi na [inlmath]20[/inlmath] načina zatim od svih mogućih slučajeva oduzmemo one gde su izostavljeni [inlmath]1[/inlmath] ili [inlmath]2[/inlmath] slova u formiranju reči odnosno
[dispmath]{6\choose3}\cdot\left(3^5-{3\choose2}\cdot2^5+3\right)[/dispmath] plus [inlmath]3[/inlmath] bih objasnila s tim da kad smo oduzeli
[dispmath]{3\choose2}\cdot2^5[/dispmath] mi smo ustvari [inlmath]2[/inlmath] puta oduzeli slucaj [inlmath]XXXXX[/inlmath], [inlmath]2[/inlmath] puta oduzeli slucaj [inlmath]ZZZZZ[/inlmath], [inlmath]2[/inlmath] puta oduzeli slucaj [inlmath]YYYYY[/inlmath] gde su [inlmath]x,y,z[/inlmath] prvo, drugo, trece izabrano slovo dakle [inlmath]3[/inlmath] od tih [inlmath]6[/inlmath] nam je visak zato plus [inlmath]3[/inlmath]. Nadam se da je tacno i razumljivo :D
Mia  OFFLINE
 
Postovi: 4
Zahvalio se: 2 puta
Pohvaljen: 4 puta

Re: Broj reči u rečniku – prijemni FON 2002.

Postod Daniel » Subota, 25. Jun 2022, 14:43

Mia je napisao:mi smo ustvari [inlmath]2[/inlmath] puta oduzeli slucaj [inlmath]XXXXX[/inlmath], [inlmath]2[/inlmath] puta oduzeli slucaj [inlmath]ZZZZZ[/inlmath], [inlmath]2[/inlmath] puta oduzeli slucaj [inlmath]YYYYY[/inlmath] gde su [inlmath]x,y,z[/inlmath] prvo, drugo, trece izabrano slovo dakle [inlmath]3[/inlmath] od tih [inlmath]6[/inlmath] nam je visak zato plus [inlmath]3[/inlmath].

Tako je, to se zove princip uključenja i isključenja.
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: Broj reči u rečniku – prijemni FON 2002.

Postod nadja » Utorak, 02. Avgust 2022, 13:49

Pozdrav svima, evo kako sam ja razmišljala:
Dakle, kao što ste već rekli, od skupa [inlmath]\{A,B,C,D,E,F\}[/inlmath] se mogu načiniti [inlmath]{6\choose 3} = 20[/inlmath] podskupa od 3 elementa.
E sad, da bih izračunala koliko riječi možemo napraviti od ta 3 elementa koristila sam onu formulu za izračunavanje n-varijacija tipa
[inlmath](k_1,k_2...,k_m)[/inlmath] pri čemu je [inlmath]k_1 + k_2 + .... +k_m = n[/inlmath] koja glasi [dispmath]\frac{n!}{k_1!k_2!\cdots k_m!}[/dispmath]
Znači, uzmimo samo za primjer podskup [inlmath]\{A,B,C\}[/inlmath].
Prvi tip je [inlmath](5,0,0)[/inlmath], tj. [inlmath]A[/inlmath] se ponavlja 5 puta. Takvih varijacija ima [inlmath]\frac{5!}{5!} = 1[/inlmath]. S obzirom da ovu peticu gore možemo rasporediti na 3 načina (tj. imamo još tipove [inlmath](0,5,0)[/inlmath]-> B se ponavlja 5 puta i [inlmath](0,0,5)[/inlmath]-> C se ponavlja 5 puta), riječi gdje se svako slovo pojavljuje 5 puta [inlmath](AAAAA,\enspace BBBBB,\enspace CCCCC[/inlmath]) je 3.

Hajdemo dalje:
Sljedeći tip je [inlmath](1,4,0)[/inlmath]-> [inlmath]A[/inlmath] se pojavljuje 1, a [inlmath]B[/inlmath] 4 puta. Takvih rasporeda ima [inlmath]\frac{5!}{1!4!}=5[/inlmath]. S obzirom da gore navedenu jedinicu i četvorku možemo rasporediti na [inlmath]3!=6[/inlmath] načina(tj. imamo još ove tipove: (4,1,0), (1,0,4), (4,0,1) i sve ostale moguće varijacije), a za svaki tip imamo 5 riječi, ukupno imamo [inlmath]5\cdot6=30[/inlmath] riječi gdje se 1 slovo ponavlja 4 puta, drugo se pojavljuje samo jednom, a treće se uopšte ne pojavljuje.

Sljedeći tip je [inlmath](2,3,0)[/inlmath]. Ovakvih riječi imamo [inlmath]\frac{5!}{2!3!}=10[/inlmath]. Pošto ovakvih tipova (sa 2 i 3) imamo ukupno [inlmath]3!=6[/inlmath]. Imamo [inlmath]6\cdot10=60[/inlmath] ovakvih riječi.

Sljedeći tip je [inlmath](1,1,3)[/inlmath]. Ovakvih riječi je [inlmath]\frac{5!}{1!1!3!}=20[/inlmath]. Ovakih tipova(sa 2 jedinice i tricom) ima [inlmath]{3\choose1}=3[/inlmath]. Znači, ovakvih riječi imamo [inlmath]3\cdot20=60[/inlmath]

I ostao nam je još samo jedan tip [inlmath](1,2,2)[/inlmath]. Ovakvih riječi je [inlmath]\frac{5!}{1!2!2!}=30[/inlmath]. Ovakvih tipova (sa jedinicom i 2 dvice) ima [inlmath]{3\choose1}=3[/inlmath](tj. pored prve varijacije imamo još:[inlmath](2,1,2), (2,2,1)[/inlmath]). Znači ukupno ih ima: [inlmath]3\cdot30=90[/inlmath]

E sad dolazimo do najvažnijeg dijela: rezultata.
Ako se ne moraju sva slova iz podskupa pojaviti u riječi, onda ih imamo: [dispmath]20\cdot(90+60+60+30)=4800[/dispmath]
Ako to nije dozvoljno, onda imamo(kao što je Mia čini mi se izračunala): [dispmath]20\cdot(90+60)=3000[/dispmath]

Znam da je malo konfuzno, tako da me slobodno pitajte ako vam šta nije jasno, potrudiću se da što prije odgovorim. Pozdrav!
nadja  OFFLINE
 
Postovi: 6
Zahvalio se: 5 puta
Pohvaljen: 1 puta


Povratak na KOMBINATORIKA

Ko je OnLine

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


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