Permutacije i kombinacije

Permutacije i kombinacije su tema koju traži svatko tko želi brzo i točno brojati moguće ishode bez dugog nabrajanja.

Permutacije broje uređene rasporede (bitan je redoslijed), npr. mjesta u klupi; kombinacije broje odabire bez reda, npr. sastav odbora. Računaju se pomoću faktora (n!), varijacija i binomnih koeficijenata (binom{n}{k}). Tako rješavamo zadatke lutrije, rasporeda i planiranja puno brže i sigurnije.

Ako ovo zvuči korisno, vrijedi vidjeti nekoliko kratkih primjera iz svakodnevice.

Temeljne ideje prebrojavanja u kombinatorici

Brojanje u kombinatorici zvuči suho, kao nešto iz sredine udžbenika koje svi preskaču. A zapravo je to alat koji ti spašava živce svaki put kad bi inače morao “nabrajati mogućnosti do sutra”.

U praksi? To je ono kad pokušavaš shvatiti:

• kolika je šansa da dobiješ na lotu
• koliko je mogućih poker ruku iz špila
• na koliko se načina može složiti raspored prezentacija u razredu

…a nema šanse da sve ručno pobrojiš.

—

Prva stvar: *što* uopće brojiš?

Tu mnogi krenu krivo. Da bi išta brojao, moraš si precizno postaviti scenu:

• Koji je skup elemenata? Karte? Ljudi? Brojevi od 1 do 49?
• Što točno čini “jednu mogućnost”? Ruka od 5 karata? Raspored 3 učenika u 3 stolice? Kombinacija brojeva na listiću?

Kad jednom znaš *što* je jedna mogućnost, tek onda ima smisla pitati “koliko ih je?”.

—

Ključno pitanje: igra li ulogu redoslijed?

Ovo je ona točka gdje pola razreda na natjecanjima iz matematike padne.

Pitaj se:

– Ako zamijenim mjesta dvama elementima, je li to nova mogućnost ili ista stara, samo drugačije zapisana?

Primjer iz života:

• Sastavljaš tim od 5 ljudi iz razreda od 20. Tko je u timu je važno, ali nije važno tko je “prvi”, “drugi” i tako dalje. Redoslijed ne igra ulogu.
• Dijeliš tri nagrade: prvo, drugo i treće mjesto. Isti troje ljudi, ali drugačiji poredak? To je nova mogućnost, jer je postalo važno *tko* je prvi, tko je drugi.

Tu se lome stvari: čim redoslijed igra ulogu, ulaziš u svijet permutacija i varijacija. Kad ne igra, to su kombinacije.

—

Permutacije: kad je raspored bitan

Permutacije su ti kao slaganje ljudi u red za fotografiranje. Ista ekipa, drugi raspored — potpuno nova situacija.

Primjer:

– Imaš 5 prijatelja i 5 stolica u nizu. Na koliko ih načina možeš posjesti? Tu svaki detalj rasporeda stvara novu mogućnost. Prvi stolac nije isti kao zadnji, znaš i sam koliko se ljudi znaju zakačiti tko će “sjediti do prozora”.

Kod permutacija:

• svi elementi su različiti
• koristiš ih sve
• svaka promjena redoslijeda znači nova mogućnost

—

Kombinacije: kad je bitno tko je unutra, ne i kojim redom

Kombinacije su više “tko je u ekipi”, a manje “tko gdje stoji”. To je odabir bez brige o rasporedu.

Primjer:

– Biraš 6 brojeva na lotu iz skupa {1, 2, …, 49}. Redoslijed kojim ih zaokružiš ne mijenja ništa. Kombinacija {7, 13, 21, 35, 42, 48} ista je bez obzira kojim redom su upisani na listić.

Ista priča s odabirom:

• članova odbora
• tima za kviz
• 5 karata iz špila (pokeraška ruka)

Bitno je *koji* su izabrani, ne i kojim su redom došli do tebe.

—

Repeticija: smije li se ponavljati?

Još jedan detalj koji često izgori usput.

Moraš jasno odlučiti:

– smije li se isti element koristiti više puta?

Primjeri:

• PIN kod na kartici: znamenke se mogu ponavljati → dopuštena ponavljanja
• Ruke u standardnom pokeru: ista karta ne može se pojaviti dva puta → bez ponavljanja
• Kolači u pekari: možeš uzeti 5 istih kiflica → ponavljanje dozvoljeno
• Podjela mjesta za tri učenika u tri različite klupe, ali svatko može samo na jedno mjesto → bez ponavljanja

Ovo mijenja formulu. Dobro postavljeno pitanje ovdje ti kasnije uštedi pola stranice krivih računa.

—

Kako to sve spojiti u praksu

Kad radiš zadatak, čak i ako je iz udžbenika, ja si to ovako posložim na papiru:

1. Definiraj skup

Što su ti “elementi”? Ljudi, karte, brojevi, stolice, nagrade…

2. Odredi važnost redoslijeda

Ako zamjena mjesta stvara novu situaciju → radi se o permutacijama / varijacijama.

Ako ne stvara → radi se o kombinacijama.

3. Provjeri ponavljanja

Može li isti broj/osoba/karta nastupiti više puta?

Ako da, ideš u verzije s ponavljanjem. Ako ne, ideš bez ponavljanja.

