0. Kaj je kombinatirika ?

0. Kaj je kombinatirika ?

0. Kaj je kombinatirika ?

”To je umetnost preˇstevanja razporeditev elementov v konˇcnih mnoˇzicah.”(Bernoulli)

Mc 2

Zanimivi problemi, povezani s kombinatoriko:

Igre na sreˇco: koliko je moˇznih kombinacij pri igri sedmica, 3 × 3, . . .

Zanimivi problemi, povezani s kombinatoriko:

Igre na sreˇco: koliko je moˇznih kombinacij pri igri sedmica, 3 × 3, . . . Igre s kartami: poker,. . .

Mc 2

1.Osnovni pravili v kombinatoriki

1.Osnovni pravili v kombinatoriki

Mc 2

Pravilo vsote: ˇ Ce se lahko dogodek A zgodi na m moˇ znih naˇ cinov, dogodek B pa na n moˇ znih naˇ cinov in so vsi dogodki paroma razliˇ cni, ima dogodek

A ali B m + n moˇ znih izzidov.

Pravilo vsote: ˇ Ce se lahko dogodek A zgodi na m moˇ znih naˇ cinov, dogodek B pa na n moˇ znih naˇ cinov in so vsi dogodki paroma razliˇ cni, ima dogodek

A ali B m + n moˇ znih izzidov.

Pojasnilo z mnoˇzicami:

Pravilo vsote: ˇ Ce se lahko dogodek A zgodi na m moˇ znih naˇ cinov, dogodek B pa na n moˇ znih naˇ cinov in so vsi dogodki paroma razliˇ cni, ima dogodek

A ali B m + n moˇ znih izzidov.

Pojasnilo z mnoˇzicami: za disjunktni mnoˇzici A in B velja

|A ∪ B| = |A| + |B|.

Pravilo vsote: ˇ Ce se lahko dogodek A zgodi na m moˇ znih naˇ cinov, dogodek B pa na n moˇ znih naˇ cinov in so vsi dogodki paroma razliˇ cni, ima dogodek

A ali B m + n moˇ znih izzidov.

Pojasnilo z mnoˇzicami: za disjunktni mnoˇzici A in B velja

|A ∪ B| = |A| + |B|.

...

........................................................................................................................................................................................................................................................

...

...

...

...

...

...

...

.........

... . .. . .. ....

... . .. . .. ....

... . .. . .. ....

... .. . . .. ....

a₁ a₂ a₃

...a_n ...

........................................................................................................................................................................................................................................................

...

...

...

...

...

...

............

...

. .. . .. ....

...

. .. . .. ....

...

. .. . .. ....

...

.. . . .. ....

b₁ b₂ b₃

...b_m

A ∩ B = ∅

Mc 2

Sploˇsno: ˇ ce so mnoˇ zice A

, A

, . . . , A

disjunktne, velja

|A

∪ A

∪ · · · ∪ A

| = |A

| + |A

| + · · · + |A

|.

Mc 2

Zgled 1: V omari imam 3 kape in 2 klobuka. Na koliko naˇcinov si lahko pokrijem glavo?

Zgled 1: V omari imam 3 kape in 2 klobuka. Na koliko naˇcinov si lahko pokrijem glavo?

Na glavo lahko dam eno kapo ali en klobuk. Torej je vseh moˇznosti 3 + 2 = 5.

Zgled 1: V omari imam 3 kape in 2 klobuka. Na koliko naˇcinov si lahko pokrijem glavo?

Na glavo lahko dam eno kapo ali en klobuk. Torej je vseh moˇznosti 3 + 2 = 5.

Zgled 2: V trgovini prodajajo 5 modelov digitalnih fotoaparatov Canon, 3 modele proizvajalca Sony, 2 modela proizvajalca Nikkon ter 1 model znamke Pentax. ˇZelim kupiti en aparat. Na koliko naˇcinov lahko to storim?

Zgled 1: V omari imam 3 kape in 2 klobuka. Na koliko naˇcinov si lahko pokrijem glavo?

Na glavo lahko dam eno kapo ali en klobuk. Torej je vseh moˇznosti 3 + 2 = 5.

Zgled 2: V trgovini prodajajo 5 modelov digitalnih fotoaparatov Canon, 3 modele proizvajalca Sony, 2 modela proizvajalca Nikkon ter 1 model znamke Pentax. ˇZelim kupiti en aparat. Na koliko naˇcinov lahko to storim?To lahko storim na

5 + 3 + 2 + 1 = 11 naˇcinov.

Mc 2

Pravilo produkta (osnovni izrek kombinatorike): Ce lahko ˇ element a iz mnoˇ zice A izberemo na m naˇ cinov, element b iz mnoˇ zice B pa na n moˇ znih naˇ cinov, lahko

urejen par (a, b) izberemo na mn moˇ znih naˇ cinov.

Pravilo produkta (osnovni izrek kombinatorike): Ce lahko ˇ element a iz mnoˇ zice A izberemo na m naˇ cinov, element b iz mnoˇ zice B pa na n moˇ znih naˇ cinov, lahko

urejen par (a, b) izberemo na mn moˇ znih naˇ cinov.

Pojasnilo z mnoˇzicami:

Pravilo produkta (osnovni izrek kombinatorike): Ce lahko ˇ element a iz mnoˇ zice A izberemo na m naˇ cinov, element b iz mnoˇ zice B pa na n moˇ znih naˇ cinov, lahko

urejen par (a, b) izberemo na mn moˇ znih naˇ cinov.

Pojasnilo z mnoˇzicami: za poljubni mnoˇzici A in B velja

|A × B| = |A| · |B|.

Sploˇsno: za mnoˇ zice A

, A

, . . . , A

velja

|A

× A

× · · · × A

| = |A

| · |A

| · · · |A

|.

Mc 2

Zgled 1: Vrˇzemo rdeˇco in modro kocko. Koliko je moˇznih izzidov?

Zgled 1: Vrˇzemo rdeˇco in modro kocko. Koliko je moˇznih izzidov?

Na vsaki kocki imamo po 6 moˇznosti. Torej je ˇstevilo vseh moˇznih izzidov 6 · 6 = 36.

Zgled 1: Vrˇzemo rdeˇco in modro kocko. Koliko je moˇznih izzidov?

Na vsaki kocki imamo po 6 moˇznosti. Torej je ˇstevilo vseh moˇznih izzidov 6 · 6 = 36.

Zgled 2: V omari imam 3 kape, 4 srajci, 1 hlaˇce in 2 para natikaˇcev. Na koliko naˇcinov se lahko obleˇcem?

Zgled 1: Vrˇzemo rdeˇco in modro kocko. Koliko je moˇznih izzidov?

Na vsaki kocki imamo po 6 moˇznosti. Torej je ˇstevilo vseh moˇznih izzidov 6 · 6 = 36.

Zgled 2: V omari imam 3 kape, 4 srajci, 1 hlaˇce in 2 para natikaˇcev. Na koliko naˇcinov se lahko obleˇcem?

