Management rekreace a sportu Kombinatorika


Download 128.4 Kb.
Pdf ko'rish
Sana19.12.2017
Hajmi128.4 Kb.
#22590

Management rekreace a sportu

6. Kombinatorika

1

6. Kombinatorika



V praxi se běžně setkáme s potřebou určit, kolika způsoby lze něco provést, případně

kolik je možných způsobů, jak nějaký jev nastane. Výpočty zmíněného charakteru se zabývá

kombinatorika. Základním principem je pravidlo součinu.

KOMBINATORICKÉ PRAVIDLO SOUČINU

Lze-li činnost A provést m způsoby a nezávisle na ní činnost B n způsoby, pak počet

všech možných způsobů, jak provést A i B se rovná m⋅n.

Příklad:

V restauraci jsou na jídelníčku 3 různé polévky a 4 různá hlavní jídla. Kolik je všech možných způsobů,

jak si vybrat polévku a k ní hlavní jídlo?

Řešení:


Polévku lze vybrat třemi způsoby, nezávisle na ní hlavní jídlo čtyřmi způsoby. Podle pravidla součinu lze vybrat

celkem 3⋅4 = 12 způsoby určitou polévku a k ní hlavní jídlo.

Kombinatorické pravidlo součinu platí i pro případ více než dvou nezávislých činností.

Příklad:


(a)  Jana  si  může  ze  své  garderoby  pro  odpolední  vycházku  vybrat  z  5  různých  halenek,  ze  7  různých

sukní a ze 4 různých párů bot. Kolika různými způsoby se může obléci?

Řešení:

Jana se může obléci celkem 5⋅7⋅4 = 140 různými způsoby.



(b)  Bezpečnostní zámek u kufříku je konstruován ze tří otočných koleček. Na každém z nich lze nastavit

číslice 0, 1,…, 9. Kolik různých konfigurací má bezpečnostní zámek?

Řešení:

Každá konfigurace je uspořádaná trojice (a, b, c). Na každé z poloh a, b, c lze nastavit nezávisle na sobě 10



různých  poloh  číslicemi  0, 1,…, 9.  Celkový  počet  konfigurací  je  pak  10⋅10⋅10 = 1000.  K výsledku  lze

dospět  i  jinou  úvahou:  Počet  konfigurací  musí  odpovídat  počtu  různých  trojmístných  čísel

(tj. 000, 001,…, 100,…, 999), kterých je celkem 1000.

Úvahy  doposud  prováděné  lze  převést  na  úvahy  o  uspořádaných  k-ticích.

Tak  v předchozím  příkladu  (a)  jde  o  počet  uspořádaných  trojic  (halenka, sukně, boty),


Management rekreace a sportu

6. Kombinatorika

2

v příkladu  (b)  počet  trojic  čísel  (a, b, c).  Pak  lze  kombinatorické  pravidlo  součinu  obecně



formulovat takto:

Počet všech uspořádaných k-tic, z nichž první člen lze vybrat n

1

 různými způsoby, druhý člen



po  výběru  prvního  členu  n

2

  různými  způsoby  atd.,  až  k-tý  člen  po  výběru  (k 



 1).  členu  n

k

různými způsoby, se rovná n



1

⋅n

2



⋅…⋅n

k

.



Příklad:

Kolika různými způsoby se může seřadit 6 klientů do fronty u přepážky ve spořitelně?

Řešení:

Klienti  vytvářejí  různé  uspořádané  šestice  (a



1

, a


2

, a


3

, a


4

, a


5

, a


6

).  Člen  a

1

,  tj.  klienta  stojícího  jako  prvního,  lze



vybrat 6 způsoby.  Po  výběru  členu  a

1

  lze  člen  a



2

  vybrat  již  pouze  5  způsoby  (1  klient  již  byl  vybrán  na  první

místo), člen a

3

 4 způsoby atd., až člen a



6

 jediným způsobem. Celkem lze tedy vytvořit 6⋅5⋅4⋅3⋅2⋅1 = 720 různých

front.

Kombinatorické  úlohy  lze  roztřídit  do  skupin,  majících  společný  "výpočetní



základ"  tzv. variací, permutací, kombinací a jejich modifikací.

VARIACE


Variace  k-té  třídy  z  n  prvků  (k ≤ n)  je  každá  uspořádaná  k-tice  různých  prvků

vybraných z n prvků. Počet všech různých variací k-té třídy z n prvků se značí V

k

(n).