4. Upari s odgovarajućim alatom

• redoslijed bitan, bez ponavljanja → klasične permutacije/varijacije
• redoslijed nebitan, bez ponavljanja → kombinacije
• ima ponavljanja → njihove “rođakinje” s ponavljanjem

I da, kad jednom to klikne, zadaci iz vjerojatnosti prestanu biti lutrija i počnu ličiti na slagalicu.

—

Ako ti se čini apstraktno, to je zato što većinu ovih odluka donosiš nesvjesno i u stvarnom životu: kad biraš sastav ekipe za nogomet, raspored sjedanja u automobilu ili kombinaciju zaključavanja za sef. Kombinatorika samo sve to zapisuje čistim, preciznim jezikom — da ne moraš nabrajati mogućnosti do jutra.

Fakulteti i binomni koeficijenti

Prije nego što krenemo u one “prave” kombinatoričke zadatke koji znaju izgledati kao sudoku na steroidima, vrijedi stati na loptu i upoznati dva osnovna igrača u ekipi: faktorijale i binomne koeficijente.

Bez njih, permutacije i kombinacije su samo lijepa ideja na papiru.

—

Znaš ono kad u kuhinji trebaš posložiti sastojke redom — prvo brašno, pa šećer, pa jaja? Faktorijal radi nešto vrlo slično s brojevima.

Faktorijal broja *n*, zapisuje se kao n!, i znači: umnožak svih prirodnih brojeva od 1 do n.

Primjer iz prakse:

• 3! = 1 · 2 · 3 = 6
• 4! = 1 · 2 · 3 · 4 = 24

I onda dolazi onaj famozni detalj koji svi prvo prihvate “na riječ”, a tek kasnije skroz shvate koliko je praktičan: dogovor je da je 0! = 1.

Zašto? Jer se s tim malim trikom hrpa formula u kombinatorici “posloži” bez ružnih iznimki. Jednom kad se navikneš, bit će ti potpuno prirodno.

Kad sam prvi put učio ovo, doslovno sam si na marginu bilježnice pisao:

• 1! = 1
• 2! = 2
• 3! = 6
• 4! = 24
• 5! = 120

Nisam to radio zato što volim prepisivati — nego zato što, kad te netko pita “koliko je 5!”, ne želiš svaki put ispočetka množiti. Par puta zapišeš i ode u mišićnu memoriju.

—

Druga priča: binomni koeficijenti.

To je onaj C(n, k) izraz koji se pojavi čim trebaš “birati nešto iz nečega”.

Najjednostavnije: C(n, k) broji na koliko načina možeš izabrati k elemenata iz skupa od n elemenata, ako redoslijed nije bitan.

Primjer iz svakodnevice: Imaš 10 pjesama na playlisti i želiš složiti mini-playlistu od 3 pjesme, ali ti je svejedno kojom ćeš ih redom slušati — zanima te samo *koje* pjesme uđu unutra, ne kojim redom.

Broj tih mogućih trojki je upravo C(10, 3).

E sad, nije C(n, k) neka magična kratica bez veze. Povezan je s faktorijalom, i to vrlo uredno:

[

C(n, k) = frac{n!}{k!(n-k)!}

]

To je ona ključna formula koja spaja oba “alata”:

• gore imaš n!, dakle sve permutacije n elemenata
• dolje dijeliš s k! i (n−k)! jer te ne zanima redoslijed unutar odabranih k elemenata, niti redoslijed preostalih.

U praksi, kad kreneš rješavati zadatke iz kombinatorike, ovo dvoje radi iza kulisa gotovo uvijek:

• faktorijali za “koliko ima svih rasporeda”
• binomni koeficijenti za “koliko ima izbora bez reda”.

Ako si tek na početku, najbolji savjet: malo si ručno zapisuj male faktorijale i računaj par C(n, k) primjera.

Nije gubljenje vremena — to je onaj dio treninga koji kasnije uštedi sate živciranja.

Permutacije bez ponavljanja

Permutacije bez ponavljanja možda zvuče kao nešto iz suhoparne matematičke skripte, ali zapravo opisuju vrlo životnu stvar: koliko načina imamo da nekoga posložimo u red — pod uvjetom da nitko ne glumi duplog.

Dakle, igramo igru u kojoj:

• redoslijed *jest* bitan
• svaki se element (osoba, knjiga, predmet…) može iskoristiti točno jednom

To je cijela filozofija “bez ponavljanja”.

—

Kad slažemo sve elemente u red

Ako imaš n različitih elemenata i želiš ih sve posložiti u neki red, broj mogućih poredaka je:

P(n) = n!

Faktorski, taj famozni „!»“, znači da množiš sve cijele brojeve od n do 1.

Primjer iz učionice koji svi znaju:

• imaš 3 knjige na stolu
• pitaš se: koliko ih načina mogu posložiti na policu?

Račun je:

– 3! = 3 × 2 × 1 = 6 mogućih poredaka

Ako si ikad slagao lektire po bojama, visini ili „najdraža–najgora“, upravo si radio permutacije. Samo to tada nitko nije tako zvao.

—

Kad slažemo samo dio skupa

Stvari postaju mrvicu zanimljivije kad ne koristiš sve elemente, nego biraš samo neke i još ih pritom slažeš u određeni red.

Tada vrijedi formula:

