KOMBINATORIKA
Cíle: 1. Ovládat pojmy faktoriál, kombinační číslo, umět aktivně využít vlastností
kombinačních čísel, Pascalův trojúhelník včetně příslušné terminologie a
symboliky.
2. Chápat správně pojmy variace, permutace, kombinace a to bez opakování i
s opakováním. Aktivně ovládat vzorce pro počty těchto skupin.
3. Umět řešit kombinatorické úlohy včetně užití kombinatorických pravidel součtu a
součinu.
4. Aktivně ovládat binomickou větu.
Podnět pro kombinatorické úvahy byly v 17. století různé hry s kostkami a hry karetní.
Jednalo se o určení pravděpodobnosti výhry.
Dnes je součástí finitní matematiky, která sleduje vlastnosti konečných množin.
Nelze ověřit výsledek, práce v množině přirozených čísel /kromě nuly/.
,,Kolika způsoby lze vybrat, seřadit, uspořádat jisté objekty?" Takové úlohy se
kombinatorika snaží roztřídit do skupin či typů a pro každý typ úlohy formuluje obecnou
metodu řešení ­ například v podobě vzorce.
Motivační úloha: Určete počet přirozených dvojciferných čísel, v jejichž dekadickém zápisu
se každá, vyskytuje nejvýše jednou.
Řešení: na místě desítek se vyskytují postupně cifry 1 ­ 9 , ke každé z nich lze
z množiny 0 , 1 , 2 .............9 vytvořit všechna dvojciferná čísla tak , že
se cifry neopakují
1 krát 9 zbývajících
2 krát 9 zbývajících
3 krát 9 zbývajících
atd.
celkem tedy vytvořím 9 . 9 = 81 čísel
Aniž si uvědomujeme použili jsme k řešení první z kombinatorických pravidel ­
pravidlo součinu.
KOMBINATORICKÁ PRAVIDLA
Předcházející jednoduchá úloha vede k zavedení kombinatorického pravidla součinu:
Předpokládejme, že máme vybrat dva prvky a,b přičemž vybíráme první z konečné
neprázdné množiny A a druhý z konečné neprázdné množiny B. V případě, že výběr
prvku b je nezávislý na výběru prvku a, je celkem A . B možností, jak vybrat tyto prvky.
Jedná se tedy o počet všech uspořádaných k-tic, jejichž první člen lze vybrat n1
způsoby, druhý n2 způsoby po výběru prvního, ........., každý k-tý člen n1 , n2 ,...,nk způsoby
po výběru ( k ­ 1) ho členu.Tento počet je roven součinu n1 . n2 . .....nk
Kombinatorickým pravidlem součinu lze řešit většinu kombinatorických úloh, řešení
je však zdlouhavé.
Jestliže je úkolem zjistit počet prvků nějaké množiny M, můžeme množinu M
rozložit na několik disjunktních podmnožin , M = M1 + M2 + .............+ Mk, a určit počty
prvků množin Mj. Tím je zavedeno kombinatorické pravidlo součtu.
Tento počet je roven |M| = |M1| + |M2| + |M3| +...........+ |Mk|
Pro řešení úloh nejen těmito pravidly je nutné definovat nejzákladnější pojem
kombinatoriky a to faktoriál.
Faktoriál čísla n je součin přirozených čísel 1 až n a značíme jej vykřičníkem
za daným číslem , obecně n!.
Matematicky to nejsnáze zapíšeme jaksi odzadu, tedy takto :
n! = n(n ­ 1)( n ­ 2 )( n ­ 3 ). . . 3 . 2 . 1
Nula není přirozené číslo, ale pokud jsme nuceni vyjádřit v některém vztahu 0! ,
definujeme ji jako 1. Přitom chceme- li faktoriál rozložit jen částečně, můžeme kdykoli
přestat a poslední člen zase považovat za faktoriál tedy, např.:
n! = n(n ­ 1 )( n ­ 2 )!
Na základě toho je možné určit faktoriál složitějších příkladů.
1. Rozložte ( n + 1 )!
Např. ( n + 1)! = ( n + 1)( n )( n ­1)( n ­ 2 )!
2. Dokažte , že platí ( n + 1 )! - n! = n . n!
Řešení : provedeme rozklad ( n + 1 )!
( n + 1 ).n! ­ n! = n.n!
vlevo vytkneme n!
n!.( n + 1 ­1 ) = n.n!
po úpravě dostáváme
n.n! = n.n!
Je důležité si zapamatovat, že faktoriál je pouze symbol, který sám o sobě
nelze ani vytknout ani vykrátit, zrovna tak jako s ním nelze například roznásobit
závorku.
Při výskytu faktoriálů ve zlomku rozvádíme větší výraz tak dlouho, dokud se
neobjeví dva stejné výrazy v čitateli i ve jmenovateli, které pak můžeme vykrátit.
Sledujte úpravy následujících zlomků.
Procvičte si :
1. V četě je dvanáct vojáků. Kolik různých dvojčlenných hlídek z nich lze
sestavit , jestliže první z dvojice má být velitelem?
( 132)
2. Je dán čtverec ABCD a na každé jeho straně n vnitřních bodů. Určete
počet všech trojúhelníků XYZ ,jejichž vrcholy leží v daných bodech a na
různých stranách čtverce ABCD.
( 1/6(4n.3n.2n)=4n)
3. Upravte
( )
( )
( )
( ) ( )
( ) ( )
(2)
!2
!
!1
!12
!
!2n
c)
(1)
!1
!
!
!1n
b)
)(n!!!1n)
-
+
-
+
-
+
-
-
+
-+
n
n
n
n
n
n
n
n
nna
Obecné metody řešení - základní typy kombinatorických úloh
Skupiny
1. Bez opakování 2.S opakováním
a/ záleží na pořadí: a/záleží na pořadí
-variace -variace
-permutace -permutace
b/nezáleží na pořadí: b/nezáleží na pořadí
-kombinace -kombinace
Skupiny bez opakování
VARIACE bez opakování
základní formulace úlohy: ,,Kolik uspořádaných k-tic lze vytvořit z n prvků?
,,Kolika způsoby lze z n objektů vybrat kn objektů,jestliže záleží
na pořadí výběru?"
Variace je počet možností sestavení k skupin z n různých prvků, kde záleží na pořadí
prvků v každé skupině, avšak prvky se vyskytují nejvýše jednou.
Počet variací označujeme V(k,n) =
( )!
!
kn
n
-
kN , nN , 1 k  n
Vzorové úlohy:
1.Najděte všechna trojmístná čísla vytvořená z číslic 1 až 6, aniž by se číslice opakovaly.
Řešení: sestavujeme skupiny 3 čísel, v nichž je jasné, že záleží na pořadí, protože např. číslo
246 není totéž jako 642
V(3,6) = 120
2. Kolik jedno až trojciferných čísel lze vytvořit z číslic 0 , 1 , 2 ,...,9,jestliže se cifry
vyskytují nejvýše jednou.
Řešení:
n = { 0,1,2,3,4,5,6,7,8,9 } n = 10
k: 1,2,3
jednociferná V(1,10) = 10
dvojciferná 1 . 9 zbývajících /kromě 1/
2 . 9 zbývajících /kromě 2/
.......
0 . 9 ­ nelze ,tím bychom vytvořili jednociferná čísla
celkem dvojciferných V(2,10) - V(1,9) /odečteme ta čísla, která začínají nulou/
V(2,10) - V(1,9) = 81
trojciferná /postup se opakuje, od celkového počtu musíme odečíst čísla
začínající nulou, ta by byla dvojciferná/
V(3,10) - V(2,9) = 648
celkem všech : V(1,10) + V(2,10) ­ V(1,9) + V(3,10) ­ V(2,9) = 739
3. Kolik různých umístění může být na prvních třech místech při hokejovém mistrovství,
jestliže se ho účastní 8 družstev?
Řešení: - při umístění záleží na pořadí, nelze aby družstvo bylo první a zároveň třetí
- jedná se tedy o variace bez opakování třetí třídy z osmi
V(3,8) = 336
Procvičte si:
1. Kolik trojciferných přirozených čísel dělitelných pěti lze sestavit z číslic 1,2,3,4,5
jestliže se číslice neopakují?
(12)
2. Kolika způsoby zvolíte třídní výbor, který se skládá z předsedy, pokladníka a
referenta, je-li ve třídě 20 žáků?
V(3,20)
PERMUTACE bez opakování
základní formulace úlohy : ,,Kolika způsoby lze seřadit do řady prvky konečné
neprázdné n ­ prvkové množiny?"
Permutací n prvků, rozumíme skupiny všech n prvků, uspořádaných v každém možném
pořadí.
Počet permutací označujeme P(n,n) =
( )
10!;
!0
!
!
!
===
-
n
nn
n
P(n,n) = n!
Permutace je zvláštní případ variace kde n=k.
Vzorové úlohy:
1. Kolika způsoby lze rozsadit pět hostů do pěti křesel?
Řešení:
- hledáme 5-ti prvkové množiny z 5-ti prvků
P(5) = 5! = 120
2. Kolika způsoby lze vedle sebe uložit šest různých knih?
Řešení:
- máme najít šestiprvkové množiny
P(6) = 6! = 720
3. Vozy tvoří kolonu takto ­ 2 vozy škoda, 3 vozy opel, 4 vozy fiat. Kolika způsoby
lze seřadit kolonu jestliže jsou stejná vozidla za sebou?
- jedná se o uspořádané trojice ! P(3) = 3! = 6
Procvičte si:
1. Kolik různých šesticiferných přirozených čísel lze napsat pomocí číslic
1,2,3,4,5,6.jestliže se číslice neopakují?
( P(6) = 720)
2. Kolika způsoby může stát za sebou pět vojáků ABCDE tak, aby
a/ voják A byl první a voják E poslední ( P(3)=6)
b/ vojáci CDE stáli za sebou v libovolném pořadí ( P(3).P(3)=36)
3. S připomínkami k navrhovanému zákonu chce v parlamentě vystoupit šest
poslanců, určete počet všech možných pořadí jejich vystoupení.
( P(6)= 720)
KOMBINACE bez opakování
základní formulace úlohy: "Kolika způsoby lze z n různých objektů vybrat k ( k n )
objektů, nezáleží-li na pořadí výběru?"
,, Kolik k-prvkových podmnožin má n-prvková množina?"
Kombinace je počet všech sestavených k skupin z n prvků,kde nezáleží na pořadí.
Platí:
V(k,n ) = k! K( k,n )
Celý postup ilustruje schéma pro 2členné variace ze tří prvků a , b , c.
2členné variace z prvků a , b , c
( a,b ) ( c,b ) ( a,c )
( b,a ) ( b,c ) ( c,a ) => V(2,3) = 6
  
