Kombinatorika Osnovni pojmi

Sana19.12.2017
Hajmi445 b.


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?




Do'stlaringiz bilan baham:

©2018 Учебные документы
Рады что Вы стали частью нашего образовательного сообщества.
?


korobejniki---voprosi-k.html

korobiha-auildi-okrug--.html

korobov-ivan-maksimovich-.html

koroglu-partitura-indd---6.html

korol--vi-ochen-horosho.html