[Slovy  jinak:  Variace  je  k-tice  vybraná  z  n  prvků,  přičemž  v  ní  záleží  na  pořadí  a  každý

z prvků se v ní vyskytuje nejvýše jednou].

Příklad:

Všechny různé variace druhé třídy z prvků a, b, c, d jsou (přehledně):

a je první

b je první

c je první

d je první

ab

ac

ad



ba

bc

bd



ca

cb

cd



da

db

dc



Platí V

2

(4) = 12



.

Pro počet V

k

(n) všech různých variací k-té třídy z n prvků platí vzorec



( )

(

) (



)

1

1



+



=

k

n



n

n

n



k

V



.

(6.1)


Management rekreace a sportu

6. Kombinatorika

3

Tento vzorec se zapisuje obvykle ve tvaru



( )

(

)



!

!

k



n

n

n



k

=



V

,

(6.2)



kde

(

)(



)

1

2



2

1

!





=

n



n

n

n



,

přičemž se definuje 0! = 1; n! se čte "n faktoriál".

Příklad:

Manažer  portfolia  dospěl  k  závěru,  že  akcie  13  společností  splňují  jeho  investorské  záměry.  Z  těchto

třinácti má určit 3 včetně pořadí, které stanoví jejich preference. Kolika způsoby to může provést?

Řešení:


Jde o variace 3. třídy ze 13 prvků, platí 

( )


(

)

1716



11

12

13



!

10

!



10

11

12



13

!

10



!

13

!



3

13

!



13

13

3



=



=



=

=



=

V



.

Výběr lze provést 1716 způsoby.

Připustí-li  se  opakování  prvků  v  uspořádané  k-tici  vybrané  z  n  prvků,  pak  se  hovoří

o variaci s opakováním:

Variace s opakováním k-té třídy z n prvků je každá uspořádaná k-tice prvků vybraných

z n prvků. Počet všech různých variací s opakováním k-té třídy z n prvků se značí 

( )

n

o



k

V

.



Příklad:

Všechny různé variace s opakováním druhé třídy z prvků a, b, c, d jsou:

aa, ab, ac, ad; ba, bb, bc, bd; ca, cb, cc, cd; da, db, dc, dd. Platí 

( )


16

4

2



=

o

V



.

Pro počet 

( )

n

o



k

V

 všech různých variací s opakováním k-té třídy z n prvků platí vzorec



( )

k

o



k

n

n =



V

.

(6.3)



Příklad:

Kolik je všech možných devítimístných telefonních čísel?



Management rekreace a sportu

6. Kombinatorika

4

Řešení:


Jde o variace s opakováním, 

( )


1000000000

10

10



9

9

=



=

o

V



.

Zvláštním případem variací jsou permutace (pro k = n).

PERMUTACE

Permutace  n  prvků  je  každá  variace  n-té  třídy  z  n  prvků.  Počet  všech  permutací  z  n

prvků se značí P(n). [Slovy jinak: Permutace n prvků je zápis těchto prvků v určitém pořadí.]

Příklad:


Všechny různé permutace prvků a, b, c jsou:

abc, acb, bac, bca, cab, cba.

Platí P(3) = 6.

Ze vztahu (6.2) ihned vyplývá vzorec pro počet permutací n prvků:

( )

!

n



n =

P

.



(6.4)

Příklad:


Kolik lze vytvořit všech slov přesmyčkou ve slově BOULE?

Řešení:


P(5) = 5! = 120.

Permutace s opakováním n prvků je každá variace s opakováním n-té třídy, ve které se

k < n  různých  prvků  vyskytuje  v  počtech  n

1

, n



2

,…, n


k

  (platí  pak  n

1

 + n


2

 +…+ n


k

 = n).  Počet

takových permutací se značí 

( )


n

o

n



n

k

,



,

1



P

. Platí


( )

!

!



!

!

2



1

,

,



1

k

o



n

n

n



n

n

n



n

k



=

P



.

(6.5)


Příklad:

Kolik různých slov lze vytvořit přesmyčkou ve slově KOLOKOL?

Řešení:

Jde o sedmici, ve které s K vyskytuje dvakrát, O třikrát a L dvakrát. Užitím (6.5) dostaneme



( )

210


1

2

1



2

3

1



2

1

2



3

4

5



6

7

!



2

!

3



!

2

!



7

7

2



,

3

,



2

=









=



=

o

P



.

Management rekreace a sportu

6. Kombinatorika

5

KOMBINACE



Kombinace  se  od  variací  zásadně  liší  v  tom,  že  ve  vybrané  k-tici  nezáleží  na

