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 svih permutacija slova reči MOSKVA, Prijemni ispit iz matematike FON 2016, 20. zadatak

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

Broj svih permutacija slova reči MOSKVA, Prijemni ispit iz matematike FON 2016, 20. zadatak

Postod bobanex » Subota, 24. Jun 2017, 21:24

Broj permutacija slova reči [inlmath]MOSKVA[/inlmath] kod kojih se između dva samoglasnika nalazi bar jedan suglasnik jednak je?
Rešenje je [inlmath]480[/inlmath].
(LINK)
Neko me je pitao za rešenje ovog zadatka. Navešću svoj odgovor a očekujem da mi neko potvrdi ispravnost ili da navede svoj način rada.

Ukupan broj permutacija od [inlmath]6[/inlmath] elemenata iznosi [inlmath]6!=720[/inlmath].
Od toga treba odbiti broj permutacija kod kojih se između dva samoglasnika ne nalazi ni jedan suglasnik, što će reći da se samoglasnici nalaze jedan pored drugog.
Samoglasnici se jedan pored drugog mogu naći na [inlmath]10[/inlmath] načina ([inlmath]AO****[/inlmath], [inlmath]OA****[/inlmath], [inlmath]*AO***[/inlmath], [inlmath]*OA***[/inlmath], ...). Preostala [inlmath]4[/inlmath] slova se mogu permutovati na [inlmath]4!=24[/inlmath] načina.
Broj traženih permutacija iznosi [inlmath]720-10\cdot24=480[/inlmath].
bobanex  OFFLINE
BANOVAN
 
Postovi: 523
Zahvalio se: 0 puta
Pohvaljen: 505 puta

Sharuj ovu temu na:

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

Re: Broj svih permutacija slova reči MOSKVA, Prijemni ispit iz matematike FON 2016, 20. zadatak

Postod Nađa » Subota, 24. Jun 2017, 21:35

Ja sam na slican nacin resila zadatak isto sam od ukupnog broja permutacija oduzela tamo gde se ne nalazi bar jedan suglasnik, medjutim taj drugi deo sam malo drugacije zapisala. Naime permutacija reci [inlmath]MOSKVA[/inlmath] gde su dva samoglasnika jedan pored drugog je [inlmath]2!\cdot5![/inlmath] sto predstavlja broj permutacija [inlmath]4[/inlmath] suglasnika i bloka sastavljenog od [inlmath]2[/inlmath] samoglasnika, gde se unutar bloka samoglasnici mogu rasporediti na [inlmath]2![/inlmath] nacina. Mislim kazem slican je postupak da ne kazem isti :) tako da eto potvrde od mene, mada nesto i nisam pametna :D
Nađa  OFFLINE
 
Postovi: 255
Zahvalio se: 137 puta
Pohvaljen: 108 puta

  • +1

Re: Broj svih permutacija slova reči MOSKVA, Prijemni ispit iz matematike FON 2016, 20. zadatak

Postod Daniel » Subota, 01. Jul 2017, 23:20

Ja bih isto radio kao Nađa, mislim da je tako najbrže. Znači, nađemo broj permutacija u kojima prvo [inlmath]OA[/inlmath], a zatim [inlmath]AO[/inlmath], posmatramo kao jedan element (što će reći, ukupno [inlmath]5[/inlmath] elemenata), a zatim to oduzmemo od broja ukupnih permutacija.

E sad, ako ova tema predstavlja poziv da smislimo najrazličitije načine rešavanja ovog zadatka (a ja upravo i volim kombinatoriku zato što se jedan isti problem može rešiti na gomilu načina), evo i od mene jednog, ne tako brzog i jednostavnog kao prethodna dva, al' čisto kao neka fiskultura za vijuge. A i kao još jedna potvrda dobijenog rezultata, koji iznosi [inlmath]480[/inlmath].

