combinatorics

Kombinatorika

​

Mirzad Kesko

​[e-mail]

​Kombinatorika

• ​Kombinatorika je grana diskretne matematike koja se bavi diskretnim strukturama koje su finitne ili koje se mogu prebrojati.

• Povezana je s mnogim drugim granama matematike, poput algebre, teorije vjerojatnoće i geometrije kao i raznim područjima u računarstvu i statističkoj fizici.

Multiple Select

Kod kojih starih civilizacija još susrećemo elemente kombinatorike?

• Indijaca

• Maya

• Kineza

• Arapa

• Azteci

​Faktorijeli

• ​Umnožak prvih n prirodnih brojeva označavamo n! i čitamo "n faktorijela".

​

Dakle:

​1! = 1, 2! = 2*1 = 2, 3! = 3*2*1 = 6, 5! = 5*4*3*2*1 = 120

​

​Po definiciji stavljamo 0!=1.

​Faktorijeli zadovoljavaju rekurzivnu formulu

​ n! = n*(n-1)!

Multiple Choice

Izračunajte $$\frac{10!}{8!}=?$$  

• 40240

• 90

• 180

• 324

Binomni koeficijent​

Multiple Choice

Izračunati $$\left(_3^7\right)=?$$  

• $$\left(_3^7\right)=\frac{7!}{3!\cdot\left(7-3\right)!}=\frac{7\cdot6\cdot5\cdot4!}{3!\cdot4!}=\frac{7\cdot6\cdot5}{1\cdot2\cdot3}=7\cdot5=32$$  

• $$\left(_3^7\right)=\frac{7!}{3!\cdot\left(7-3\right)!}=\frac{7\cdot6\cdot5\cdot4!}{3!\cdot4!}=\frac{7\cdot6\cdot5}{1\cdot2\cdot3}=7\cdot5=35$$  

​Princip uzastopnog prebrojavanja

• Ako možemo birati prvi element na ​a₁ načina,

​drugi element na a₂ načina,

​n-ti element na a_n načina,

​tada je ukupan broj načina na koji možemo birati uređenu n-torku jednak

​a₁*a₂*....*a_n.

​Varijacije bez ponavljanja

Poll

Koliko se dvocifrenih brojeva može napisati od cifri 1,2,3,4,5, ako svaku cifru smijemo iskoristiti samo jednom?

• 15

• $$V_5^2\ =\ 2\cdot5\ =\ 10$$  

• $$V_5^2\ =\ 5\cdot4=20$$  

• 5! = 5*4*3*2*1 = 120