uspořádání, jinak řečeno v k-tici nezáleží na pořadí prvků.

Kombinací k-té třídy z n prvků (k ≤ n) je každý výběr k různých prvků z n prvků. Počet

všech  různých  kombinací  k-té  třídy  z  n  prvků  se  značí  C

k

(n).  [Slovy  jinak:  Kombinace  je



k-tice  prvků  vybraná  z  n  prvků,  přičemž  v  ní  nezáleží  na  pořadí  a  každý  z  prvků  se  v  ní

vyskytuje nejvýše jednou.]

Příklad:

Všechny různé kombinace druhé třídy z prvků a, b, c, d jsou:

ab, ac, ad, bc, bd, cd.

Pro počet C

k

(n) všech různých kombinací k-té třídy z n prvků platí vzorec:



( )

(

)











=

=



k

n

k



n

k

n



n

C

k



!

!

!



,

(6.6)


kde 









k

n



 se nazývá kombinační číslo a čte se "n nad k". Pro vyčíslení 









k

n



 platí

(

) (



)

(

)



1

2

1



1

1



+



=











k

k



k

n

n



n

k

n



.

Například: 

1

2

3



5

6

7



3

7





=









.

Příklad:



Kolika způsoby lze vybrat 3 výrobky z 10 výrobků?

Řešení:


Jde o kombinace třetí třídy z deseti prvků (nezáleží na pořadí), 

( )


120

1

2



3

8

9



10

3

10



10

3

=





=









=



C

.

Platí vzorce



Management rekreace a sportu

6. Kombinatorika

6









+

+



=









+

+











=









=



















=









1

1



1

,

1



,

1

0



,

k

n



k

n

k



n

n

n



n

k

n



n

k

n



.

(6.7)


Kombinační  čísla  mají  v  matematice  široké  uplatnění,  například,  při  formulaci

binomické věty.

BINOMICKÁ VĚTA

Binomická věta udává vzorec pro umocnění součtu:

Pro libovolná čísla a, b a libovolné přirozené číslo n platí

(

)



n

n

n



n

n

n



b

n

n



ab

n

n



b

a

n



b

a

n



a

n

b



a









+











+

+









+











+









=

+





1

2

2



1

1

2



1

0



.

(6.8)


Příklad:

(

)



.

4

6



4

1

2



3

2

3



4

1

2



3

4

4



4

4

3



4

2

4



1

4

0



4

4

3



2

2

3



4

4

3



2

2

3



4

4

3



1

2

2



1

3

4



4

b

ab



b

a

b



a

a

b



ab

b

a



b

a

a



b

b

a



b

a

b



a

a

b



a

+

+



+

+

=



+



+



+



+

+

=











+









+









+











+









=

+



Příklad:

Kolik je různých podmnožin množiny, která obsahuje n prvků?

Řešení:

Prázdná množina je jediná, podmnožin obsahujících jeden prvek je n, podmnožin obsahujících 2 prvky je 











2

n

(jde o kombinace druhé třídy z n prvků), podmnožin obsahujících 3 prvky je 











3

n

,…, podmnožin obsahujících



(n − 1)  prvků  je 









−1

n



n

,  podmnožina  obsahující  všechny  prvky  dané  množiny  je  jediná.  Sečtením  dostáváme

( )

( ) ( )


.

2

1



1

1

pro



8

.

6



užitím

1

3



2

1

0



1

,

1



,

0

1



7

.

6



užitím

vyjádříme

1

1

3



2

1

n



n

b

a



n

n

n



n

n

n



n

n

n



n

n

n



n

n

n



n

n

n



=

+

=



=

=

=



=









+











+

+









+











+









+









=











=









=









=



=

+











+

+









+











+

+





Management rekreace a sportu

6. Kombinatorika

7

Cílové znalosti



1.  Užití kombinatorického pravidla součinu při řešení běžných kombinatorických úloh.

2.  Rozlišení kombinatorických úloh na variace, permutace, kombinace a jejich modifikace.

3.  Vzorce pro stanovení počtu variací, permutací, kombinací a jejich modifikací.


Management rekreace a sportu

6. Kombinatorika

8

VI. Kombinatorika_CVIČENÍ



K

OMBINATORICKÉ PRAVIDLO SOUČINU

1.  Z města  A  do  města  B  vedou  čtyři  cesty,  z města  B  do  města  C  pět  cest.  Určete  počet

cest, které vedou z města A do města C přes město B.