Izberem 1 kapo, eno srajco, 1 hlaˇce in 1 par natikaˇcev. Po pravilu produkta je vseh moˇznosti 3 · 4 · 1 · 2 = 24.

Zgled 1: Vrˇzemo rdeˇco in modro kocko. Koliko je moˇznih izzidov?

Na vsaki kocki imamo po 6 moˇznosti. Torej je ˇstevilo vseh moˇznih izzidov 6 · 6 = 36.

Zgled 2: V omari imam 3 kape, 4 srajci, 1 hlaˇce in 2 para natikaˇcev. Na koliko naˇcinov se lahko obleˇcem?

Izberem 1 kapo, eno srajco, 1 hlaˇce in 1 par natikaˇcev. Po pravilu produkta je vseh moˇznosti 3 · 4 · 1 · 2 = 24. Ce to prikaˇˇ zemo v obliki urejenih ˇcetveric:

(k₁, s₁, h₁, n₁) (k₁, s₁, h₁, n₂) (k₁, s₂, h₁, n₁) (k₁, s₂, h₁, n₂) (k₁, s₃, h₁, n₁) (k₁, s₃, h₁, n₂) (k₁, s₄, h₁, n₁) (k₁, s₄, h₁, n₂) (k₂, s₁, h₁, n₁) (k₂, s₁, h₁, n₂) (k₂, s₂, h₁, n₁) (k₂, s₂, h₁, n₂) (k₂, s₃, h₁, n₁) (k₂, s₃, h₁, n₂) (k₂, s₄, h₁, n₁) (k₂, s₄, h₁, n₂) (k₃, s₁, h₁, n₁) (k₃, s₁, h₁, n₂) (k₃, s₂, h₁, n₁) (k₃, s₂, h₁, n₂) (k₃, s₃, h₁, n₁) (k₃, s₃, h₁, n₂) (k₃, s₄, h₁, n₁) (k₃, s₄, h₁, n₂)

Zgled 1: Vrˇzemo rdeˇco in modro kocko. Koliko je moˇznih izzidov?

Na vsaki kocki imamo po 6 moˇznosti. Torej je ˇstevilo vseh moˇznih izzidov 6 · 6 = 36.

Zgled 2: V omari imam 3 kape, 4 srajci, 1 hlaˇce in 2 para natikaˇcev. Na koliko naˇcinov se lahko obleˇcem?

Izberem 1 kapo, eno srajco, 1 hlaˇce in 1 par natikaˇcev. Po pravilu produkta je vseh moˇznosti 3 · 4 · 1 · 2 = 24. Ce to prikaˇˇ zemo v obliki urejenih ˇcetveric:

(k₁, s₁, h₁, n₁) (k₁, s₁, h₁, n₂) (k₁, s₂, h₁, n₁) (k₁, s₂, h₁, n₂) (k₁, s₃, h₁, n₁) (k₁, s₃, h₁, n₂) (k₁, s₄, h₁, n₁) (k₁, s₄, h₁, n₂) (k₂, s₁, h₁, n₁) (k₂, s₁, h₁, n₂) (k₂, s₂, h₁, n₁) (k₂, s₂, h₁, n₂) (k₂, s₃, h₁, n₁) (k₂, s₃, h₁, n₂) (k₂, s₄, h₁, n₁) (k₂, s₄, h₁, n₂) (k₃, s₁, h₁, n₁) (k₃, s₁, h₁, n₂) (k₃, s₂, h₁, n₁) (k₃, s₂, h₁, n₂) (k₃, s₃, h₁, n₁) (k₃, s₃, h₁, n₂) (k₃, s₄, h₁, n₁) (k₃, s₄, h₁, n₂)

Mc 2

Zgled 3: Iz Kopra peljejo 3 ladje v Poreˇc,iz Poreˇca pelje 5 ladij v Split, iz Splita pa 6 ladij do Dubrovnika. Na koliko naˇcinov lahko pride turist iz Kopra v Dubrovnik?

Zgled 3: Iz Kopra peljejo 3 ladje v Poreˇc,iz Poreˇca pelje 5 ladij v Split, iz Splita pa 6 ladij do Dubrovnika. Na koliko naˇcinov lahko pride turist iz Kopra v Dubrovnik?

Stevilo moˇˇ znih voˇzenj je enako 3 · 5 · 6 = 90.

Zgled 3: Iz Kopra peljejo 3 ladje v Poreˇc,iz Poreˇca pelje 5 ladij v Split, iz Splita pa 6 ladij do Dubrovnika. Na koliko naˇcinov lahko pride turist iz Kopra v Dubrovnik?

Stevilo moˇˇ znih voˇzenj je enako 3 · 5 · 6 = 90.

Zgled 4: Koliko je vseh ˇstevil med 10000 in 100000, ki vsebujejo le ˇstevke 1,2 in 3?

Zgled 3: Iz Kopra peljejo 3 ladje v Poreˇc,iz Poreˇca pelje 5 ladij v Split, iz Splita pa 6 ladij do Dubrovnika. Na koliko naˇcinov lahko pride turist iz Kopra v Dubrovnik?

Stevilo moˇˇ znih voˇzenj je enako 3 · 5 · 6 = 90.

Zgled 4: Koliko je vseh ˇstevil med 10000 in 100000, ki vsebujejo le ˇstevke 1,2 in 3?

Vsa ˇstevila kandidati so petmestna. Petmestno ˇstevilo pa lahko jemljemo kot (a₁, a₂, a₃, a₄, a₅), kjer je a₁ ∈ {1,2,3}, a₂ ∈ {1,2,3}, . . . , a₅ ∈ {1,2,3}. Vseh moˇznih ˇstevil je torej 3 · 3 · 3 · 3 · 3 = 3⁵ = 243.

Zgled 3: Iz Kopra peljejo 3 ladje v Poreˇc,iz Poreˇca pelje 5 ladij v Split, iz Splita pa 6 ladij do Dubrovnika. Na koliko naˇcinov lahko pride turist iz Kopra v Dubrovnik?

Stevilo moˇˇ znih voˇzenj je enako 3 · 5 · 6 = 90.

Zgled 4: Koliko je vseh ˇstevil med 10000 in 100000, ki vsebujejo le ˇstevke 1,2 in 3?

Vsa ˇstevila kandidati so petmestna. Petmestno ˇstevilo pa lahko jemljemo kot (a₁, a₂, a₃, a₄, a₅), kjer je a₁ ∈ {1,2,3}, a₂ ∈ {1,2,3}, . . . , a₅ ∈ {1,2,3}. Vseh moˇznih ˇstevil je torej 3 · 3 · 3 · 3 · 3 = 3⁵ = 243.

Zgled 5: Koliko je vseh 4-mestnih ˇstevil, ki vsebujejo 5 in imajo vse ˇstevke razliˇcne?

Mc 2

Nalogo reˇsimo tako, da najprej doloˇcimo koliko je ˇstevil, ki se zaˇcenjajo s 5:

Nalogo reˇsimo tako, da najprej doloˇcimo koliko je ˇstevil, ki se zaˇcenjajo s 5:fiksiramo 5 na zaˇcetek, na drugo mesto lahko postavimo 9 ˇstevk, na tretje mesto 8 ˇstevk, na ˇcetrto 7 ˇstevk, zato je vseh takih

9 · 8 · 7 = 504,

Nalogo reˇsimo tako, da najprej doloˇcimo koliko je ˇstevil, ki se zaˇcenjajo s 5:fiksiramo 5 na zaˇcetek, na drugo mesto lahko postavimo 9 ˇstevk, na tretje mesto 8 ˇstevk, na ˇcetrto 7 ˇstevk, zato je vseh takih

9 · 8 · 7 = 504, nato pa koliko je ˇstevil, ki se ne zaˇcenjajo s 5:

Nalogo reˇsimo tako, da najprej doloˇcimo koliko je ˇstevil, ki se zaˇcenjajo s 5:fiksiramo 5 na zaˇcetek, na drugo mesto lahko postavimo 9 ˇstevk, na tretje mesto 8 ˇstevk, na ˇcetrto 7 ˇstevk, zato je vseh takih

9 · 8 · 7 = 504,

nato pa koliko je ˇstevil, ki se ne zaˇcenjajo s 5:ˇce je 5 na drugem mestu, lahko na prvo mesto postavimo 8 ˇstevk (ˇstevke 0 ne smemo), na drugo prosto mesto zopet 8, za tretje prosto mesto pa imamo na voljo 7 ˇstevk: torej je vseh takih ˇstevil 8·8·7.

Nalogo reˇsimo tako, da najprej doloˇcimo koliko je ˇstevil, ki se zaˇcenjajo s 5:fiksiramo 5 na zaˇcetek, na drugo mesto lahko postavimo 9 ˇstevk, na tretje mesto 8 ˇstevk, na ˇcetrto 7 ˇstevk, zato je vseh takih

9 · 8 · 7 = 504,

nato pa koliko je ˇstevil, ki se ne zaˇcenjajo s 5:ˇce je 5 na drugem mestu, lahko na prvo mesto postavimo 8 ˇstevk (ˇstevke 0 ne smemo), na drugo prosto mesto zopet 8, za tretje prosto mesto pa imamo na voljo 7 ˇstevk: torej je vseh takih ˇstevil 8·8·7. Ce pa 5 prestavimo na tretjo oz. na ˇˇ cetro mesto v ˇstevilu, je vseh moˇznosti, ko ˇstevka 5 ni na zaˇcetku ˇstevila, enaka

3 · 8 · 8 · 7 = 1344.

Nalogo reˇsimo tako, da najprej doloˇcimo koliko je ˇstevil, ki se zaˇcenjajo s 5:fiksiramo 5 na zaˇcetek, na drugo mesto lahko postavimo 9 ˇstevk, na tretje mesto 8 ˇstevk, na ˇcetrto 7 ˇstevk, zato je vseh takih

9 · 8 · 7 = 504,

nato pa koliko je ˇstevil, ki se ne zaˇcenjajo s 5:ˇce je 5 na drugem mestu, lahko na prvo mesto postavimo 8 ˇstevk (ˇstevke 0 ne smemo), na drugo prosto mesto zopet 8, za tretje prosto mesto pa imamo na voljo 7 ˇstevk: torej je vseh takih ˇstevil 8·8·7. Ce pa 5 prestavimo na tretjo oz. na ˇˇ cetro mesto v ˇstevilu, je vseh moˇznosti, ko ˇstevka 5 ni na zaˇcetku ˇstevila, enaka

3 · 8 · 8 · 7 = 1344.

Skupaj je 504 + 1344 = 1848 4-mestnih ˇstevil z razliˇcnimi ˇstevkami, ki vsebujejo 5.

Mc 2

Zakaj smo uporabili pravilo vsote na koncu?

Mc 2

Posploˇsi nalogo: koliko je n-mestnih ˇstevil, ki vsebujejo ˇstevko 5 in imajo vse ˇstevke razliˇcne?

Posploˇsi nalogo: koliko je n-mestnih ˇstevil, ki vsebujejo ˇstevko 5 in imajo vse ˇstevke razliˇcne?

Rezultat: (8n + 1) · 8 · 7 · · ·(11 − n).

Mc 2

2.Permutacije (razporeditve)

2.Permutacije (razporeditve)

Naloga: Osebe A, B, C in D ˇzelimo posesti na 4 stole. Na koliko naˇcinov lahko to storimo?

2.Permutacije (razporeditve)

Naloga: Osebe A, B, C in D ˇzelimo posesti na 4 stole. Na koliko naˇcinov lahko to storimo?

(A, B, C, D), (A, B, D, C), (A, C, B, D), (A, C, D, B), (A, D, B, C), (A, D, C, B), (B, A, C, D), (B, A, D, C), (B, C, A, D), (B, C, D, A), (B, D, A, C), (B, D, C, A), (C, A, B, D), (C, A, D, B), (C, B, A, D), (C, B, D, A), (C, D, A, B), (C, D, B, A), (D, A, B, C), (D, A, C, B), (D, B, A, C), (D, B, C, A), (D, C, A, B), (D, C, B, A).

2.Permutacije (razporeditve)

Naloga: Osebe A, B, C in D ˇzelimo posesti na 4 stole. Na koliko naˇcinov lahko to storimo?

(A, B, C, D), (A, B, D, C), (A, C, B, D), (A, C, D, B), (A, D, B, C), (A, D, C, B), (B, A, C, D), (B, A, D, C), (B, C, A, D), (B, C, D, A), (B, D, A, C), (B, D, C, A), (C, A, B, D), (C, A, D, B), (C, B, A, D), (C, B, D, A), (C, D, A, B), (C, D, B, A), (D, A, B, C), (D, A, C, B), (D, B, A, C), (D, B, C, A), (D, C, A, B), (D, C, B, A).

Opazimo lahko, da gre za preslikave mnoˇzice Ω = {A, B, C, D}

nase.

2.Permutacije (razporeditve)

Naloga: Osebe A, B, C in D ˇzelimo posesti na 4 stole. Na koliko naˇcinov lahko to storimo?

(A, B, C, D), (A, B, D, C), (A, C, B, D), (A, C, D, B), (A, D, B, C), (A, D, C, B), (B, A, C, D), (B, A, D, C), (B, C, A, D), (B, C, D, A), (B, D, A, C), (B, D, C, A), (C, A, B, D), (C, A, D, B), (C, B, A, D), (C, B, D, A), (C, D, A, B), (C, D, B, A), (D, A, B, C), (D, A, C, B), (D, B, A, C), (D, B, C, A), (D, C, A, B), (D, C, B, A).

Opazimo lahko, da gre za preslikave mnoˇzice Ω = {A, B, C, D}

nase.

Mc 2

Drugaˇce povedano:na koliko naˇcinov se lahko dana mnoˇzica preslika nase?

