Kombinatorika Osnovni pojmi

Kombinatorika

• Osnovni pojmi

• Permutacije, variacije, kombinacije

• Tipične kombinatorične naloge sprašujejo po številu različni razporeditev, izborov ali sestavljenih odločitev.

• Primeri

• 4-mestna števila iz števk od 1 do 9

• Število posaditev 4 dreves v drevored. Kaj se zgodi, če breza in platana na smeta biti posajeni druga ob drugi?

• 120 študentov RP; oblikujemo seminarske skupine po 3 študente. Koliko je vseh različnih trojk?

• Kombinatorično drevo – nazoren prikaz korakov pri odločanju

• Primeri:

• Priprava zajtrka 1: tri vrste kruha, dva namaza

• (dvostopenjsko odločanje – izbor na drugi stopnji (npr. vrsta namaza) je neodvisen od izbora na prvi stopnji (npr. vrsta kruha)).

• Priprava zajtrka 2: tri vrste kruha, dva namaza, 4 napitki (tristopenjsko odločanje)

• Posplošitev? Oblikujte pravilo.

• Naj bo proces odločanja takšen, da poteka v k zaporednih fazah, pri čemer je v prvi fazi n1, v drugi n2…, in v k-ti fazi nk možnih odločitev, število izborov v posameznih fazi pa je neodvisno od tega, katere možnosti smo izbrali v predhodnih fazah. Potem je mogoče sestavljeni izbor opraviti na natanko

• n = n1 x n2 x n3 x…x nk

• načinov.

• To pravilo imenujemo osnovni izrek kombinatorike oz. pravilo produkta.

• Drugi načini prikazovanja za primera ‘Zajtrk 1 in 2’?

• Nesimetrično kombinatorično drevo

• Primer: trimestna števila iz treh različnih števk, npr. 1, 2, 3, pri čemer 2 ne sme biti na mestu desetic.

• Drugi primeri za simetrično in nesimetrično kombinatorično drevo.

• Primer

• Miha ima 3 pare športnih obutev in 2 para elegantnih čevljev. Na koliko načinov se lahko obuje?

• Pravilo?

• Če se pri izbiranju lahko odločimo za eno od n1 možnosti iz prve množice ali pa za eno od n2 možnosti iz druge množice izborov, ki so nezdružljivi z izbori iz prve množice, imamo

• n = n1 + n2 možnih izborov.

• To pravilo imenujemo pravilo vsote.

• Permutacije

• Urejanje vseh elementov dane množice v vrsto (npr. od leve proti desni) – iskanje števila vseh možnih razporedb

• Permutacije brez ponavljanja

• n! – ‘n fakulteta’, ‘n faktorsko’, ‘n faktorialno’

• n!

• 0! = 1

• Primeri

• Učenci v kolone

• 5 mestna števila (prvih pet in zadnjih pet po leksikografski oz. slovarski ureditvi)

• Športniki v barvnih oblačilih

• Permutacije kot preslikave

• Vsaka bijektivna preslikava končne množice nase je permutacija. Poljubno končno množico z močjo n na natančno n! načinov bijektivno preslikamo nase.

• Grafi permutacij

• Permutacije s ponavljanjem

• Razporedb dolžine n, v katerih na k mestih nastopa enak objekt (ostali pa so od njega in med seboj različni), je k! manj, kot bi bilo permutacij n različnih objektov.

• Kaj, če se ponavljajo različni objekti v dani skupini n objektov?

• Primeri:

• Koliko je permutacij (razporedb) črk besede MATEMATIKA?

• Športniki v barvnih oblačilih

• Variacije

• - tudi pri variacijah gre za linearno urejanje elementov, vendar tokrat ne jemljemo vseh elementov, ampak samo neko podmnožico, npr. r od n elementov.

• Variacije brez ponavljanja

• Primer: variacije reda 5, ki jih sestavimo iz števk 0 – 9.

Če produkt pomnožimo z (n-r)(n-r-1)…2.1 in tudi delimo, dobimo:

• Če produkt pomnožimo z (n-r)(n-r-1)…2.1 in tudi delimo, dobimo:

• (Enak izračun dobimo po osnovnem izreku kombinatorike.)

• Če je n = r …

• Variacije s ponavljanjem

• Primer: variacije reda 5, ki jih sestavimo iz števk 0 – 9.

• 00000, 00001, 00002, 00003…

• (Za vsakega od predalčkov imamo na voljo n elementov.)

• Variacije s ponavljanjem:

• Primer: Koliko trimestnih števil iz števk 1, 3, 5, 7 in 9 je manjših od 600? (v obeh primerih: ko se števke lahko ponavljajo in ko se ne)

• Kombinacije

• - variacije, pri katerih vrstni red ni pomemben

• Primer: Kombinacije reda 3 iz elementov A, B, C, D

• Izpeljava splošnega zapisa za število kombinacij brez ponavljanja ( ).

• Binomski simbol

• Kombinacije s ponavljanjem

• Primer: Mama ima 4 otroke. Zastavi jim tri naloge. Na koliko načinov lahko razporedi naloge med otroke?