P(n, k) = n! / (n − k)!

• n = ukupan broj elemenata
• k = koliko ih uzimaš i slažeš u red

Primjer iz školskog života:

• u razredu je 5 učenika koji dolaze u obzir za izlaganje
• trebaš raspored za 2 izlaganja zaredom
• redoslijed je bitan (nije isto tko ide prvi, a tko drugi)

Račun:

P(5, 2) = 5! / 3! = (5 × 4 × 3 × 2 × 1) / (3 × 2 × 1) = 5 × 4 = 20 mogućih poredaka

Drugim riječima, iako imaš samo petoro učenika i dva mjesta, kombinacija ima dovoljno da razred dobije materijala za raspravu do odmora.

—

Suština u jednoj rečenici:

Permutacije bez ponavljanja broje sve moguće „redoslijede bez duplikata“ — bilo da slažeš knjige, učenike, lozinke ili raspored govornika na konferenciji.

Permutacije s ponavljanjem i osnovna ograničenja

U ovom se dijelu naglasak prebacuje na prebrojavanje s ponovljenim elementima, gdje se neka slova ili znamenke pojavljuju više puta, a svaki drugačiji redoslijed i dalje se računa kao nova permutacija.

Zatim se prelazi na permutacije uz ograničenja za znamenke, pokazujući kako pravila poput „nema vodeće nule” ili „prvo slovo nije A” smanjuju broj valjanih permutacija.

Na kraju se uvode jednostavne strategije za uređaje s ograničenjima, pri čemu se preporučuje korak‑po‑korak pregled svake pozicije, pažljivo navođenje dopuštenih izbora, a tek potom primjena formula za permutacije kao što su (n^r) ili faktorijelsko pravilo za ponovljene simbole.

Prebrojavanje s ponovljenim elementima

Računanje s ponavljajućim elementima: onaj detalj koji svima pobjegne

Kad prvi put čuješ “n! podijeljeno s nečim”, zvuči kao da ti netko pokušava prodati lošu šalu iz udžbenika.

Ali ovo je zapravo vrlo životna priča: riječi s ponovljenim slovima, šifre u kojima se simboli ponavljaju, etikete, registarske tablice… sve to pada pod isti matematički kišobran.

—

Zašto uopće dijelimo s faktorijelima?

Kreneš od jednostavne ideje: imaš n elemenata i želiš znati na koliko ih se načina možeš posložiti.

Bez ikakvih ograničenja odgovor je čist: n!.

Ali — čim se neki elementi ponavljaju, nastaje problem.

Primjer: ako imaš tri slova *A, A, B*, zapisan redoslijed AAB i ABA stvarno su različiti.

Ali A₁A₂B i A₂A₁B tebi su ista stvar, jer ta dva A nisu razlikovljiva. Matematički bismo ih ipak “prebrojali dvaput” ako ne pazimo.

Tu ulijeće korekcija.

—

Opće pravilo u jednoj rečenici

Ako imaš ukupno n elemenata, a među njima:

• n₁ elemenata jedne vrste
• n₂ elemenata druge vrste
• …
• nₖ elemenata k‑te vrste

onda je ukupan broj različitih permutacija:

[

P(n; n_1, n_2, dots, n_k) = frac{n!}{n_1! , n_2! cdots n_k!}

]

U prijevodu: kreneš od n!, a zatim dijeliš s faktorijelom svake “grupe duplikata” da makneš lažna, višestruka brojanja.

—

“MATEMATIKA” pod lupom

Uzmimo riječ koja je mnogima obilježila djetinjstvo i pokoju frustraciju: MATEMATIKA.

Broj slova je jasan:

– ukupno: n = 10

Razbijmo ih po slovima:

• M se pojavljuje 2 puta
• A se pojavljuje 3 puta
• T se pojavljuje 2 puta
• E, I i K po jednom

Možeš to zapisati ovako: M₂ A₃ T₂ E₁ I₁ K₁

Sad ubaciš sve u formulu:

[

P = frac{10!}{2! cdot 3! cdot 2! cdot 1! cdot 1! cdot 1!}

]

Ovih 1! naravno ne mijenja ništa, ali ostavljamo ih u zapisu da se lijepo vidi struktura — svaki blok istih slova ima svoj “popravni faktor”.

—

Što kad postoje ograničenja po pozicijama?

Tu se priča malo zakomplicira, ali ne postaje nerješiva.

Primjer tipa koji profesori vole: “Koliko različitih rasporeda slova riječi MATEMATIKA postoji ako prvo slovo mora biti suglasnik?”

Postupak je dvostupanjski:

1. Prvo riješi uvjete po pozicijama.
• Odabereš što *smije* stajati na određenim mjestima (npr. prvi znak mora biti M, T ili K).
• Fiksiraš tu poziciju ili skup pozicija.
2. Tek onda na preostala mjesta primijeniš formulу s ponavljanjem.
• Kad “skineš” jedno slovo M ili T s popisa da ga staviš na prvo mjesto, više ga nemaš isti broj puta u ostatku riječi.
• Znači: u formuli za preostalih 9 pozicija nećeš više imati, recimo, M₂ nego M₁, i slično.

Ključ je da redoslijed uvijek ide ovako: prvo ispoštuj ograničenja po pozicijama, zatim pravilno prilagodiš brojeve ponavljanja pa tek na kraju računaš permutacije s formulom n! / (n₁!…nₖ!).