Drugaˇce povedano:na koliko naˇcinov se lahko dana mnoˇzica preslika nase?

Koliko bijektivnih preslikav

f : Ω → Ω obstaja?

Mc 2

Preˇstejmo moˇznosti:

Mc 2

Preˇstejmo moˇznosti:

na prvem mestu imamo 4 moˇznosti: A ali B ali C ali D.

Mc 2

Preˇstejmo moˇznosti:

4

na prvem mestu imamo 4 moˇznosti: A ali B ali C ali D.

Mc 2

Preˇstejmo moˇznosti:

4

na prvem mestu imamo 4 moˇznosti: A ali B ali C ali D,

na drugem mestu imamo 3 moˇznosti (z izjemo tistega, ki smo ga fiksirali na prvem mestu).

Mc 2

Preˇstejmo moˇznosti:

4 3

na prvem mestu imamo 4 moˇznosti: A ali B ali C ali D,

na drugem mestu imamo 3 moˇznosti (z izjemo tistega, ki smo ga fiksirali na prvem mestu).

Mc 2

Preˇstejmo moˇznosti:

4 3

na prvem mestu imamo 4 moˇznosti: A ali B ali C ali D,

na drugem mestu imamo 3 moˇznosti (z izjemo tistega, ki smo ga fiksirali na prvem mestu),

na tretjem mestu nam ostanejo le 2 moˇznosti. . .

Mc 2

Preˇstejmo moˇznosti:

4 3 2

na prvem mestu imamo 4 moˇznosti: A ali B ali C ali D,

na drugem mestu imamo 3 moˇznosti (z izjemo tistega, ki smo ga fiksirali na prvem mestu),

na tretjem mestu nam ostanejo le 2 moˇznosti. . .

Mc 2

Preˇstejmo moˇznosti:

4 3 2

na prvem mestu imamo 4 moˇznosti: A ali B ali C ali D,

na drugem mestu imamo 3 moˇznosti (z izjemo tistega, ki smo ga fiksirali na prvem mestu),

na tretjem mestu nam ostanejo le 2 moˇznosti, na ˇcetrtem pa ena moˇznost.

Mc 2

Preˇstejmo moˇznosti:

4 · 3 · 2 · 1

na prvem mestu imamo 4 moˇznosti: A ali B ali C ali D,

na drugem mestu imamo 3 moˇznosti (z izjemo tistega, ki smo ga fiksirali na prvem mestu),

na tretjem mestu nam ostanejo le 2 moˇznosti, na ˇcetrtem pa ena moˇznost.

Vseh skupaj je torej po pravilu produkta

4 · 3 · 2 · 1 = 24.

Mc 2

Naj bo n naravno ˇstevilo. Oznaˇcimo z n! produkt n! = 1 · 2 · 3 · · ·(n − 1) · n.

Naj bo n naravno ˇstevilo. Oznaˇcimo z n! produkt n! = 1 · 2 · 3 · · ·(n − 1) · n.

Steviloˇ n! preberemo kot ’n faktorsko’, ’n fakulteta’ ali ’n faktoriel’.

Naj bo n naravno ˇstevilo. Oznaˇcimo z n! produkt n! = 1 · 2 · 3 · · ·(n − 1) · n.

Steviloˇ n! preberemo kot ’n faktorsko’, ’n fakulteta’ ali ’n faktoriel’.

Definiramo ˇse 0! = 1.

Naj bo n naravno ˇstevilo. Oznaˇcimo z n! produkt n! = 1 · 2 · 3 · · ·(n − 1) · n.

Steviloˇ n! preberemo kot ’n faktorsko’, ’n fakulteta’ ali ’n faktoriel’.

Definiramo ˇse 0! = 1.

Iz zadnjega zgleda sledi trditev

Stevilo permutacij mnoˇˇ zice z n elementi je enako P_n = n!.

Zgled 2.1 4! = 24,

Naj bo n naravno ˇstevilo. Oznaˇcimo z n! produkt n! = 1 · 2 · 3 · · ·(n − 1) · n.

Steviloˇ n! preberemo kot ’n faktorsko’, ’n fakulteta’ ali ’n faktoriel’.

Definiramo ˇse 0! = 1.

Iz zadnjega zgleda sledi trditev

Stevilo permutacij mnoˇˇ zice z n elementi je enako P_n = n!.

Zgled 2.1 4! = 24, 5! = 120, . . .

Naj bo n naravno ˇstevilo. Oznaˇcimo z n! produkt n! = 1 · 2 · 3 · · ·(n − 1) · n.

Steviloˇ n! preberemo kot ’n faktorsko’, ’n fakulteta’ ali ’n faktoriel’.

Definiramo ˇse 0! = 1.

Iz zadnjega zgleda sledi trditev

Stevilo permutacij mnoˇˇ zice z n elementi je enako P_n = n!.

Zgled 2.1 4! = 24, 5! = 120, . . .

Zgled 2.2 Oˇcitno velja n! = n(n − 1)!

Mc 2

Zgled 2.3 Izraˇcunaj:

(a) 6! − 4! =

Zgled 2.3 Izraˇcunaj:

(a) 6! − 4! = 720 − 24 = 696

Zgled 2.3 Izraˇcunaj:

(a) 6! − 4! = 720 − 24 = 696

(b) 15! − 14!

15! + 14! =

Zgled 2.3 Izraˇcunaj:

(a) 6! − 4! = 720 − 24 = 696

(b) 15! − 14!

15! + 14! =14!(15 − 1)

14!(15 + 1) = 14

16 = 7 8

Zgled 2.3 Izraˇcunaj:

(a) 6! − 4! = 720 − 24 = 696

(b) 15! − 14!

15! + 14! =14!(15 − 1)

14!(15 + 1) = 14

16 = 7 8

(c) (n − 1)! − n!

(n + 1)! + n! =

Zgled 2.3 Izraˇcunaj:

(a) 6! − 4! = 720 − 24 = 696

(b) 15! − 14!

15! + 14! =14!(15 − 1)

14!(15 + 1) = 14

16 = 7 8

(c) (n − 1)! − n!

(n + 1)! + n! =(n − 1)!(1 − n)

n!((n + 1) + 1) = 1 − n n(n + 2)

Mc 2

Zgled 2.4 Izraˇcunaj: Na polici imamo 3 leposlovne knjige, 4 slovarje in 2 stripa.

Na koliko naˇcinov lahko postavimo knjige na polico:

Zgled 2.4 Izraˇcunaj: Na polici imamo 3 leposlovne knjige, 4 slovarje in 2 stripa.

Na koliko naˇcinov lahko postavimo knjige na polico:

• pri poljubni razporeditvi

Zgled 2.4 Izraˇcunaj: Na polici imamo 3 leposlovne knjige, 4 slovarje in 2 stripa.

Na koliko naˇcinov lahko postavimo knjige na polico:

• pri poljubni razporeditvi

