a pravděpodobnost
KOMBINATORIKA
L17: Permutace bez opakování
<< Předchozí lekce | Seznam lekcí | Další lekce >>
V předchozích lekcích jsme se věnovali variacím bez opakování, což jsou uspořádané k-tice z n prvků, kdy každý prvek se vyskytuje nejvýše jednou. Jejich zvláštním případem je, kdy sestavujeme z n prvků variace n-tého řádu. Ty budeme označovat pojmem permutace.
a) Kolik trojciferných čísel můžeme vytvořit z čísel 1, 2, 3, aby se každá číslice vyskytovala nejvýše jedenkrát? Vypište tato čísla!
b) Kolik čtyřciferných čísel můžeme vytvořit z čísel 1, 2, 3, 4, aby se každá číslice vyskytovala nejvýše jedenkrát? Vypište tato čísla!
Počet takových čísel můžeme zjistit i se znalostí variací.
a) Trojciferná čísla
$${V(3, 3) = = \frac{3!}{(3 - 3)!} = \frac{3!}{0!} = 3 \cdot 2 \cdot 1 = 6}$$
123, 132
213, 231
312, 321
Z číslic 1, 2, 3 můžeme vytvořit 6 trojciferných čísel tak, aby se číslice neopakovaly.
b) Čtyřciferná čísla
$${V(4, 4) = = \frac{4!}{(4 - 4)!} = \frac{4!}{0!} = 4 \cdot 3 \cdot 2 \cdot 1 = 24}$$
1234, 1243, 1324, 1342, 1423, 1432
2134, 2143, 2314, 2341, 2413, 2431
3124, 3142, 3214, 3241, 3412, 3421
4123, 4132, 4213, 4231, 4312, 4321
Z číslic 1, 2, 3, 4 můžeme vytvořit 24 čtyřciferných čísel tak, aby se číslice neopakovaly.
Vztah pro permutaci bez opakování můžeme jednodušše odvodit ze vztahu pro variaci bez opakování. Platí: $${V(k, n) = n\cdot(n-1)\cdot(n-2)\cdot~\dots~\cdot(n - k + 1)}$$ Tedy: $${V(k, n) = \frac{n!}{(n - k)!}}$$ Permutaci jsme si definovali jako n-člennou variaci z n prvků: $${P(n) = V(n, n) = \frac{n!}{(n - n)!}}$$ $${P(n) = V(n, n) = \frac{n!}{0!}}$$ Z lekce L01, která se věnovala faktoriálu, víme, že ${0! = 1}$. $${P(n) = V(n, n) = \frac{n!}{1} = n!}$$
Jinými slovy: Pokud vybíráme n-tici z n prvků, tak 1. prvek můžeme vybírat z n prvků, druhý z n - 1, třetí z n - 2, až předposlední ze dvou prvků a poslední z jednoho.
Dojdeme ke stejnému vztahu:
$${P(n) = n \cdot (n - 1) \cdot (n - 2) \cdot~\dots~\cdot 2 \cdot 1 = n!}$$Jedná se o permutaci z 15.
$${P(15) = 15! = 15 \cdot 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 1~307~674~368~000}$$
15 knih můžeme uspořádat v knihovně 1 307 674 368 000 způsoby.
Pěticiferná čísla:
Jedná se o permutaci z 5.
$${P(5) = 5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120}$$
Pěticiferná čísla dělitelná pěti:
Tyto čísla mohou z nabízených číslic končit pouze 5. Zbylými čtyřmi číslicemi obsahujeme zbývající 4 cifry. Sestavujeme tedy permutaci ze 4
$${P(4) = 4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24}$$
Sudá pěticiferná čísla:
Tyto čísla mohou z nabízených číslic končit 4 nebo 6. Zbylými čtyřmi číslicemi obsahujeme zbývající 4 cifry. Sestavujeme tedy permutaci ze 4 a násobíme dvěma pro jednotlivé varianty poslední cifry.
$${2 \cdot P(4) = 2 \cdot 4! = 2 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 48}$$
a) v libovolném pořadí?
b) pokud budou nejprve v řadě za sebou dívky a až potom chlapci?
c) pokud mají dívky stát v řadě za sebou?
a)
Ve třídě je celkem 8 + 6 = 14 žáků. Tvoříme tedy permutace ze 14. $${P(14) = 14! = 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 87~178~291~200}$$
b)
Počet způsobů seřazení 6 dívek zjistíme pomocí permutace ze 6: $${P(6) = 6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720}$$
Počet způsobů seřazení 8 chlapců zjistíme pomocí permutace z 8: $${P(8) = 8! = 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 40~320}$$
Celkový počet možností seřazení zjistíme pomocí kombinatorického pravidla součinu: $${P(6) \cdot P(8) = 6! \cdot 8! = 720 \cdot 40~320 = 29~030~400}$$
c)
Počet způsobů, jak rozmístit dívky ve skupině za sebou zjistíme pomocí permutace ze 6: $${P(6) = 6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720}$$
Skupinu dívek můžeme v řadě 14 žáků umístit devíti způsoby, o čemž se můžeme přesvědčit níže (C = chlapec, D = dívka):
DDDDDDCCCCCCCC
CDDDDDDCCCCCCC
CCDDDDDDCCCCCC
CCCDDDDDDCCCCC
CCCCDDDDDDCCCC
CCCCCDDDDDDCCC
CCCCCCDDDDDDCC
CCCCCCCDDDDDDC
CCCCCCCCDDDDDD
Zbylá místa můžeme obsadit chlapci. Těch je 8, počet možností tedy získáme jako permutaci z 8: $${P(8) = 8! = 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 40~320}$$
Celkový počet možností seřazení žáků tedy bude: $${9 \cdot P(6) \cdot P(8) = 9 \cdot 6! \cdot 8! = 9 \cdot 720 \cdot 40~320 = 261~273~600}$$
I) Jedná se o permutaci ze 7: $${P(7) = 7! = 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5~040}$$
II) Pokud bude Lenka sedět uprostřed, obsazujeme zbývajících 6 míst. Jedná se tedy o permutaci ze 6: $${P(6) = 6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720}$$
III) Lenka může sedět na kraji ve dvou případech. V obou případech obsazujeme zbývajících 6 míst. Jedná se tedy o permutaci ze 6 násobenou dvěma.: $${2 \cdot P(6) = 2 \cdot 6! = 2 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 1~440}$$
b) Kolikati způsoby lze zamíchat balíček 52 karet?
a) Jedná se o permutaci z 32. $${P(32) = 32! = 263~130~836~933~693~530~167~218~012~160~000~000 \doteq 2,63 \cdot 10^35}$$
b) Jedná se o permutaci z 52. $${P(52) = 52! = 80~658~175~170~943~878~571~660~636~856~403~766~975~289~505~440~883~277~824~000~000~000~000 \doteq 8,07 \cdot 10^67}$$
Pozn.: Jako výsledek by stačilo uvést 32! a 52!. Takové hodnoty již většinou na běžné kalkulačce přesně nevyčíslíme, ale zde jsou uvedeny pro představu velikosti čísla u faktoriálu vyšších hodnot. Tyto hodnoty mohou být vyčísleny například pomocí aplikace Wolfram Alpha, či jiných specializovaných matematických aplikací.
V dané permutaci je 6 prvků.
Když budeme postupovat z opačného směru, můžeme dělit dané číslo 2, výsledek 3 atd., až nám při dělení číslem n vyjde podíl 1. Potom číslo n je počet prvků, ze kterých jsme tvořili dané permutace.
$${40~320 : 2 = 20~160}$$
$${20~160 : 3 = 6~720}$$
$${6~720 : 4 = 1~680}$$
$${1~680 : 5 = 336}$$
$${336 : 6 = 56}$$
$${56 : 7 = 8}$$
$${8 : 8 = 1}$$
40 328 permutací vytvoříme z 8 prvků
Když budeme postupovat z opačného směru, můžeme dělit dané číslo 2, výsledek 3 atd., až nám při dělení číslem n vyjde podíl 1. Potom číslo n je počet prvků, ze kterých jsme tvořili dané permutace.
$${6~402~373~705~728~000 : 2 = 3~201~186~852~864~000}$$
$${3~201~186~852~864~000 : 3 = 1~067~062~284~288~000}$$
$${1~067~062~284~288~000 : 4 = 266~765~571~072~000}$$
$${266~765~571~072~000 : 5 = 53~353~114~214~400}$$
$${53~353~114~214~400 : 6 = 8~892~185~702~400}$$
$${8~892~185~702~400 : 7 = 1~270~312~243~200}$$
$${1~270~312~243~200 : 8 = 158~789~030~400}$$
$${158~789~030~400 : 9 = 17~643~225~600}$$
$${17~643~225~600 : 10 = 1~764~322~560}$$
$${1~764~322~560 : 11 = 160~392~960}$$
$${160~392~960 : 12 = 13~366~080}$$
$${13~366~080 : 13 = 1~028~160}$$
$${1~028~160 : 14 = 73~440}$$
$${73~440 : 15 = 4~896}$$
$${4~896 : 16 = 306}$$
$${306 : 17 = 18}$$
$${18 : 18 = 1}$$
40 328 permutací vytvoříme z 18 prvků
- Co je to "permutace bez opakování"?
- Jak je definován faktoriál?
- Jak určíme počet permutací?
- Kolik různých šesticiferných přirozených čísel lze napsat pomocí číslic 1, 2, 3, 4, 5, 6, jestliže v zápisu každého čísla se každá z číslic může vyskytnout pouze jednou? Kolik z nich bude lichých?
- Zvětší-li se počet prvků o 2, zvětší se počet permutací 42 krát. Jaký je původní počet prvků?
- Permutace z n prvků je každá n-členná variace z těchto prvků, Je to tedy uspořádaná n-tice sestavená z n prvků tak, že každý se v ní vyskytuje právě jednou.
- ${n! = n \cdot (n - 1) \cdot (n - 2) \cdot~\dots~\cdot 2 \cdot 1}$
${0! = 1}$ - ${P(n) = n \cdot (n - 1) \cdot (n - 2) \cdot~\dots~\cdot 2 \cdot 1 = n!}$
- 720 čísel, z toho 360 lichých
- 5 prvků