—

Ako jednom “klikneš” ovu logiku — n! gore, a dolje faktorijeli svih grupa koje se ponavljaju — više ti se neće događati da se izgubiš u riječima s duplim slovima ili kodovima s istim simbolima.

Matematički dio je jednostavan; trik je samo u tome da ne zaboraviš tko se koliko puta pojavio u priči.

Permutacije uz ograničenja znamenki

Kad god slažeš brojeve od zadanih znamenki, ne krećeš odmah u brojanje kao da radiš popis za dućan. Prvo moraš vidjeti koje su pozicije “osjetljive” — one za koje vrijede dodatna pravila — a tek onda ima smisla brojati permutacije.

Najčešće je problematična baš prva znamenka. Razlog je jednostavan: broj koji počinje nulom prestaje biti “pravi” višeznamenkasti broj i pretvori se u nešto kraće. Drugim riječima, 0427 nije četveroznamenkasti broj, nego 427. Zato prva pozicija u pravilu ima stroža pravila od ostalih.

Uzmi konkretan slučaj: skup znamenki {0,1,2,3,4,5,6,7,8,9} i zabranu prvih nekoliko znamenki {0,1,2,3} na početnoj poziciji.

To automatski znači da prva znamenka smije biti samo jedna od {4,5,6,7,8,9}. Već tu se sužava izbor, pa se kasnije sve ostalo računa polazeći od te “skresane” liste.

Nakon što odabereš prvu znamenku, svaka sljedeća pozicija traži novu malu provjeru:

• je li dozvoljeno ponavljanje znamenki (možemo li ponovno uzeti istu cifru ili ne)
• koliko je znamenki već iskorišteno do te točke
• postoji li još neko dodatno pravilo za baš tu poziciju (npr. zadnja znamenka mora biti parna, srednja ne smije biti 5 itd.)

Tek kad se sve te sitnice poslože u glavi, brojanje permutacija prestaje biti magija i postane čista, uredna kombinatorika.

Strategije za ograničena razmještanja

Kad krenu permutacije “s pravilima”, više nismo u onoj bezbrižnoj fazi n! i gotovo. Tu matematika odjednom počne ličiti na slaganje gostiju za svadbeni stol: neki ne smiju sjediti skupa, netko mora biti kraj prozora, prvi stol je “svečani”… pa hajde to posložiti.

Ja sam si kroz godine izvukao nekoliko trikova koji spašavaju živce — i vrijeme.

—

Prvo: pronađi ‘posebna’ mjesta

U svakom zadatku imaš pozicije koje jednostavno nisu iste kao ostale.

Prva znamenka broja ne smije biti nula.

Prvo slovo riječi mora biti suglasnik.

Zadnja dva mjesta moraju biti različita.

To su ti “VIP sjedala” u nizu. Dokle god ih ne izdvojiš, sve ostalo je mutno.

Ja uvijek prvo nacrtam crtice:

_ _ _ _

I iznad napišem što je s kojim mjestom: prvo — ne smije 0; drugo i treće — bilo što; četvrto — mora biti parna znamenka. Kad to vizualiziraš, pola posla je gotovo.

—

Drugo: dogovori se sam sa sobom što se smije ponavljati

Kod riječi i brojeva pod ograničenjima pitanje ponavljanja je presudno.

Imamo li slova koja se ponavljaju, tipa u riječi “ANANAS”?

Ili radimo s znamenkama 1,2,3,3,3?

Ili imamo beskonačno mnogo istih znamenaka (npr. “mogu se koristiti sve znamenke od 0 do 9, ponavljanje dopušteno”)?

Ako se nešto *smije* ponavljati, onda igraš drukčiju igru nego kad imaš fiksan skup koji se troši.

Sjećam se zadatka na faksu: brojke 1,2,3,4,5, ponavljanje dopušteno, a broj mora biti peteroznamenkast, prvi broj ne smije biti 0 (koje ionako nemamo), ali zadnja znamenka mora biti parna.

Ljudi krenu s 5! i odmah zablude.

Reality check: kad se ponavljanje dopušta, više nisi u svijetu “permutacija bez ponavljanja”, nego u kombinaciji “svako mjesto ima svoj mali meni izbora”.

—

Treće: formula n!/(n₁!·…·nₖ!) je tvoj osnovni alat — ali ne i jedini

Ona stara dobra:

broj permutacija s ponavljanjem = n! / (n₁! · … · nₖ!)

n — ukupan broj znakova

n₁, n₂… — koliko se puta ponavlja svako “isto” slovo/znamenka

Primjer koji su moji učenici obožavali mrziti: “KOMBINATORIKA”.

Ponoviš si:

– izbroji sva slova,

– izbroji koliko kojih,

– udari tu formulu i dobiješ “sirovi” broj mogućnosti *bez ikakvih dodatnih ograničenja*.

Onda tek kreće pravo pitanje: što smijem, a što ne?

Prvo slovo ne smije biti samoglasnik? Okej, uzmeš ukupni broj i odbaciš sve rasporede gdje je na početku samoglasnik.

Zvuči jednostavno, ali samo ako nisi preskočio ovu baznu računicu.

—

Četvrto: ograničenja rješavaš tako da ih *postupno eliminiraš*