2.  V hřebčíně mají 10 bílých a 8 černých závodních koní stejné výkonnosti. Na závod mají

vybrat  dvojice,  kde  bude  jeden  černý  a  jeden  bílý  kůň.  Kolika  způsoby  mohou  výběr

provést?

3.  Máme k dispozici 10 karafiátů, 12 žlutých a 14 červených tulipánů. Kolika způsoby lze

udělat kytičku, která bude obsahovat 1 karafiát, 1 žlutý a 1 červený tulipán?

4.  Určete  počet  všech  čtyřciferných  přirozených  čísel,  v nichž  se  vyskytuje  každá  číslice

nejvýše jednou.

5.  Jsou-li vrženy dvě kostky, výsledek lze vyjádřit uspořádanou dvojicí (a, b), kde a je číslo,

které padlo na 1. kostce, a b je číslo, které padlo na 2.kostce. Kolik je takových různých

dvojic? Kolik z nich je takových, že součty a + b jsou navzájem různé.

V

ARIACE


6.  Ve škole se učí 10 různým předmětům a každému se učí nejvýše hodinu denně. Kolika

způsoby lze sestavit rozvrh hodin na jeden den, je-li v něm 5 různých předmětů?

7.  Upravte: 

(

)



(

)

(



)

(

)



!

2

!



!

1

!



1

2

!



!

2



+

+



+

n



n

n

n



n

n

.



8.  Z kolika různých prvků lze vytvořit 870 variací druhé třídy?

9.  Zvětšíme-li počet prvků o jeden, zvětší se počet variací druhé třídy o 16. Určete původní

počet prvků.

10. Státní  poznávací  značka  automobilu  je  tvořena  trojicí  číslice,  písmeno,  číslice

a oddělenou  skupinou  čtyř  číslic.  Kolik  lze  státních  poznávacích  značek  vytvořit,  je-li

k dispozici 14 písmen?

11. Řešte rovnici 

( )


( )

20

2



0

3

0



2

=

− xV



x

V

.



Management rekreace a sportu

6. Kombinatorika

9

P

ERMUTACE



12. Jan napsal 4 dopisy, k nimž měl 4 obálky s adresami. Nedopatřením mu dopisy upadly

na zem. Kolika způsoby je mohl do obálek vložit?

13. Kolik deseticiferných čísel s různými číslicemi lze vytvořit z číslic 0,

 

1,



 

2,

 



3,

 

4,



 

5,

 



6,

 

7,



 

8,

 



9?

14. Kolik různých slov lze vytvořit přesmyčkou ve slově JANA?

K

OMBINACE


15. 8 pracovníků chce vyjádřit nespokojenost řediteli. Ředitel je ochoten přijmout tříčlennou

delegaci. Kolika způsoby lze takovou delegaci vytvořit?

16. Zvětší-li  se  počet  prvků  o  1,  zvětší  se  počet  kombinací  třetí  třídy  o  21.  Kolik  je  dáno

prvků?


17. V bedně je 28 výrobků 1. jakosti a 2 výrobky vadné. Kolikerým způsobem lze vybrat pět

výrobků tak, aby tři z nich byly 1. jakosti a dva z nich byly vadné?

18. Řešte rovnici 

16

5



3

4

2



=











+











x

x

x



x

.

V



ŠEHOCHUŤ

19. Vypočtěte užitím Binomické věty 

(

)

6



3

1 i


.

20. V lavici  sedí  5  chlapců,  z nichž  dva  bratři  chtějí  sedět  vedle  sebe.  Kolikrát  můžeme



chlapce přesadit?

21. Kolik různých slov lze utvořit přesmyčkou ve slově CINCINNATI?

22. Hokejové  mužstvo  má  20  hráčů – 13  útočníků,  5  obránců  a  2  brankáře.  Kolik  různých

sestav  by  mohl  vytvořit  tým,  má-li  sestava  3  útočníky,  2  obránce  a  1  brankáře?

Nerozlišujeme konkrétní posty v útoku a v obraně.


Management rekreace a sportu

6. Kombinatorika

10

V

ÝSLEDKY CVIČENÍ



1. 20; 2. 80; 3. 1 680; 4. 4 536; 5. 36 a 11; 6.  30 240; 7. 2; 8. n = 30; 9. n = 8; 

10. 14 000 000; 11. x = 10; 12. 24; 13. 3 265 920; 14. 12; 15. 56; 16. n = 7; 17. 3 276;



18. x = 7; 19. 64; 20. 48; 21. 50 400; 22. 5 720.

Download 128.4 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling