MATEMANIJA

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].

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

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]