Najčešća pogreška koju vidim: učenik pokuša u jednoj jedinoj formuli “uhvatiti” sva ograničenja.

Rezultat? Kaos.

Umjesto toga:

kreni korak po korak — nešto dodaš, nešto izbaciš.

Primjer iz učionice, onaj koji uvijek povuče uzdah:

“Koliko različitih četveroznamenkastih brojeva se može napisati znamenkama 0,1,2,2,3, pri čemu broj ne smije počinjati nulom?”

Taktika koju forsiram:

– Najprije zaboravi nulu, složi sve permutacije kao da je možeš staviti bilo gdje.

– Koristiš n!/(n₁!…): imaš 5 znamenki, 2 se ponavljaju → 5! / 2!.

– Zatim posebno izbrojiš *one loše* slučajeve u kojima je prva znamenka 0.

– Oduzmeš loše od ukupnog.

Postupno “odrezaš” zabranjene izbore. Kao da čistiš fotografiju od smetnji: ne radiš sve filtere odjednom, ideš sloj po sloj.

—

Mali trik iz prakse: mijenjaj perspektivu

Ponekad se više isplati brojati što *ne smije* nego što *smije*.

Nekad je lakše prvo složiti strukturu (npr. “prvo rasporedim samoglasnike, pa onda popunjavam praznine suglasnicima”).

Kad sam prvi put dobio zadatak “dva ista slova ne smiju biti jedno do drugoga”, iz čiste tvrdoglavosti sam pokušao direktno brojati “dobre” rasporede.

Zaglavio.

Nakon deset minuta natezanja shvatiš da je puno pametnije:

1. izbroj sve rasporede bez ograničenja;
2. pronađi koliko ih ima s barem jednim parom istih slova jedan do drugoga;
3. oduzmi.

To je onaj trenutak kad se permutacije iz neprijatelja pretvore u slagalicu.

—

Za kraj, kratki “mentalni podsjetnik” koji pomaže prije svakog zadatka:

– Gdje su “posebna” mjesta? (prvo, zadnje, sredina…?)

– Što se smije, a što se ne smije ponavljati?

– Mogu li prvo izračunati “sve bez ograničenja” preko n!/(n₁!·…·nₖ!)?

– Mogu li zabranjene slučajeve lakše izbrojati pa ih oduzeti?

Ako si to posložiš u glavi, i najnaporniji zadatak s permutacijama s ograničenjima postane — ako ne baš zabavan — onda barem dovoljno pitom da ga riješiš bez drame.

Varijacije (uređeni odabiri) i njihove formule

Kad god u kombinatorici čuješ da je “redoslijed bitan”, priča više nije o običnom biranju nego o varijacijama – uređenim izborima iz većeg skupa elemenata. Nije svejedno tko sjedi na kojem mjestu, tko je prvi, drugi, treći… to je upravo teritorij varijacija.

Zamisli policu s knjigama: jedno je odabrati koje tri knjige ćeš ponijeti na put, a nešto sasvim drugo odrediti i redoslijed u koferu, jer znaš koju želiš čitati prvu, a koju ostaviš za avion. Obje situacije koriste isti skup knjiga, ali samo druga “brine” o poretku — i zato spada u varijacije.

—

Što je zapravo varijacija?

Kratko:

Varijacija je uređeni izbor k elemenata iz skupa od n elemenata.

Dakle:

• biraš k elemenata,
• biraš ih iz n mogućih,
• i poredak tih k elemenata je važan.

Dva tipična scenarija:

• ne želiš ponavljanja (svaki se element može pojaviti samo jednom),
• dopuštaš ponavljanja (isti se element može izabrati više puta, na različitim pozicijama).

—

Varijacije bez ponavljanja

Ovdje igramo “svatko samo jednom”. Koristi se kad, primjerice, dodjeljuješ medalje: zlato, srebro, bronca. Nitko ne može osvojiti dvije medalje odjednom.

Formula za broj takvih uređenih izbora je:

[

V(n, k) = frac{n!}{(n-k)!}

]

• (n) – ukupan broj elemenata (npr. 10 učenika u razredu),
• (k) – koliko mjesta/pozicija popunjavaš (npr. 3 nagrade),
• faktorijel “!” znači umnožak svih brojeva do toga (5! = 5·4·3·2·1).

Primjer iz prakse: imaš 10 proizvoda, a trebaš složiti vitrinu s 3 pozicije, gdje je bitno koja je polica “prva”, koja “druga”, koja “treća”, i ne želiš isti proizvod dvaput.

[

V(10, 3) = frac{10!}{7!}

= 10 cdot 9 cdot 8

= 720

]

Dakle, postoji 720 različitih načina da složiš ta tri proizvoda po redu.

—

Varijacije s ponavljanjem

Druga priča: dopuštaš da se isti element pojavi više puta. Tipičan primjer je PIN kod ili lozinka: ista znamenka ili slovo može se ponavljati.

Tu je formula jednostavnija:

[

V(n, k) = n^k

]

• imaš (n) različitih mogućnosti za svaku poziciju,
• imaš (k) pozicija,
• svaka pozicija može biti bilo što od tih (n), neovisno o ostalima.

Primjer: 10 znamenki (0–9), a želiš 4-znamenkasti kod:

[

V(10, 4) = 10^4 = 10,000

]