Posmatrao bih malo opštiji slučaj, da imamo [inlmath]k[/inlmath] slova u kojem dva slova (pretpostavimo bez umanjenja opštosti da su to slova [inlmath]A[/inlmath] i [inlmath]B[/inlmath]) ne smeju biti jedno pored drugog (odatle će se uvrštavanjem [inlmath]k=6[/inlmath] u rezultat lako dobiti rezultat i za naš konkretan slučaj). Posmatraćemo prvo slučajeve u kojima se [inlmath]A[/inlmath] pojavljuje pre [inlmath]B[/inlmath]. Tada se [inlmath]A[/inlmath] sme naći na pozicijama [inlmath]1,2,3,\ldots,k-2.[/inlmath] Na [inlmath](k-1).[/inlmath] poziciji se ne sme naći, jer bi onda [inlmath]B[/inlmath] moralo biti na [inlmath]k[/inlmath]-toj poziciji pa bi [inlmath]A[/inlmath] i [inlmath]B[/inlmath] bili jedno pored drugog.
  • Ako se [inlmath]A[/inlmath] nađe na [inlmath]1.[/inlmath] poziciji, za [inlmath]B[/inlmath] preostaje neka od pozicija [inlmath]3,4,\ldots,k[/inlmath] (ukupno [inlmath]k-2[/inlmath] pozicija).
  • Ako se [inlmath]A[/inlmath] nađe na [inlmath]2.[/inlmath] poziciji, za [inlmath]B[/inlmath] preostaje neka od pozicija [inlmath]4,5,\ldots,k[/inlmath] (ukupno [inlmath]k-3[/inlmath] pozicija).
  • Ako se [inlmath]A[/inlmath] nađe na [inlmath]3.[/inlmath] poziciji, za [inlmath]B[/inlmath] preostaje neka od pozicija [inlmath]5,6,\ldots,k[/inlmath] (ukupno [inlmath]k-4[/inlmath] pozicija).
    [inlmath]\vdots[/inlmath]
  • Ako se [inlmath]A[/inlmath] nađe na [inlmath](k-3).[/inlmath] poziciji, za [inlmath]B[/inlmath] preostaje neka od pozicija [inlmath]k-1[/inlmath] ili [inlmath]k[/inlmath] (ukupno [inlmath]2[/inlmath] pozicije).
  • Ako se [inlmath]A[/inlmath] nađe na [inlmath](k-2).[/inlmath] poziciji, za [inlmath]B[/inlmath] preostaje pozicija [inlmath]k[/inlmath] (ukupno [inlmath]1[/inlmath] pozicija).
Odatle sledi ukupan broj mogućnosti raspoređivanja slova [inlmath]A[/inlmath] i [inlmath]B[/inlmath] (takvih da se [inlmath]A[/inlmath] pojavljuje pre [inlmath]B[/inlmath]), a koji iznosi
[dispmath]1+2+3+\cdots+(k-3)+(k-2)[/dispmath] što je suma aritmetičkog niza i ona iznosi
[dispmath]\frac{k-2}{2}(1+k-2)=\frac{(k-1)(k-2)}{2}[/dispmath] Ako sada isti postupak primenimo i na slučajeve u kojima se prvo pojavljuje [inlmath]B[/inlmath] pa zatim [inlmath]A[/inlmath], dobićemo, sasvim logično, isti broj slučajeva, tako da će ukupan broj mogućnosti raspoređivanja [inlmath]A[/inlmath] i [inlmath]B[/inlmath], bez obzira na njihov međusobni redosled, iznositi [inlmath](k-1)(k-2)[/inlmath].
Ostalo je još da to pomnožimo brojem mogućnosti raspoređivanja preostalih [inlmath]k-2[/inlmath] elemenata, a to je [inlmath](k-2)![/inlmath] (permutacije bez ponavljanja).
Dakle, ukupan broj ovakvih slučajeva iznosi
[dispmath](k-1)(k-2)(k-2)!=(k-2)(k-1)![/dispmath] Uvrštavanjem [inlmath]k=6[/inlmath] dobijamo i rešenje za naš slučaj,
[dispmath]4\cdot5!=480[/dispmath]
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 35 gostiju


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