( a,b ) ( b,c ) ( a,c ) => K(2,3) = 3
závěr: V(2,3) = 2! K(2,3)
Počet kombinací označujeme K( k,n ) =
( )!!
!
knk
n
-
Tento výraz se v kombinatorice vyskytuje velmi často, proto je pro něj zaveden
zvláštní symbol ( čte se ,, n nad k ,,) a nazývá se kombinační číslo. Vzhledem k významu je
mu věnována zvláštní kapitola, kde se dozvíte jaké vlastnosti toto číslo má.
Příkladem kombinací bez opakování je třeba počet možností telefonního spojení mezi dvěma
skupinami deseti účastníků tak , aby každý vždy hovořil pouze s jedním ze skupiny, a přitom
jsou k dispozici jen 3 telefonní linky. Počet prvků je zde počet účastníků ve skupině / každou
linkou jsou spojeni dva účastníci současně/ , třídu tvoří počet linek ­ tedy
Řešení:
n = 10 , k = 3 K( 3,10 ) = 120
Vzorové úlohy:
1. Na polici je 40 knih. Kolika způsoby lze vybrat dvě?
Řešení:
n = 40
k = 2 - nezáleží na pořadí výběru K( 2,40 ) = 780
2. V rovině je dáno 24 různých bodů, z nichž žádné tři body neleží na téže přímce. Vypočtěte,
kolik je těmito body určeno : a/ přímek
b/ trojúhelníků
Řešení:
ad a/ přímka je jednoznačně určena dvěma body nebo-li hledáme dvojice z 24 prvků
k = 2 , n = 24 , nezáleží na pořadí K( 2,24 ) = 12.23 = 276
Představme si, že ze 24 bodů právě 6 umístíme na jednu přímku.
- musíme pak vyjít z celkového počtu přímek a od něj odečíst ty, které by mohlo
tvořit těchto 6 bodů
- nezapomínáme na tu jedinou přímku na níž leží těchto šest bodů
pro výpočet pak platí : K( 2,24 ) - K( 2,6 ) + 1
ad b/ trojúhelník tvoří rovinu a ta je dána 3 body, nebo-li hledáme trojice z 24 prvků
k = 3
, n = 24 , nezáleží na pořadí K( 3,24 ) = 23.22.4 =
3. Určete kolika způsoby je možno ze sedmi mužů a čtyř žen vybrat šestičlennou skupinu,
v níž jsou: a/ právě dvě ženy
b/ aspoň dvě ženy
ad a/ - pro šestičlennou skupinu lze dvě ženy ze čtyř vybrat K(2,4) způsoby,
zbývající čtyři muže ze sedmi K(4,7) způsoby
- podle kombinatorického pravidla součinu je možno skupinu utvořit K( 2,4 ) .
K( 4,7 ) = 210 způsoby
ad b/ - má-li šestičlenná skupina obsahovat aspoň dvě ženy, obsahuje právě dvě,
anebo právě tři, anebo právě čtyři ženy
- počet způsobů jak lze skupinu utvořit je
K( 2,4 ).K( 4,7 ) + K( 3,4 ).K( 3,7 ) + K( 4,4 ).K( 2,7 ) = 371 způsobů
4. Je dáno n bodů , z nichž žádné ze čtyř neleží v jedné rovině, určete počet rovin.
- rovina je dána 3 body , tzn. že k = 3
- vybíráme trojice z n bodů, u nichž nezáleží na pořadí
K( 3,n ) =
Procvičte si:
1. Petr má sedm knih, o které se zajímá Ivana, Ivana má deset knih, o které se zajímá
Petr. Určete , kolika způsoby si Petr může vyměnit své dvě knihy za dvě Ivaniny.
(K(2,7).K(2,10)=945)
2. Určete, kolika způsoby může m chlapců a n dívek utvořit taneční pár.
(K(1,m).K(1,n)= m.n)
3. Určete kolika způsoby je možno ze dvaceti osob vybrat deset, požadujeme-li aby
mezi vybranými a/ nebyl pan A (K(10,19))
b/ nebyli zároveň pánové A, (K(10,20)-K(8,18))
c/ byl aspoň jeden z pánů A,B (2K(9,18)+K(8,18))
Skupiny s opakováním
Variace s opakováním
základní formulace úlohy:" Kolika způsoby lze z daných n objektů vybrat k objektů, jestliže
záleží na pořadí vybírání a připustíme-li,že objekty mohou být
vybírány vícekrát?"
Každý takový výběr nazýváme k-prvkovou variací s opakováním z n prvků.
- uvědomíme si pojem ,,variace" a dodejme, že prvky se mohou opakovat
- toto opakování je potřebné k sestavování číselných skupin
motivační úloha: Najděte počet variací skupin trojmístných čísel z číslic 1 až 6 jestliže.
a/ číslice se neopakují
Řešení:
- zde se jedná o čistou variaci bez opakování V( 3,6 ) = 120
b/ číslice se opakují
Řešení:
- lze vytvořit čísla 1 1-6 1-6 (přiřadí)
2
3
.
.
6 1-6 1-6
---------------
6 . 6 . 6 pro výpočet platí 6 . 6 . 6 = 63
šest možností na místě stovek, desítek, jednotek
Pro variaci s opakováním platí V`( k,n) = nk
Vzorové úlohy:
1. Určete,kolik značek Morseovy abecedy lze utvořit sestavením teček a čárek do skupin o
jednom až třech prvcích.
Řešení:
- Morseova abeceda obsahuje jako prvky tečku a čárku, n=2
- v sestavování se tedy prvky opakují, ale stále záleží na pořadí/ význam abecedy/
- skupiny tedy mohou obsahovat stejné prvky, k = 1 , 2 , 3
Pro výpočet platí: V`(1,2) + V`(2,2)+V`(3,2) = 2 + 2 + 2 = 14
2. V jisté zemi je státní poznávací značka tvořena uspořádanou sedmicí , jejíž první tři členy
jsou písmena a další čtyři číslice.Určete, kolik poznávacích značek mají k dispozici,
mohou-li pro první část značky použít každé z 28 písmen.
Řešení
- první část značky je uspořádaná trojice vybraná z 28 písmen, která se mohou
opakovat
- jejich počet je V`( 3,28) = 28
- druhá část značky je uspořádaná čtveřice vybraná z deseti číslic, které se také mohou
opakovat
- jejich počet je V`( 4,10) = 10000
- podle kombinatorického pravidla součinu pak platí
V`( 3,28 ) . V`( 4,10 ) = 28 . 10000 = 219 520 000 poznávacích značek
3. Kolik různých telefonních stanic lze zapojit na telefonní centrálu, jestliže jsou všechna
čísla stanic pěticiferná?Kolik může být těchto stanic, předpokládáme-li, že číslo nemůže
začínat číslicí 0?
Řešení:
- čísla telefonních stanic jsou uspořádané pětice tvořené z deseti číslic
- jejich počet je proto počet variací s opakováním páté třídy z deseti prvků
V`( 5,10 ) = 100 000
- pěticiferných čísel, která začínají číslicí 0, je tolik, kolik je variací s opakováním
čtvrté třídy z deseti prvků
- jejich počet je V`( 4,10 ) = 10 000
- počet stanic , jejichž číslo nezačíná číslicí 0, je
V`( 5,10 ) ­ V`( 4,10 ) = 100 000 ­ 10 000 = 90 000
Procvičte si:
1. Kolik různých čtyřciferných čísel lze sestavit z číslic 5 , 6 , 8?
( V`(4,3))
2. Hodíme třemi hracími kostkami ­ bílou,modrou a žlutou. Kolik různých výsledků
dostaneme?
( V`(3,6))
3.Kufřík má heslový zámek, který se otevře , když na každém z pěti kotoučů
nastavíme správnou číslici.Těchto číslic je na každém kotouči devět.Určete počet
pokusů, které je nutno provést, chceme-li kufřík otevřít jestliže jsme zapomněli
heslo.
( V`(5,9))
Permutace s opakováním
základní formulace úlohy: ,,Mějme k1 objektů prvního druhu,k2 objektů druhého
druhu......atd. až kk objektů k-tého druhu.Kolika
způsoby lze těchto k1+k2+...+kk objektů uspořádat
do řady?"
Každé takové uspořádání nazýváme permutace s opakováním a jejich celkový
počet označujeme P`(k1,k2,k3,.........kk) a vypočteme
P`(
Vzorové úlohy:
1. Určete počet všech anagramů, jež lze vytvořit ze slova KOMBINATORIKA.
Řešení:
- vytvoříme skupiny stejných písmen, ty budou postupně tvořit k1....kk
A ­ 2 ,B ­ 1 , I ­ 2 , K - 2 , M ­ 1 , A ­ 1 , O ­ 2 , R ­ 1 , T ­ 1
celkem 13 písmen, která se mohou jakkoli zaměňovat
počet takto vytvořených anagramů je P`( 2,2,2,2,1,1,1,1,1 ) =
16
!13
2. Kolika způsoby může aranžér umístit do výkladní skříně 3 stejné červené svetry, 2
stejné modré sukně a 3 stejné zelené kabáty?
Řešení:
- vytvoříme postupně skupiny k1 = 3, k2 = 2 , k3 = 3
- množina ze které vybíráme je dána součtem skupin tzn. k1+k2+k3=8
počet možností umístění je P`( 3,3,2 ) =560
3. Určete počet všech čtyřciferných přirozených čísel dělitelných devíti,v jejichž
dekadickém zápisu se vyskytují pouze číslice 0 , 1 ,2 ,5 , 7.
Řešení:
- ciferný součet daných čísel musí být dělitelný devíti, tzn. přicházejí v úvahu součty
27 , 18 , 9 ,vzhledem k zadaným číslicím nelze získat součet 27
- součet 18 lze dostat použitím číslic 7,7,2,2 anebo 7,5,5,1
- součet 9 utvoří pouze číslice 7,2,0,0 nebo 7,1,1,0 nebo 5,2,2,0 nebo 5,2,1,1
- počet takových čísel je patrný z následujícího zápisu
7,7,2,2..........P`(2,2) = 6
7,5,5,1..........P`(1,2,1) = 12
7,2,0,0..........P`(1,1,2) ­ P(3) = 6 čísla nesmí začínat nulou,jinak trojciferná
7,1,1,0..........P`(1,2,1) ­ P`(1,2) = 9
5,2,2,0 .........P`(1,2,1) ­ P`(1,2) = 9
5,2,1,1..........P`(1,1,2) = 12
- počet všech takto tvořených čtyřciferných přirozených čísel je dán součtem
jednotlivých výpočtů 6 + 12 + 6 + 9 + 9 + 12 =54
Procvičte si:
1. Určete počet všech anagramů ze slova ABRAKADABRA.
(P`(5,2,2,1,1))
2. Určete počet všech uspořádaných šestic sestavených ze čtyř nul a dvou jedniček.
(P`(2,4))
3. Vozy tvoří kolonu takto ­ 2 vozy Škoda, 3 vozy Opel, 4 vozy Fiat. Kolika způsoby
lze seřadit kolonu jestliže pořadí vozů není podmínkou?
(P`(2,3,4 ))
Kombinace s opakováním
základní formulace úlohy: ,, Kolika způsoby můžeme z daných n objektů vybrat
k objektů , nezáleží-li na pořadí a připustíme-li , že
objekty mohou být vybrány vícekrát?"
Každý z možných výběrů nazýváme k-prvkovou kombinací s opakováním z n prvků.
K-členná kombinace s opakováním z n prvků je neuspořádaná k-tice sestavená z těchto n
prvků tak, že každý se v ní vyskytuje nejvýše k.krát.
Jejich celkový počet označujeme K`( k,n ) a počítáme ho podle vzorce
K`(k,n) =
Na rozdíl od kombinací bez opakování zde není třeba předpokládat kn.
Vzorové úlohy:
1. Máme tři stejné předměty a tři přihrádky. Kolika různými způsoby můžeme tyto
předměty rozdělit do přihrádek?
Řešení:
- tři stejné předměty lze umístit postupně takto
1 přihrádka 3 0 0 0 0 2 2 1 1 1
2 přihrádka 0 3 0 1 2 1 0 0 2 1
3 přihrádka 0 0 3 2 1 0 1 2 0 1
- z toho je vidět, že požadavkům úlohy vyhovuje 10 způsobů
- pro výpočet n = 3 /počet přihrádek/
k = 3 /počet předmětů/
pak platí K`( 3,3 ) = =10
Vzorové úlohy:
1. V sáčku jsou červené, modré a zelené kuličky; kuličky téže barvy jsou nerozlišitelné .
Určete, kolika způsoby lze vybrat pět kuliček, jestliže
v sáčkuje a/ aspoň pět kuliček od každé barvy
b/ pět červených, čtyři modré a čtyři zelené.
Řešení:
V pětici kuliček, které vybíráme, nezáleží na pořadí a barvy kuliček se v ní
mohou opakovat. Jde tedy o 5členné kombinace kombinace s opakováním ze tří
prvků.
a/ V tomto případě je možno utvořit všechny možné pětice ze tří barev, neboť
kuliček dané barvy je dostatek tj. pět. Počet způsobů výběru je K`( 5,3 )= 21
b/ Nyní nelze vybrat pět modrých ani pět zelených kuliček. Ostatní výběry lze
uskutečnit. Počet způsobů výběru je K`( 5,3 ) ­ 2 = 19
2. Ze skladu je třeba rozvést šest stejných beden do čtyř různých prodejen.
Určete počet způsobů rozvozu.
Řešení:
- uvědomíme si, že nezáleží na pořadí a ne všechny prodejny musí mít zboží
- může existovat prodejna, která bude mít všech šest beden
- jedná se tedy o kombinaci šesté třídy s opakováním ze čtyř prvků
počet způsobů rozvozu je K`( 6,4 ) = 84
3. Určete počet způsobů jak lze dostat čtyři stejné koule do tří různých krabic.
Řešení:
- uvědomíme si, že je možné umístit všechny čtyři koule do jedné z krabic
- jedná se tedy znovu o kombinaci a to čtvrté třídy ze tří prvků s opakováním
počet způsobů umístění koulí je K`( 4,3 ) = 15
Procvičte si:
1. Podle vlastností dělíme látky na feromagnetické,paramagnetické a diamagnetické.
Určete počet rozdělení osmi látek do těchto skupin.
( K`(8,3))
2. V akvaristice mají čtyři druhy rybek v ceně 10 Kč za rybku. Kolika způsoby
lze nakoupit, zaplatíme-li 60 Kč?
( K`(6,4))
3. Určete počet všech trojúhelníků, z nichž žádné dva nejsou shodné a jejichž
každá strana má velikost vyjádřenou jedním z čísel 4,5,6,7.
(K`(3,4))
Závěr první části kombinatoriky
Získané dovednosti:
- chápat pojem faktoriál a operace s faktoriály
- chápat pojem variace, permutace, kombinace
bez opakování i s opakováním, umět tyto pojmy
použít při řešení jednoduchých úloh
- na základě rozboru textu dané úlohy umět
aplikovat správný kombinatorický pojem
Úlohy z kombinatoriky nebývají složité, většinou se jedná o dosazení dvou čísel/třída,
prvky/ do jednoho vzorce. Důležité je rozpoznat, která operace danou úlohu řeší.
To znamená, jde-li o variaci, permutaci nebo kombinaci.
Určitou pomůckou zde je způsob vyjádření počtu prvků. Je-li zřejmé, že jsou všechny
prvky stejné /body roviny/ nebo není známo jejich rozlišení /pět číslic a neví se které/
jde zpravidla o kombinace ­ k určení nás zajímá jen jejich kvantita.
U variací /tedy i u permutací/ nás zajímá obojí.
Nelze opomenout úlohy, které mívají určenu stránku kvalitativní i kvantitativní
a přesto nejde o variace. Uvedeme následující úlohu:
Lístek v loterii obsahuje čísla 1 až 9, kolik lístků bychom potřebovali, abychom
vyhráli.
Řešení: - položme si otázku, zda v dané skupině existuje pořadí čísel a zjistíme,
že ne, protože označení je stejné
- lístek dále obsahuje 9 číslic, ale ty jsou rozlišeny 1 až 9
- možnosti označení čísel na lístku nelze kvalitativně rozlišit a jde tedy
o kombinace
Řada příkladů není postavena jen na určení druhu operace.Obsahují zápletku, kterou
je nutno řešit výhradně logicky. Uvedeme následující úlohu:
Máme určit počet úhlopříček v n-úhelníku.
Řešení: - zde je jasné, že všechny úhlopříčky jsou stejné, nelze je tedy řadit
- jde o kombinace, kde počet prvků je vlastně počet úhlů, ze kterých
úhlopříčky vycházejí
- jednu skupinu vždy tvoří jedna úhlopříčka, která je zadána dvěma body
- jde o kombinaci 2. třídy příklad bychom řešili K ( 2,n )
Je zde ale zápletka, že všechny přímky mezi úhly nejsou úhlopříčky /některé jsou
strany n-úhelníku, kterých je n/, takže je musíme od získaného vztahu odečíst.
Počet úhlopříček tedy je : K ( 2,n ) ­ n
A konečně jsou zde i úlohy školní, kde jen těžko aplikujeme i výše uvedenou
logiku z praxe. Můžeme uvést jeden příklad za všechny:
Kolik pěticiferných čísel je možno sestavit z číslic 0,1,3,4,7?
- jelikož u každého čísla záleží na pořadí číslic, jedná se o variace /v tomto případě
o permutace n=k/
- pozor však na čísla začínající nulou, nyní ještě nevíme kolik jich bude
- musíme si představit, že to budou čísla, mající na začátku stále nulu, takže se
kombinování neúčastní/ zbytek se tedy kombinování účastní tj. čtyři/
- odečteme od celkového počtu permutací z pěti prvků počet permutací ze čtyř prvků
P( 5 ) ­ P( 4) = 5! ­ 4! = 96
Na závěr si vytvoříme jednoduchý příklad:
Mějme množinu 6 prvků, které tvoří číslice 1,2,3,4,5,6. Vytvořme všechny kombinační
funkce druhé třídy, tedy n = 6, k = 2.
1. Vytvoříme
variace bez opakování V(2,6) = 30
2. Permutace nelze
vytvořit ani bez opakování ani s opakováním.
3. Kombinace bez
opakování K(2,6) = 15 - povšimneme si vztahu
kombinace a variace K < V
4. Variace s opakováním,
vytvoříme tak, že si představíme, že v každé dvojici / obecně tedy v n-tici /
k sobě mohou být přiřazeny i stejné prvky V`(2,6)=36
5. Kombinace
s opakováním K`( 2,6 ) = 21
V následujících
úlohách zdůvodněte typ a řešte /konzultujte s vyučujícím/.
1. Kolik různých
pěticiferných čísel lze vytvořit z číslic 2 a 5?
(32)
2. Kolik
trojciferných čísel lze sestavit z číslic 1,2,3,4,5, jestliže se žádná číslice
neopakuje?
(60)
3. Kolik
přímek je určeno šesti body, jestliže - žádné tři neleží
na téže přímce (15) - tři body leží na jedné
přímce (13)
4. Obchod nabízí 12
různých pohledů. Kolika způsoby lze koupit - 15 pohledů
(7 726 160) - 7 pohledů (31
824) - 7 různých pohledů (792)
5. Kolika způsoby lze ubytovat 10 hostů do dvou třílůžkových pokojů a do
dvou dvoulůžkových pokojů?
(25
200)
6. Kolik různých součinů o dvou činitelích lze utvořit z čísel 2,3,5,7, jestliže se
libovolněkrát opakují?
(10)
7. Kolik anagramů vytvoříte ze slova PRAMA?
(60)
8. Určete počet výsledků při jednom hodu 2 kostkami.
(36)
9. Kolik přirozených čísel menších než 5 000 lze vytvořit z číslic 0,3,4,5,
jestliže se žádná neopakuje?
(42)
10. Kolika způsoby lze ze sady 12 různobarevných pastelek, mezi nimiž je jedna
černá, vybrat 3 tak, aby
- jedna z nich byla černá (55)
- ani jedna nebyla černá (165)