Vsako knjigo jemljemo kot element mnoˇzice, vse te elemente moramo permutirati:

(3 + 4 + 2)! = 9! = 362880

naˇcinov

Zgled 2.4 Izraˇcunaj: Na polici imamo 3 leposlovne knjige, 4 slovarje in 2 stripa.

Na koliko naˇcinov lahko postavimo knjige na polico:

• pri poljubni razporeditvi

Vsako knjigo jemljemo kot element mnoˇzice, vse te elemente moramo permutirati:

(3 + 4 + 2)! = 9! = 362880

naˇcinov

• ˇce morajo leposlovne knjige stati skupaj

Zgled 2.4 Izraˇcunaj: Na polici imamo 3 leposlovne knjige, 4 slovarje in 2 stripa.

Na koliko naˇcinov lahko postavimo knjige na polico:

• pri poljubni razporeditvi

Vsako knjigo jemljemo kot element mnoˇzice, vse te elemente moramo permutirati:

(3 + 4 + 2)! = 9! = 362880

naˇcinov

• ˇce morajo leposlovne knjige stati skupaj

Zgled 2.4 Izraˇcunaj: Na polici imamo 3 leposlovne knjige, 4 slovarje in 2 stripa.

Na koliko naˇcinov lahko postavimo knjige na polico:

• pri poljubni razporeditvi

Vsako knjigo jemljemo kot element mnoˇzice, vse te elemente moramo permutirati:

(3 + 4 + 2)! = 9! = 362880

naˇcinov

• ˇce morajo leposlovne knjige stati skupaj

Dejansko permutiramo le 7 enot (ena enota se sestoji iz 3 leposlovnih knjig, ki jih tudi v ’ovoju’

permutiramo med sabo), zato 7! · 3! = 30240 naˇcinov

• ˇce morata biti stripa na obeh koncih police

Zgled 2.4 Izraˇcunaj: Na polici imamo 3 leposlovne knjige, 4 slovarje in 2 stripa.

Na koliko naˇcinov lahko postavimo knjige na polico:

• pri poljubni razporeditvi

Vsako knjigo jemljemo kot element mnoˇzice, vse te elemente moramo permutirati:

(3 + 4 + 2)! = 9! = 362880

naˇcinov

• ˇce morajo leposlovne knjige stati skupaj

Dejansko permutiramo le 7 enot (ena enota se sestoji iz 3 leposlovnih knjig, ki jih tudi v ’ovoju’

permutiramo med sabo), zato 7! · 3! = 30240 naˇcinov

• ˇce morata biti stripa na obeh koncih police

Zgled 2.4 Izraˇcunaj: Na polici imamo 3 leposlovne knjige, 4 slovarje in 2 stripa.

Na koliko naˇcinov lahko postavimo knjige na polico:

• pri poljubni razporeditvi

Vsako knjigo jemljemo kot element mnoˇzice, vse te elemente moramo permutirati:

(3 + 4 + 2)! = 9! = 362880

naˇcinov

• ˇce morajo leposlovne knjige stati skupaj

Dejansko permutiramo le 7 enot (ena enota se sestoji iz 3 leposlovnih knjig, ki jih tudi v ’ovoju’

permutiramo med sabo), zato 7! · 3! = 30240 naˇcinov

• ˇce morata biti stripa na obeh koncih police

Fiksiramo oba stripa na obeh koncih, permutiramo preostalih 7 enot, hkrati pa lahko oba stripa zemenjata svoja poloˇzaja, zato 7! · 2! = 10080 naˇcinov

Mc 2

Zgled 2.5 Zgodba pravi, da je nek ˇclovek s svojimi sedmimi prijatelji veˇcerjal vsak dan v drugaˇcnem sedeˇznem redu. Obljubil jim je brezplaˇcno veˇcerjo prviˇc, ko bodo sedeli spet v zaˇcetnem sedeˇznem redu.

Zgled 2.5 Zgodba pravi, da je nek ˇclovek s svojimi sedmimi prijatelji veˇcerjal vsak dan v drugaˇcnem sedeˇznem redu. Obljubil jim je brezplaˇcno veˇcerjo prviˇc, ko bodo sedeli spet v zaˇcetnem sedeˇznem redu.

Ali bi prijatelji dobili brezplaˇcno veˇcerjo, ˇce bi sedeli za ravno mizo?

Zgled 2.5 Zgodba pravi, da je nek ˇclovek s svojimi sedmimi prijatelji veˇcerjal vsak dan v drugaˇcnem sedeˇznem redu. Obljubil jim je brezplaˇcno veˇcerjo prviˇc, ko bodo sedeli spet v zaˇcetnem sedeˇznem redu.

Ali bi prijatelji dobili brezplaˇcno veˇcerjo, ˇce bi sedeli za ravno mizo?

Kaj pa , ˇce bi bila miza okrogla?

Zgled 2.5 Zgodba pravi, da je nek ˇclovek s svojimi sedmimi prijatelji veˇcerjal vsak dan v drugaˇcnem sedeˇznem redu. Obljubil jim je brezplaˇcno veˇcerjo prviˇc, ko bodo sedeli spet v zaˇcetnem sedeˇznem redu.

Ali bi prijatelji dobili brezplaˇcno veˇcerjo, ˇce bi sedeli za ravno mizo?

Kaj pa , ˇce bi bila miza okrogla?

Vsak moˇznih sedeˇznih redov za ravno mizo, za katero sedi 8 ljudi, je 8! = 40320, kar pomeni, da bi ˇsele po veˇc kot 110 letih zopet sedeli tako, kot so prvikrat pri veˇcerji.

Zgled 2.5 Zgodba pravi, da je nek ˇclovek s svojimi sedmimi prijatelji veˇcerjal vsak dan v drugaˇcnem sedeˇznem redu. Obljubil jim je brezplaˇcno veˇcerjo prviˇc, ko bodo sedeli spet v zaˇcetnem sedeˇznem redu.

Ali bi prijatelji dobili brezplaˇcno veˇcerjo, ˇce bi sedeli za ravno mizo?

Kaj pa , ˇce bi bila miza okrogla?

Vsak moˇznih sedeˇznih redov za ravno mizo, za katero sedi 8 ljudi, je 8! = 40320, kar pomeni, da bi ˇsele po veˇc kot 110 letih zopet sedeli tako, kot so prvikrat pri veˇcerji.

Razporeditev 8 elementov v krogu je manj, le 7! = 5040, kar pomeni nekaj manj kot 14 let. . . Pojasnilo: ˇce se vsak za mizo premakne za en stol v desno, se razporeditev ohranja. Zato lahko do razultata pridemo tako, da fiksiramo enaga ostale pa permutiramo na sedmih stolih. . .

Mc 2

3.Permutacije s

ponavljanjem(razporeditve s

ponavljanjem)

3.Permutacije s

ponavljanjem(razporeditve s ponavljanjem)

Kot zgled poglejmo, koliko besed lahko dobimo iz besede ARARA.

3.Permutacije s