Dakle, 10 000 različitih PIN-ova.

—

Kako odlučiti koju formulu koristiti?

Bez tablice se može, ali evo jedne kratke “mentalne provjere”:

• Pitaš se: Smije li se isti element ponoviti na više mjesta?
• Ako je odgovor ne → koristiš

[

V(n, k) = frac{n!}{(n-k)!}

]

– Ako je odgovor da → ide

[

V(n, k) = n^k

]

• I još jedno pitanje: Je li ti redoslijed stvarno bitan?
• Ako nije, tada nisi u svijetu varijacija nego u kombinacijama — to je već druga priča i drugačije formule.

—

Ako ti treba, mogu na istim brojkama (npr. 5 ljudi, 2 mjesta) usporediti varijacije i kombinacije, pa da razlika sjedne “u želudac”, ne samo na papir.

Kombinacije bez ponavljanja u problemima iz stvarnog života

1. U općem slučaju koristi se formula C(n, k) = n! / (k!(n − k)!). n je ukupan broj elemenata na raspolaganju, a k je koliko ih uzimamo — bez ponavljanja i bez reda.
2. Kod izbora odbora priča je vrlo prizemna: važno je *tko* sjedi za stolom, a potpuno je nebitno kojim su redoslijedom dobili glasove. Kombinacije, ne permutacije.
3. Loto je ista logika, samo s više adrenalina. Broj mogućih listića računa se kao C(39, 7) — biraš 7 brojeva od 39, ali raspored na listiću ne mijenja ništa na dobitku.
4. Karte, pizze, salate… U svim tim situacijama redoslijed izbora nema nikakvu težinu.

Poker ruka od pet karata ista je ruka bez obzira kojim si ih redom podigao s špila, a pizza s pršutom, gljivama i mozzarellom ista je — bez obzira jesi li pršut naručio prvi ili zadnji.

Kombinacije s ponavljanjem i „zvjezdice i pregrade“

U prošloj cjelini stalno smo igrali na sigurno: svaki se element smio iskoristiti najviše jednom. To u učionici zvuči uredno, ali u stvarnom životu pada u vodu nakon prve kuglice sladoleda. Tko uzima samo jedan okus? Ili u voćnoj salati — tko stavlja točno jednu jagodu, jednu bananu, jednu borovnicu… i gotovo?

Zato nam trebaju kombinacije s ponavljanjem. One hvataju baš te situacije iz stvarnog života:

• redoslijed *nije* bitan
• isti se element može pojaviti više puta

Ne brojimo dakle “čokolada–vanilija–čokolada” kao drukčije od “čokolada–čokolada–vanilija”. Brojimo samo *koje* smo okuse uzeli i *koliko puta* svaki.

—

Gdje upada formula C(n + k − 1, k)?

Ako imaš:

• n različitih elemenata (npr. 5 okusa sladoleda)
• k odabira (kuglica)

onda broj različitih kombinacija s ponavljanjem daje formula:

> C(n + k − 1, k)

Primjer iz života:

Imaš 4 okusa sladoleda u slastičarnici i želiš čašu sa 3 kuglice. Možeš uzeti sve tri iste, tri različite, dvije iste + jednu drugu…

Tu upada:

• n = 4 (okusi)
• k = 3 (kuglice)

Broj mogućih “čaša sladoleda” po okusu je:

> C(4 + 3 − 1, 3) = C(6, 3)

Koliko je točno — to možeš izračunati, ali bitnije je da znaš *zašto* baš taj izraz.

—

“Zvjezdice i crte” — vizual za glavu, ne za Instagram

Metoda stars and bars, kod nas često “zvjezdice i crte”, služi da cijelu tu priču nacrtaš u jednoj liniji.

Dogovor:

• zvjezdice (*) = odabiri (kuglice, komadići voća…)
• crte (|) = granice između vrsta

Primjer: imaš 3 vrste voća i želiš ukupno 5 komadića u voćnoj salati.

To znači:

• n = 3 (recimo jabuka, banana, kivi)
• k = 5 (ukupno 5 komadića)

U “zvjezdicama i crtama” to izgleda kao niz:

• 5 zvjezdica (jer biraš 5 komada)
• 2 crte (jer 3 vrste voća = 2 granice između njih)

Nešto tipa:

> **|*|**

Ovo možeš čitati ovako:

• prije prve crte: 2 zvjezdice → 2 komada *jabuke*
• između crta: 1 zvjezdica → 1 komad *banane*
• iza druge crte: 2 zvjezdice → 2 komada *kvija*

Ukupno 5 komadića, raspoređenih po vrstama.

Svaki *drugačiji raspored* zvjezdica i crta označava neku drugu kombinaciju brojeva (0 jabuka, 5 banana, 0 kivija; ili 4 jabuke, 1 kivi; i tako dalje).

A koliko takvih rasporeda ima?

Gledaš koliko ukupnih simbola pišeš u red:

• zvjezdica: k
• crta: n − 1

Ukupno: n + k − 1 simbola.

Trebaš odabrati mjesta za k zvjezdica (ili za crte, svejedno), pa dobiješ:

> C(n + k − 1, k)

I eto — ista formula iz malo ljudskije priče.

—

Ako si dosad kombinacije doživljavao kao suhoparni C(n, k) iz tablice na kraju udžbenika, ovo je onaj trenutak kad klikne:

ponavljanje elemenata + nebitan redoslijed = kombinacije s ponavljanjem, a zvjezdice i crte su ti najbrži mentalni crtež za to.

Primjena permutacija i kombinacija na vjerojatnost i zadatke tipa lutrije

U problemskim zadacima nalik lutriji koriste se permucije kada je redoslijed izvučenih brojeva važan, dok se kombinacije koriste kada je bitan samo skup brojeva, kao u standardnom izvlačenju “7 od 39”.

Modeliranjem izvlačenja pomoću kombinacija čitatelj može izračunati ukupan broj mogućih listića, a zatim to pretvoriti u jasnu vjerojatnost dobitka, primjerice izglede 1 prema 15.380.937.

Ovaj odjeljak objašnjava kako korak po korak postaviti takve modele, pokazuje kako izračunati realne šanse za dobitak i ističe zašto ni dobre strategije odabira brojeva ne mogu nadvladati vrlo male izglede.

Modeliranje izvlačenja na lutriji

Kad gledaš loto na televiziji, sve djeluje kao neka magija kuglica i sreće.

Ali ispod te šarene plastike krije se sasvim prizemna matematika. Nema kristalne kugle, ima — kombinatorika.

Krenimo od onog klasičnog formata: recimo da biraš 7 brojeva od 39. To je naš “kruh i mlijeko” u domaćim lotima.

Prva važna stvar: listić nije niz, nego *skup*. Redoslijed ne igra nikakvu ulogu.

Ako uzmeš 1, 5, 12, 19, 27, 32, 38 — isto ti vrijedi kao 38, 32, 27, 19, 12, 5, 1. Lutriju ne zanima kojim redom si ih zaokružio, samo što je na kraju na listiću.

Matematički se to zove kombinacija. Za naš primjer koristi se formula:

C(39, 7) = 39! / (7! · (39 − 7)!)

Kad to stvarno izračunaš, dobiješ 15.380.937 mogućih različitih listića. Toliko različitih “svemira” postoji u jednoj običnoj igri 7 od 39.

I tvoj listić je samo jedan od tih petnaest milijuna i nešto.

Znam, zvuči brutalno kad shvatiš kolika je šansa da pogodiš sve brojeve.

Ali iskreno — bolje je znati gdje stojiš, nego živjeti u iluziji da postoji neka “tajna šifra” koju netko u kladionici šapće “svojima”.

Tu dolazimo do vječnog mita: *uzorci*.

Ljudi vole gledati listiće i tražiti “logiku”: dijagonale na listiću, “nijedan listić bez broja 7”, “nikad dva uzastopna broja”, datumi rođenja…

Čim vidiš da netko priča o “sustavu koji uvijek radi”, možeš slobodno mentalno okrenuti očima.

Zašto? Zato što svaka od tih 15.380.937 kombinacija ima potpuno istu šansu biti izvučena.

Skroz je svejedno je li kombinacija “ružna” (2, 3, 4, 5, 6, 7, 8) ili “lijepa” (3, 7, 11, 19, 25, 32, 38).

Loto aparat ne zna za estetiku, datume rođenja, godišnjice i “osjećaj u kostima”.

Možeš raditi statističke analize prošlih izvlačenja, brojati koliko se puta pojavio broj 17, gledati koje kombinacije “dugo nisu izašle”…

Ali to ti ne mijenja budućnost. Loto je dizajniran tako da uvijek zadrži element čiste nasumičnosti.

To je ugrađeno u igru — baš da bi spriječilo bilo kakvo dugoročno “nadmudrivanje sustava”.

To ne znači da ne smiješ uživati u igri.

Samo znači da ju je pametno gledati ovako:

• listić = skup brojeva, red nebitan
• broj mogućih listića = kombinacije (u našem primjeru više od 15 milijuna)
• svaki listić ima istu šansu, bez obzira na uzorak, “feeling” ili ritual

Ako igraš s tim na umu, štitiš se od razočaranja i skupih zabluda.

Igra ostaje ono što zapravo jest: mala matematička avantura začinjena čistom srećom — ne strategija za “pametne” koja će ti preko noći donijeti vilu od 2.000.000 €.

Izračunavanje vjerojatnosti pobjede

Kad jednom progutaš činjenicu da je tvoj listić samo jedna sitna kombinacija u moru milijuna, cijela priča s lotom odjednom se ohladi. Nema više onog “osjećam da je moj red” — ostane gola matematika.

U igri 7 od 39 brojke su brutalno jasne: postoji C(39,7) = 15.380.937 različitih kombinacija. To znači da je tvoj “sretni” listić samo 1 od 15.380.937 mogućih. Šansa za glavni zgoditak? Točno ta: 1 : 15.380.937.

Da, to je otprilike kao da se nadaš da ćeš na parkingu u špici u centru Zagreba naći slobodno mjesto… i još koverta puna keša na vozačevom sjedalu.

—

Što to znači u praksi?

Jednom sam sjedio s prijateljem koji redovno “puni” loto. I kaže on: “Ma dobro, kupim pet listića, povećavam si šansu pet puta.”

Istina, ali pet puta gotovo ništa je i dalje — skoro ništa. Pet listića ti samo daje 5 od 15.380.937 kombinacija. Matematički je šansa veća, ali toliko malo da je psihološki efekt jači od stvarnog.

Par stvari koje vrijedi imati u glavi:

• Više listića ≠ realna šansa za životnu prekretnicu. Umjesto 1 : 15.380.937, imaš možda 10 : 15.380.937. Iz perspektive statistike, i dalje si praktički promatrač, ne favorit.
• Razumijevanje kombinacija pomaže smiriti očekivanja. Kad shvatiš koliko je 15 milijuna kombinacija, drukčije gledaš na onih svojih par odigranih. Nije poanta da prestaneš igrati, nego da prestaneš računati na to kao na plan B za život.
• Svaka promjena pravila mijenja igru. Manje brojeva u bubnju? Veća šansa. Mogućnost ponavljanja brojeva? Opet nova matematika. Loto nije magija, nego set pravila koja određuju koliko je tvoj pogodak (ne)vjerojatan.
• Tablice prošlih izvlačenja ne spašavaju stvar. Znam ljude koji vode svoje “statistike” po bilježnicama, boje brojeve, prate koji “kasne”… Lijep mali hobi, ali brojevi nemaju pamćenje. Kladiti se na broj jer “ga dugo nije bilo” isto je kao bacati kovanicu i misliti da je glava “dužna” pasti.

—

Pa što onda s lotom?

Ako ga gledaš kao razonodu — kao što netko ode na koncert, drugi ode na tekmu, ti odigraš par kombinacija — sve je u redu. Problem nastaje kad se u glavi pretvori u “strategiju ulaganja”.

Puno je zdravije gledati na loto ovako:

• uplata je cijena za kratku fantaziju (“što bih da dobijem…”)
• ishod je unaprijed jasan: gotovo sigurno nećeš dobiti ništa ozbiljno
• ako se kojim čudom dogodi dobitak, to je bonus, ne plan

Jednom sam si namjerno zapisao sve uplate za godinu dana. Sitno po sitno, ispalo je više od 200 €. Za isti iznos mogao sam otplatiti dio godišnjeg, kupiti solidne slušalice ili ubaciti u fond i pustiti da raste. Loto uspomena od toga? Nula.

—

Zaključak, bez šminke

Loto može biti zabavna navika, kratki bijeg iz svakodnevice, ali nije financijska strategija, nije mirovina i nije plan za stan. Igraj ako ti je gušt — ali umjereno, za iznos koji ti je potpuno svejedno hoće li nestati.

Kao zabava? U redu. Kao ulaganje? Ne.

Često postavljana pitanja

Kako prepoznati greške pri razlikovanju permutacija i kombinacija u zadacima?

Kao crvena lampica, greška se prepoznaje čim učenik zanemari poredak.

Treba provjeriti:

• Je li u zadatku jasno važan redoslijed izbora? Ako jest, koristi se permutacija.
• Bira li se “skup” bez brige o mjestu? Tada je kombinacija.

Preporučuje se:

• Podvlačiti riječi poput “redoslijed”, “poredak”, “grupa”.
• Nakon rješenja, ukratko preformulirati zadatak riječima: “Brinem li se o redu?”

Kako efikasno učiti permutacije i kombinacije za prijemne ispite?

Učenik uči najefikasnije kad:

• Prvo nauči razliku: permutacije – poredak je bitan, kombinacije – poredak nije bitan.
• Zapiše ključne formule na mali „šalabahter“ za brzo ponavljanje.
• Rješava serije zadataka istog tipa, zatim miješane zadatke.
• Poslije svakog zadatka kratko objasni sebi naglas zašto je rješenje ispravno.
• Redovito provjerava tipične pogreške i ispravlja ih.

Koje su najčešće zablude učenika o permutacijama i kombinacijama?

Poput labirinta sa sličnim hodnicima, učenici često:

• Misle da je “više opcija” uvijek kombinacija, pa zanemare redoslijed
• Brkaju permutacije bez ponavljanja s onima s ponavljanjem
• Zaborave uvjet “bez zamjene” ili “sa zamjenom” kod zadatka
• Uče napamet formule, bez razumijevanja “priče” zadatka

Preporuka: prvo opisati situaciju riječima, zatim odabrati odgovarajuću formulu.

Kako softverski alati mogu pomoći pri rješavanju kombinatornih problema?

Softverski alati pomažu jer brzo računaju, provjeravaju rješenja i vizualiziraju uzorke.

• Kalkulatori i aplikacije: nude gotove funkcije za brojanje izbora, rasporeda i podskupova.
• Tablični proračuni: omogućuju tablice slučajeva, formule i grafove.
• Sustavi računalne algebre: rješavaju veće, složenije zadatke.

Koristan je oprez, alati olakšavaju rad, ali korisnik i dalje mora razumjeti postupak.

Kako proširiti osnovne formule na naprednije kombinatorne strukture (grafovi, kodovi)?

Napredne strukture proširuju osnovne formule dodavanjem uvjeta i veza među objektima.

• Za grafove koristi se brojanje putova, ciklusa i obojenja čvorova, često uz matrice susjedstva i rekurzivne relacije.
• Za kodove primjenjuju se kombinacije s ograničenjima udaljenosti, koriste se binarni nizovi i Hammingova udaljenost.

Preporučuje se rad s malim primjerima, softverskim alatima i postupno uvođenje novih pravila.