Kombinatorika Irina Perfilieva
[email protected]
19. unora 2008 ´
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
Outline
1
ˇ kombinatoriky Pˇredmet ´ Zakladn´ ı kombinatoricke´ konfigurace
2
´ Dveˇ zakladn´ ı pravidla kombinatoriky
3
ˇ zakladn´ ´ Pocet ıch kombinatorickych ´ konfigurac´ı
4
Princip inkluze a exkluze
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
Outline
1
ˇ kombinatoriky Pˇredmet ´ Zakladn´ ı kombinatoricke´ konfigurace
2
´ Dveˇ zakladn´ ı pravidla kombinatoriky
3
ˇ zakladn´ ´ Pocet ıch kombinatorickych ´ konfigurac´ı
4
Princip inkluze a exkluze
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
ˇ kombinatoriky Pˇredmet
Co je kombinatorika ˇ ´ Vetev matematiky, ktera´ se zab´yva´ problemy sestaven´ı ´ ı) skupin prvku˚ koneˇcne´ mnoˇziny, se naz´yva´ (konfigurovan´ kombinatorika. Jista´ sestava nebo konfigurace prvku˚ koneˇcne´ mnoˇziny se naz´yva´ kombinatoricka´ konfigurace.
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
ˇ kombinatoriky Pˇredmet
Co je kombinatorika ˇ ´ Vetev matematiky, ktera´ se zab´yva´ problemy sestaven´ı ´ ı) skupin prvku˚ koneˇcne´ mnoˇziny, se naz´yva´ (konfigurovan´ kombinatorika. Jista´ sestava nebo konfigurace prvku˚ koneˇcne´ mnoˇziny se naz´yva´ kombinatoricka´ konfigurace.
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
Historie kombinatoriky
Historie kombinatoriky: ´ B. Pascale a Vznik kombinatoriky je spjat se jmeny P. (de) Fermata a jejich v´yzkumem v oblasti teorie her. ˇ G. Leibniz, kteremu ´ ˇ c´ıme za K dalˇs´ımu rozvoji pˇrispel vdeˇ slovo kombinatorika. ˇ J. Bernoulli pouˇzil kombinatoriku v teorii pravdepodobnosti. L. Euler je zakladatelem matematick´ych metod v´ypoˇctu ruzn´ ˚ ych kombinatorick´ych konfigurac´ı.
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
Historie kombinatoriky
Historie kombinatoriky: ´ B. Pascale a Vznik kombinatoriky je spjat se jmeny P. (de) Fermata a jejich v´yzkumem v oblasti teorie her. ˇ G. Leibniz, kteremu ´ ˇ c´ıme za K dalˇs´ımu rozvoji pˇrispel vdeˇ slovo kombinatorika. ˇ J. Bernoulli pouˇzil kombinatoriku v teorii pravdepodobnosti. L. Euler je zakladatelem matematick´ych metod v´ypoˇctu ruzn´ ˚ ych kombinatorick´ych konfigurac´ı.
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
Historie kombinatoriky
Historie kombinatoriky: ´ B. Pascale a Vznik kombinatoriky je spjat se jmeny P. (de) Fermata a jejich v´yzkumem v oblasti teorie her. ˇ G. Leibniz, kteremu ´ ˇ c´ıme za K dalˇs´ımu rozvoji pˇrispel vdeˇ slovo kombinatorika. ˇ J. Bernoulli pouˇzil kombinatoriku v teorii pravdepodobnosti. L. Euler je zakladatelem matematick´ych metod v´ypoˇctu ruzn´ ˚ ych kombinatorick´ych konfigurac´ı.
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
Historie kombinatoriky
Historie kombinatoriky: ´ B. Pascale a Vznik kombinatoriky je spjat se jmeny P. (de) Fermata a jejich v´yzkumem v oblasti teorie her. ˇ G. Leibniz, kteremu ´ ˇ c´ıme za K dalˇs´ımu rozvoji pˇrispel vdeˇ slovo kombinatorika. ˇ J. Bernoulli pouˇzil kombinatoriku v teorii pravdepodobnosti. L. Euler je zakladatelem matematick´ych metod v´ypoˇctu ruzn´ ˚ ych kombinatorick´ych konfigurac´ı.
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu ´ Zakladn´ ı kombinatoricke´ konfigurace
Permutace ´ ıme z koneˇcne´ mnoˇziny N s n prvky. Vychaz´ Permutace ´ an´ ´ ı teto ´ mnoˇziny. Permutace N je jedno moˇzne´ uspoˇrad Pˇr´ıklad Pro N = {a, b, c}, n = 3 (a, b, c) (a, c, b) (b, a, c) (b, c, a) (c, a, b) (c, b, a) jsou vˇsechny moˇzne´ permutace N = {a, b, c}. logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu ´ Zakladn´ ı kombinatoricke´ konfigurace
Permutace ´ ıme z koneˇcne´ mnoˇziny N s n prvky. Vychaz´ Permutace ´ an´ ´ ı teto ´ mnoˇziny. Permutace N je jedno moˇzne´ uspoˇrad Pˇr´ıklad Pro N = {a, b, c}, n = 3 (a, b, c) (a, c, b) (b, a, c) (b, c, a) (c, a, b) (c, b, a) jsou vˇsechny moˇzne´ permutace N = {a, b, c}. logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu ´ Zakladn´ ı kombinatoricke´ konfigurace
´ ım Permutace s opakovan´ ´ ım Permutace s opakovan´ ´ ım je uspoˇrad ´ an´ ´ ı skupiny z n prvku, Permutace s opakovan´ ˚ mezi nimiˇz je i1 stejn´ych prvku˚ prvn´ıho typu, i2 stejn´ych prvku˚ ´ druheho typu atd. aˇz ik stejn´ych prvku˚ k-ho typu, pˇriˇcemˇz i1 + i2 + · · · ik = n. Pˇr´ıklad Pro N = {a, a, b, c}, n = 4 a i1 = 2, i2 = 1, i3 = 1 jsou vˇsechny ´ ım: moˇzne´ permutace s opakovan´ (a, a, b, c) (a, a, c, b) (b, a, a, c) (c, a, a, b)
(a, b, a, c) (a, b, c, a) (a, c, a, b) (a, c, b, a) (b, a, c, a) (b, c, a, a) (c, a, b, a) (c, b, a, a).
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu ´ Zakladn´ ı kombinatoricke´ konfigurace
´ ım Permutace s opakovan´ ´ ım Permutace s opakovan´ ´ ım je uspoˇrad ´ an´ ´ ı skupiny z n prvku, Permutace s opakovan´ ˚ mezi nimiˇz je i1 stejn´ych prvku˚ prvn´ıho typu, i2 stejn´ych prvku˚ ´ druheho typu atd. aˇz ik stejn´ych prvku˚ k-ho typu, pˇriˇcemˇz i1 + i2 + · · · ik = n. Pˇr´ıklad Pro N = {a, a, b, c}, n = 4 a i1 = 2, i2 = 1, i3 = 1 jsou vˇsechny ´ ım: moˇzne´ permutace s opakovan´ (a, a, b, c) (a, a, c, b) (b, a, a, c) (c, a, a, b)
(a, b, a, c) (a, b, c, a) (a, c, a, b) (a, c, b, a) (b, a, c, a) (b, c, a, a) (c, a, b, a) (c, b, a, a).
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu ´ Zakladn´ ı kombinatoricke´ konfigurace
Variace ´ ıme z koneˇcne´ mnoˇziny N s n prvky. Vychaz´ Variace ´ Variace r -te´ tˇr´ıdy z n prvku˚ (r ≤ n) je uspoˇradan a´ sestava r prvku˚ z dan´ych n prvku˚ mnoˇziny N. Pˇr´ıklad Pro N = {a, b, c}, n = 3 a r = 2 (a, b) (a, c) (b, a) (b, c) (c, a) (c, b) jsou vˇsechny moˇzne´ variace 2. tˇr´ıdy ze 3 prvku. ˚ logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu ´ Zakladn´ ı kombinatoricke´ konfigurace
Variace ´ ıme z koneˇcne´ mnoˇziny N s n prvky. Vychaz´ Variace ´ Variace r -te´ tˇr´ıdy z n prvku˚ (r ≤ n) je uspoˇradan a´ sestava r prvku˚ z dan´ych n prvku˚ mnoˇziny N. Pˇr´ıklad Pro N = {a, b, c}, n = 3 a r = 2 (a, b) (a, c) (b, a) (b, c) (c, a) (c, b) jsou vˇsechny moˇzne´ variace 2. tˇr´ıdy ze 3 prvku. ˚ logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu ´ Zakladn´ ı kombinatoricke´ konfigurace
´ ım Variace s opakovan´ ´ ıme z koneˇcne´ mnoˇziny N s n prvky. Vychaz´ ´ ım Variace s opakovan´ ´ ım je variace, kde se Variace r -te´ tˇr´ıdy z n prvku˚ s opakovan´ prvky mohou opakovat. Pˇr´ıklad Pro N = {a, b, c}, n = 3 a r = 2 (a, a) (a, b) (a, c) (b, a) (b, b) (b, c) (c, a) (c, b) (c, c) ´ ım 2. tˇr´ıdy ze 3 prvku. jsou vˇsechny moˇzne´ variace s opakovan´ ˚
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu ´ Zakladn´ ı kombinatoricke´ konfigurace
´ ım Variace s opakovan´ ´ ıme z koneˇcne´ mnoˇziny N s n prvky. Vychaz´ ´ ım Variace s opakovan´ ´ ım je variace, kde se Variace r -te´ tˇr´ıdy z n prvku˚ s opakovan´ prvky mohou opakovat. Pˇr´ıklad Pro N = {a, b, c}, n = 3 a r = 2 (a, a) (a, b) (a, c) (b, a) (b, b) (b, c) (c, a) (c, b) (c, c) ´ ım 2. tˇr´ıdy ze 3 prvku. jsou vˇsechny moˇzne´ variace s opakovan´ ˚
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu ´ Zakladn´ ı kombinatoricke´ konfigurace
Kombinace ´ ıme z koneˇcne´ mnoˇziny N s n prvky. Vychaz´ Kombinace ´ Kombinace r -te´ tˇr´ıdy z n prvku˚ (r ≤ n) je neuspoˇradan a´ sestava r prvku˚ z dan´ych n prvku˚ mnoˇziny N. Pˇr´ıklad Pro N = {a, b, c}, n = 3 a r = 2 {a, b} {a, c} {b, c}. jsou vˇsechny moˇzne´ kombinace 2. tˇr´ıdy ze 3 prvku. ˚ logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu ´ Zakladn´ ı kombinatoricke´ konfigurace
Kombinace ´ ıme z koneˇcne´ mnoˇziny N s n prvky. Vychaz´ Kombinace ´ Kombinace r -te´ tˇr´ıdy z n prvku˚ (r ≤ n) je neuspoˇradan a´ sestava r prvku˚ z dan´ych n prvku˚ mnoˇziny N. Pˇr´ıklad Pro N = {a, b, c}, n = 3 a r = 2 {a, b} {a, c} {b, c}. jsou vˇsechny moˇzne´ kombinace 2. tˇr´ıdy ze 3 prvku. ˚ logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu ´ Zakladn´ ı kombinatoricke´ konfigurace
´ ım Kombinace s opakovan´ ´ ıme z koneˇcne´ mnoˇziny N s prvky n typu, Vychaz´ ˚ pˇriˇcemˇz ´ ´ mame nekoneˇcneˇ mnoho prvku˚ kaˇzdeho typu. ´ ım Kombinace s opakovan´ ´ ım je kombinace, Kombinace r -te´ tˇr´ıdy z n prvku˚ s opakovan´ kde se prvky mohou opakovat. Pˇr´ıklad Pro mnoˇzinu prvku˚ s typy a, b, c, n = 3 a r = 2 (a, a) (b, b) (c, c) (a, b) (a, c) (b, c) ´ ım 2. tˇr´ıdy ze 3 jsou vˇsechny moˇzne´ kombinace s opakovan´ prvku. ˚
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu ´ Zakladn´ ı kombinatoricke´ konfigurace
´ ım Kombinace s opakovan´ ´ ıme z koneˇcne´ mnoˇziny N s prvky n typu, Vychaz´ ˚ pˇriˇcemˇz ´ ´ mame nekoneˇcneˇ mnoho prvku˚ kaˇzdeho typu. ´ ım Kombinace s opakovan´ ´ ım je kombinace, Kombinace r -te´ tˇr´ıdy z n prvku˚ s opakovan´ kde se prvky mohou opakovat. Pˇr´ıklad Pro mnoˇzinu prvku˚ s typy a, b, c, n = 3 a r = 2 (a, a) (b, b) (c, c) (a, b) (a, c) (b, c) ´ ım 2. tˇr´ıdy ze 3 jsou vˇsechny moˇzne´ kombinace s opakovan´ prvku. ˚
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
Outline
1
ˇ kombinatoriky Pˇredmet ´ Zakladn´ ı kombinatoricke´ konfigurace
2
´ Dveˇ zakladn´ ı pravidla kombinatoriky
3
ˇ zakladn´ ´ Pocet ıch kombinatorickych ´ konfigurac´ı
4
Princip inkluze a exkluze
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
ˇ ˇ Pravidla soucinu a souctu
ˇ Pravidlo soucinu ´ ˇ A a pak dalˇs´ıch m moˇznost´ı pro Mame-li n moˇznost´ı pro v´yber ˇ B, potom v´yber ˇ uspoˇradan ´ v´yber e´ dvojice (A, B) se uskuteˇcn´ı n · m moˇznostmi. Example ˇ Poˇcet K dvoucifern´ych cˇ ´ısel deliteln´ ych 2: K = 9 · 5 = 45.
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
ˇ ˇ Pravidla soucinu a souctu
ˇ Pravidlo souctu ´ ˇ A a pak nezavisle ´ Mame-li n moˇznost´ı pro v´yber m dalˇs´ıch ˇ B, potom v´yber ˇ A nebo B se uskuteˇcn´ı moˇznost´ı pro v´yber n + m moˇznostmi. Example ˇ Poˇcet K cˇ ´ısel od 1 do 99 deliteln´ ych 2: ˇ A: jednociferne´ cˇ ´ıslo deliteln e´ 2 ˇ B: dvouciferne´ cˇ ´ıslo deliteln e´ 2 KA = 4
KB = 9 · 5 = 45 K = KAneboB = 4 + 45 = 49
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
Outline
1
ˇ kombinatoriky Pˇredmet ´ Zakladn´ ı kombinatoricke´ konfigurace
2
´ Dveˇ zakladn´ ı pravidla kombinatoriky
3
ˇ zakladn´ ´ Pocet ıch kombinatorickych ´ konfigurac´ı
4
Princip inkluze a exkluze
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
ˇ permutac´ı, variac´ı, kombinac´ı Pocet
ˇ permutac´ı mnoˇziny s n prvky Pocet Pn = n · (n − 1) · . . . · 1 = n!
´ faktorial
Napˇr´ıklad pro n = 3: P3 = 3 · 2 · 1 = 6.
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
ˇ permutac´ı, variac´ı, kombinac´ı Pocet
ˇ permutac´ı s opakovan´ ´ ım mnoˇziny s n prvky Pocet Pni1 ,...,ik =
n! i1 ! · · · ik !
Napˇr´ıklad pro n = 4,i1 = 2,i2 = 1,i3 = 1: P32,1,1 =
4! 24 = = 12. 2!1!1! 2·1·1
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
ˇ permutac´ı, variac´ı, kombinac´ı Pocet
ˇ variac´ı r -te´ tˇr´ıdy z n prvku˚ Pocet Vnr = V (n, r ) = n · (n − 1) · . . . · (n − r + 1) =
n! (n − r )!
Napˇr´ıklad pro n = 3, r = 2: V32 = 3 · 2 = 6.
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
ˇ permutac´ı, variac´ı, kombinac´ı Pocet
ˇ variac´ı r -te´ tˇr´ıdy z n prvku˚ s opakovan´ ´ ım Pocet ˜ r = n · n · . . . · n = nr V n | {z } r
Napˇr´ıklad pro n = 3, r = 2:
˜2 V 3
= 32 = 9.
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
ˇ permutac´ı, variac´ı, kombinac´ı Pocet
ˇ kombinac´ı r -te´ tˇr´ıdy z n prvku˚ Pocet Cnr · r ! = Vnr Vr n! n · (n − 1) · . . . · (n − r + 1) Cnr = n = = r! r !(n − r )! r! Napˇr´ıklad pro n = 3, r = 2: C32 =
3·2 1·2
= 3.
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
ˇ permutac´ı, variac´ı, kombinac´ı Pocet
ˇ kombinac´ı r -te´ tˇr´ıdy z n prvku˚ s opakovan´ ´ ım Pocet ˜ r = Cr C n n+r −1 ˜ 2 = C2 = Napˇr´ıklad pro n = 3, r = 2: C 3 4
4·3 1·2
= 6.
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
ˇ ıch c´ ˇ ısel Vlastnosti kombinacn´
Cnk = Cnn−k k+1 Cnk + Cnk +1 = Cn+1
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
ˇ ıch c´ ˇ ısel Vlastnosti kombinacn´
Cnk = Cnn−k k+1 Cnk + Cnk +1 = Cn+1
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
Outline
1
ˇ kombinatoriky Pˇredmet ´ Zakladn´ ı kombinatoricke´ konfigurace
2
´ Dveˇ zakladn´ ı pravidla kombinatoriky
3
ˇ zakladn´ ´ Pocet ıch kombinatorickych ´ konfigurac´ı
4
Princip inkluze a exkluze
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
Princip inkluze a exkluze ´ ˇ u˚ a vlastnosti A1 , . . . , Ak . Pˇredpoklad: Mame N pˇredmet Oznaˇcme: ˇ u˚ s vlastnost´ı Ai , i = 1, . . . , k; Ni – poˇcet pˇredmet ˇ u˚ s vlastnostmi Ai , Aj , i, j = 1, . . . , k; Nij – poˇcet pˇredmet atd. ˇ u˚ s vlastnostmi Ai1 , . . . , Ail . Ni1 ,...il – poˇcet pˇredmet ˆ 0 pˇredmet ˇ u˚ nemaj´ıc´ıch ani jednu z vlastnost´ı Potom poˇcet N A1 , . . . , Ak se rovna´ ˆ 0 = N − S1 + S2 − · · · + (−1)k Sk , N kde Sl =
X 1
Ni1 ,...il ,
l = 1, . . . , k logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
Demonstrace principu inkluze a exkluze
Ve skupineˇ je 25 studentu. ˚ Z nich 20 ukonˇcilo semestr ˇ sne, ˇ 12 navˇstevuje ˇ usp sportovn´ı klub, pˇriˇcemˇz 10 z nich ´ eˇ ˇ sne. ˇ Kolik neusp ˇ sn´ych studentu˚ ukonˇcilo semestr usp ´ eˇ ´ eˇ nechod´ı do sportovn´ıho klubu? ˇ sen´ ˇ ı: Re N1 = 20, N2 = 12, N12 = 10, ˆ 0 = 25 − (20 + 12) + 10 = 3. N
logo
ˇ kombinatoriky Dveˇ zakladn´ ´ ˇ zakladn´ ´ Pˇredmet ı pravidla kombinatoriky Pocet ıch kombinatorickych ´ konfigurac´ı Princip inklu
Demonstrace principu inkluze a exkluze
Ve skupineˇ je 25 studentu. ˚ Z nich 20 ukonˇcilo semestr ˇ sne, ˇ 12 navˇstevuje ˇ usp sportovn´ı klub, pˇriˇcemˇz 10 z nich ´ eˇ ˇ sne. ˇ Kolik neusp ˇ sn´ych studentu˚ ukonˇcilo semestr usp ´ eˇ ´ eˇ nechod´ı do sportovn´ıho klubu? ˇ sen´ ˇ ı: Re N1 = 20, N2 = 12, N12 = 10, ˆ 0 = 25 − (20 + 12) + 10 = 3. N
logo