ponavljanjem(razporeditve s ponavljanjem)

Kot zgled poglejmo, koliko besed lahko dobimo iz besede ARARA.

AAARR AARAR ARAAR RAAAR RAARA

RRAAA ARRAA AARRA ARARA RAAAR

Mc 2

Ugotovimo lahko: do prve razporeditve AAARR pride dejansko veˇckrat kot je navedeno v seznamu (lahko zamenjamo med sabo ˇcrke A in zamenjamo med sabo ˇ

crke R), vendar te veˇckratnosti ne upoˇstevamo, saj med A in R ne razlikujemo.

Ugotovimo lahko: do prve razporeditve AAARR pride dejansko veˇckrat kot je navedeno v seznamu (lahko zamenjamo med sabo ˇcrke A in zamenjamo med sabo ˇ

crke R), vendar te veˇckratnosti ne upoˇstevamo, saj med A in R ne razlikujemo.

Za kolikokrat se ˇstevilo permutacij zmanjˇsa na raˇcun tega, da imamo enake elemente v seznamu?

Ugotovimo lahko: do prve razporeditve AAARR pride dejansko veˇckrat kot je navedeno v seznamu (lahko zamenjamo med sabo ˇcrke A in zamenjamo med sabo ˇ

crke R), vendar te veˇckratnosti ne upoˇstevamo, saj med A in R ne razlikujemo.

Za kolikokrat se ˇstevilo permutacij zmanjˇsa na raˇcun tega, da imamo enake elemente v seznamu?

Zaradi veˇckratnosti A je 3! manj permutacij kot bi jih bilo sicer,

Ugotovimo lahko: do prve razporeditve AAARR pride dejansko veˇckrat kot je navedeno v seznamu (lahko zamenjamo med sabo ˇcrke A in zamenjamo med sabo ˇ

crke R), vendar te veˇckratnosti ne upoˇstevamo, saj med A in R ne razlikujemo.

Za kolikokrat se ˇstevilo permutacij zmanjˇsa na raˇcun tega, da imamo enake elemente v seznamu?

Zaradi veˇckratnosti A je 3! manj permutacij kot bi jih bilo sicer, zaradi veˇckratnosti R je 2! manj permutacij kot bi jih bilo sicer.

Ugotovimo lahko: do prve razporeditve AAARR pride dejansko veˇckrat kot je navedeno v seznamu (lahko zamenjamo med sabo ˇcrke A in zamenjamo med sabo ˇ

crke R), vendar te veˇckratnosti ne upoˇstevamo, saj med A in R ne razlikujemo.

Za kolikokrat se ˇstevilo permutacij zmanjˇsa na raˇcun tega, da imamo enake elemente v seznamu?

Zaradi veˇckratnosti A je 3! manj permutacij kot bi jih bilo sicer, zaradi veˇckratnosti R je 2! manj permutacij kot bi jih bilo sicer.

Torej se mora ˇstevilo permutacij v naˇsem primeru ujemati s 5!

3!2!, kar je enako 10.

Ugotovimo lahko: do prve razporeditve AAARR pride dejansko veˇckrat kot je navedeno v seznamu (lahko zamenjamo med sabo ˇcrke A in zamenjamo med sabo ˇ

crke R), vendar te veˇckratnosti ne upoˇstevamo, saj med A in R ne razlikujemo.

Za kolikokrat se ˇstevilo permutacij zmanjˇsa na raˇcun tega, da imamo enake elemente v seznamu?

Zaradi veˇckratnosti A je 3! manj permutacij kot bi jih bilo sicer, zaradi veˇckratnosti R je 2! manj permutacij kot bi jih bilo sicer.

Torej se mora ˇstevilo permutacij v naˇsem primeru ujemati s 5!

3!2!, kar je enako 10.

Mc 2

Sploˇsno: ˇCe razporejamo n razliˇcnih objektov, med katerimi je k₁, k₂, . . . , k_r enakih, je ˇstevilo razporeditev teh elementov enako ˇstevilu permutacij s ponavljanjem

P_n^k1,k2,...,kr = n!

k₁! · k₂!· · ·k_r!

Opomba: ˇce se vsak element pojavi natanko enkrat, je k₁ = k₂ = . . . = k_r = 1, zato velja

P_n^1,1,...,1 = n!

1! · 1!· · ·1! = n! = P_n

Mc 2

Zgled 3.1 Koliko razliˇcnih besed dolˇzine 10 lahko sestavimo iz ˇcrk besede MATEMATIKA?

Zgled 3.1 Koliko razliˇcnih besed dolˇzine 10 lahko sestavimo iz ˇcrk besede MATEMATIKA?

V besedi se veˇckrat pojavi ˇcrka M (2 krat), ˇcrka A (3 krat), ˇcrka T(2 krat), zato P₁₀^2,3,2 = _2!·3!·2!^10! = 151200

Zgled 3.1 Koliko razliˇcnih besed dolˇzine 10 lahko sestavimo iz ˇcrk besede MATEMATIKA?

V besedi se veˇckrat pojavi ˇcrka M (2 krat), ˇcrka A (3 krat), ˇcrka T(2 krat), zato P₁₀^2,3,2 = _2!·3!·2!^10! = 151200

Koliko besed se ne zaˇcne z ˇcrko E?

Zgled 3.1 Koliko razliˇcnih besed dolˇzine 10 lahko sestavimo iz ˇcrk besede MATEMATIKA?

V besedi se veˇckrat pojavi ˇcrka M (2 krat), ˇcrka A (3 krat), ˇcrka T(2 krat), zato P₁₀^2,3,2 = _2!·3!·2!^10! = 151200

Koliko besed se ne zaˇcne z ˇcrko E?

Od vseh moˇznih permutacij s ponavljanjem odˇstejemo ˇstevilo tistih, katere se zaˇcno z E:

Zgled 3.1 Koliko razliˇcnih besed dolˇzine 10 lahko sestavimo iz ˇcrk besede MATEMATIKA?

V besedi se veˇckrat pojavi ˇcrka M (2 krat), ˇcrka A (3 krat), ˇcrka T(2 krat), zato P₁₀^2,3,2 = _2!·3!·2!^10! = 151200

Koliko besed se ne zaˇcne z ˇcrko E?

Od vseh moˇznih permutacij s ponavljanjem odˇstejemo ˇstevilo tistih, katere se zaˇcno z E:

P₁₀^2,3,2 − P₉^2,3,2 = 151200 − 15120 = 136080.

Zgled 3.1 Koliko razliˇcnih besed dolˇzine 10 lahko sestavimo iz ˇcrk besede MATEMATIKA?

V besedi se veˇckrat pojavi ˇcrka M (2 krat), ˇcrka A (3 krat), ˇcrka T(2 krat), zato P₁₀^2,3,2 = _2!·3!·2!^10! = 151200

Koliko besed se ne zaˇcne z ˇcrko E?

Od vseh moˇznih permutacij s ponavljanjem odˇstejemo ˇstevilo tistih, katere se zaˇcno z E:

P₁₀^2,3,2 − P₉^2,3,2 = 151200 − 15120 = 136080.

Zgled 3.1 Koliko razliˇcnih besed dolˇzine 10 lahko sestavimo iz ˇcrk besede MATEMATIKA?

V besedi se veˇckrat pojavi ˇcrka M (2 krat), ˇcrka A (3 krat), ˇcrka T(2 krat), zato P₁₀^2,3,2 = _2!·3!·2!^10! = 151200

Koliko besed se ne zaˇcne z ˇcrko E?

Od vseh moˇznih permutacij s ponavljanjem odˇstejemo ˇstevilo tistih, katere se zaˇcno z E:

P₁₀^2,3,2 − P₉^2,3,2 = 151200 − 15120 = 136080.

Zgled 3.2 Zelimo sestaviti veriˇˇ zico iz 4 kroglic bele barve, 3 kroglic ˇcrne bartve in 2 kroglic rumene barve. Koliko vzorcev je moˇznih:

Zgled 3.1 Koliko razliˇcnih besed dolˇzine 10 lahko sestavimo iz ˇcrk besede MATEMATIKA?

V besedi se veˇckrat pojavi ˇcrka M (2 krat), ˇcrka A (3 krat), ˇcrka T(2 krat), zato P₁₀^2,3,2 = _2!·3!·2!^10! = 151200

Koliko besed se ne zaˇcne z ˇcrko E?

Od vseh moˇznih permutacij s ponavljanjem odˇstejemo ˇstevilo tistih, katere se zaˇcno z E:

P₁₀^2,3,2 − P₉^2,3,2 = 151200 − 15120 = 136080.

Zgled 3.2 Zelimo sestaviti veriˇˇ zico iz 4 kroglic bele barve, 3 kroglic ˇcrne bartve in 2 kroglic rumene barve. Koliko vzorcev je moˇznih:

pri poljubni razporeditvi in ne loˇcujemo med kroglicami iste barve

Zgled 3.1 Koliko razliˇcnih besed dolˇzine 10 lahko sestavimo iz ˇcrk besede MATEMATIKA?

V besedi se veˇckrat pojavi ˇcrka M (2 krat), ˇcrka A (3 krat), ˇcrka T(2 krat), zato P₁₀^2,3,2 = _2!·3!·2!^10! = 151200

Koliko besed se ne zaˇcne z ˇcrko E?

Od vseh moˇznih permutacij s ponavljanjem odˇstejemo ˇstevilo tistih, katere se zaˇcno z E:

P₁₀^2,3,2 − P₉^2,3,2 = 151200 − 15120 = 136080.

Zgled 3.2 Zelimo sestaviti veriˇˇ zico iz 4 kroglic bele barve, 3 kroglic ˇcrne bartve in 2 kroglic rumene barve. Koliko vzorcev je moˇznih:

pri poljubni razporeditvi in ne loˇcujemo med kroglicami iste barve

Mc 2

Rezultat: P₉^4,3,2 = 9!

4! 3! 2! = 1260

pri poljubni razporeditvi in loˇcujemo med kroglicami iste barve

Rezultat: P₉^4,3,2 = 9!

4! 3! 2! = 1260

pri poljubni razporeditvi in loˇcujemo med kroglicami iste barve Rezultat: P₉ = 9! = 362880

Mc 2

4.Variacije (urejene izbire)

4.Variacije (urejene izbire)

Ponovitev: Permutacije: iz mnoˇzice z n elementi tvorimo nize iz vseh n elementov

4.Variacije (urejene izbire)

Ponovitev: Permutacije: iz mnoˇzice z n elementi tvorimo nize iz vseh n elementov

Variacije (brez ponavljanja): elemente iz mnoˇzice n elementov razporejamo na r mest, kjer je r < n.

4.Variacije (urejene izbire)

Ponovitev: Permutacije: iz mnoˇzice z n elementi tvorimo nize iz vseh n elementov

Variacije (brez ponavljanja): elemente iz mnoˇzice n elementov razporejamo na r mest, kjer je r < n.

Oznaka: V_n^r - ”variacije n elementov reda r”

4.Variacije (urejene izbire)

Ponovitev: Permutacije: iz mnoˇzice z n elementi tvorimo nize iz vseh n elementov

Variacije (brez ponavljanja): elemente iz mnoˇzice n elementov razporejamo na r mest, kjer je r < n.

Oznaka: V_n^r - ”variacije n elementov reda r”

Zgled 4.1: Koliko nizov dolˇzine 3 lahko sestavimo iz znakov

♥,♦,♠,♣, ˇ

ce se v nizu ne sme pojaviti doloˇceni znak veˇckrat?

Mc 2

Znak na prvem mestu izberemo izmed 4 moˇznosti, na drugem mestu izberemo znak iz preostalih treh moˇznosti, za tretje mesto nam preostaneta 2 znaka.

Znak na prvem mestu izberemo izmed 4 moˇznosti, na drugem mestu izberemo znak iz preostalih treh moˇznosti, za tretje mesto nam preostaneta 2 znaka.

Po osnovnem izreku kombinatorike je vseh moˇznosti 4 · 3 · 2 = 24.

Mc 2

Sploˇsno: ˇStevilo variacij n elementov reda r je V_n^r = n(n − 1)(n− 2)· · ·(n − r + 1) = n!

(n − r)!.

Sploˇsno: ˇStevilo variacij n elementov reda r je V_n^r = n(n − 1)(n− 2)· · ·(n − r + 1) = n!

(n − r)!.

Pokaˇzimo veljavnost formule:

Sploˇsno: ˇStevilo variacij n elementov reda r je V_n^r = n(n − 1)(n− 2)· · ·(n − r + 1) = n!

(n − r)!.

Pokaˇzimo veljavnost formule:To velja, ker imamo v prvi fazi izbire n moˇznosti,

Sploˇsno: ˇStevilo variacij n elementov reda r je V_n^r = n(n − 1)(n− 2)· · ·(n − r + 1) = n!

(n − r)!.

Pokaˇzimo veljavnost formule:To velja, ker imamo v prvi fazi izbire n moˇznosti,v drugi fazi ˇse n − 1 moˇznosti,

Sploˇsno: ˇStevilo variacij n elementov reda r je V_n^r = n(n − 1)(n− 2)· · ·(n − r + 1) = n!

(n − r)!.

Pokaˇzimo veljavnost formule:To velja, ker imamo v prvi fazi izbire n moˇznosti,v drugi fazi ˇse n − 1 moˇznosti, v tretji fazi n − 2 moˇznosti,. . . ,

Sploˇsno: ˇStevilo variacij n elementov reda r je V_n^r = n(n − 1)(n− 2)· · ·(n − r + 1) = n!

(n − r)!.

Pokaˇzimo veljavnost formule:To velja, ker imamo v prvi fazi izbire n moˇznosti,v drugi fazi ˇse n − 1 moˇznosti, v tretji fazi n − 2 moˇznosti,. . . ,v r-ti fazi pa n − (r − 1) = n − r + 1 izborov,

Sploˇsno: ˇStevilo variacij n elementov reda r je V_n^r = n(n − 1)(n− 2)· · ·(n − r + 1) = n!

(n − r)!.

Pokaˇzimo veljavnost formule:To velja, ker imamo v prvi fazi izbire n moˇznosti,v drugi fazi ˇse n − 1 moˇznosti, v tretji fazi n − 2 moˇznosti,. . . ,v r-ti fazi pa n − (r − 1) = n − r + 1 izborov, po pravilu produkta sledi V_n^r = n(n − 1)(n − 2)· · ·(n − r + 1) = _(n−r)!^n!

Sploˇsno: ˇStevilo variacij n elementov reda r je V_n^r = n(n − 1)(n− 2)· · ·(n − r + 1) = n!

(n − r)!.

Pokaˇzimo veljavnost formule:To velja, ker imamo v prvi fazi izbire n moˇznosti,v drugi fazi ˇse n − 1 moˇznosti, v tretji fazi n − 2 moˇznosti,. . . ,v r-ti fazi pa n − (r − 1) = n − r + 1 izborov, po pravilu produkta sledi V_n^r = n(n − 1)(n − 2)· · ·(n − r + 1) = _(n−r)!^n!

Zgled 4.2: Izmed 20 dijakov doloˇcimo enega dijaka, da pobere denar za fotokopije, enega, da pobere denar za izlet, enega, da pobere domaˇce naloge in enega, da napravi seznam vseh, ki se bodo udeleˇzili maturantskega plesa. (Izbrani dijak ne sme dobiti veˇc kot ene zadolˇzitve.)

Sploˇsno: ˇStevilo variacij n elementov reda r je V_n^r = n(n − 1)(n− 2)· · ·(n − r + 1) = n!

(n − r)!.

Pokaˇzimo veljavnost formule:To velja, ker imamo v prvi fazi izbire n moˇznosti,v drugi fazi ˇse n − 1 moˇznosti, v tretji fazi n − 2 moˇznosti,. . . ,v r-ti fazi pa n − (r − 1) = n − r + 1 izborov, po pravilu produkta sledi V_n^r = n(n − 1)(n − 2)· · ·(n − r + 1) = _(n−r)!^n!

Zgled 4.2: Izmed 20 dijakov doloˇcimo enega dijaka, da pobere denar za fotokopije, enega, da pobere denar za izlet, enega, da pobere domaˇce naloge in enega, da napravi seznam vseh, ki se bodo udeleˇzili maturantskega plesa. (Izbrani dijak ne sme dobiti veˇc kot ene zadolˇzitve.)

Oˇcitno izbiramo v mnoˇzici z 20 elementi 4 elemente (vrstni red izbire dijakov je

Mc 2

pomemben, saj npr. (d₁, d₃, d₅, d₉) 6= (d₉, d₃, d₅, d₁)).

pomemben, saj npr. (d₁, d₃, d₅, d₉) 6= (d₉, d₃, d₅, d₁)).

V₂₀⁴ = 20!

(20 − 4)! = 116280.

pomemben, saj npr. (d₁, d₃, d₅, d₉) 6= (d₉, d₃, d₅, d₁)).

V₂₀⁴ = 20!

(20 − 4)! = 116280.

Kaj pa, ˇce bi se v nizih elementi mnoˇzice, iz katere izbiramo, lahko ponavljali:

pomemben, saj npr. (d₁, d₃, d₅, d₉) 6= (d₉, d₃, d₅, d₁)).

V₂₀⁴ = 20!

(20 − 4)! = 116280.

Kaj pa, ˇce bi se v nizih elementi mnoˇzice, iz katere izbiramo, lahko ponavljali: (•₁) znaki ♥,♦,♠,♣ bi se v zgledu 4.1 pojavili veˇckrat v nizu; npr. niz ♥♥♠

(•₂) v zgledu 4.2 bi eden dijak lahko opravljal veˇc zadolˇzitev hkrati. . . ; npr.

(d₁, d₁, d₁, d₂₀)

pomemben, saj npr. (d₁, d₃, d₅, d₉) 6= (d₉, d₃, d₅, d₁)).

V₂₀⁴ = 20!

(20 − 4)! = 116280.

Kaj pa, ˇce bi se v nizih elementi mnoˇzice, iz katere izbiramo, lahko ponavljali: (•₁) znaki ♥,♦,♠,♣ bi se v zgledu 4.1 pojavili veˇckrat v nizu; npr. niz ♥♥♠

(•₂) v zgledu 4.2 bi eden dijak lahko opravljal veˇc zadolˇzitev hkrati. . . ; npr.

(d₁, d₁, d₁, d₂₀)

Postopek izbire ima spet veˇc faz:

pomemben, saj npr. (d₁, d₃, d₅, d₉) 6= (d₉, d₃, d₅, d₁)).

V₂₀⁴ = 20!

(20 − 4)! = 116280.

Kaj pa, ˇce bi se v nizih elementi mnoˇzice, iz katere izbiramo, lahko ponavljali: (•₁) znaki ♥,♦,♠,♣ bi se v zgledu 4.1 pojavili veˇckrat v nizu; npr. niz ♥♥♠

(•₂) v zgledu 4.2 bi eden dijak lahko opravljal veˇc zadolˇzitev hkrati. . . ; npr.

(d₁, d₁, d₁, d₂₀)

Postopek izbire ima spet veˇc faz:ˇstevilo moˇznosti izbire se ne zmanjˇsuje(ˇstevilo elementov, ki jih lahko izberemo v posamezni fazi, ostaja isto). . .

(•₁) v prvi fazi imamo 8 moˇznosti, prav tako v 2.,3.,4. fazi izbire. Po osnovnem

Mc 2

izreku kombinatorike je ˇstevilo neodvisnih izbir v teh ˇsterih fazah enako

izreku kombinatorike je ˇstevilo neodvisnih izbir v teh ˇsterih fazah enako 8 · 8 · 8 · 8 = 8⁴ = 4096.

(•₂) na vseh mestih izbire (,,,) imamo 20 kandidatov; vseh izbir je 20⁴ = 160000.

izreku kombinatorike je ˇstevilo neodvisnih izbir v teh ˇsterih fazah enako 8 · 8 · 8 · 8 = 8⁴ = 4096.

(•₂) na vseh mestih izbire (,,,) imamo 20 kandidatov; vseh izbir je 20⁴ = 160000.

Priˇsli smo do izbir r elementov iz n elementov, kjer se v poznajˇsih fazah izbira elementa

lahko ponovi. . .

Mc 2

5. Variacije s ponavljanjem(urejene

izbire s ponavljanjem)

5. Variacije s ponavljanjem(urejene izbire s ponavljanjem)

Definirajmo:

Variacije n elementov reda r s ponavljanjem oznaˇcimo kot ^(p)V_n^r in velja

(p)V_n^r = n^r.

Mc 2