{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Kapitola 1 - Kombinatorika"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Základní kombinatorická pravidla"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Definice 1.1 - Kombinatorické pravidlo součinu\n",
    "Nechť množina $A_i$ má $n_i$ prvků pro $i=1, 2, \\ldots, k$. Pak počet všech uspořádaných $k$-tic $(a_1 , a_2, \\ldots, a_k)$, kde $a_1 \\in A_1, a_2 \\in A_2,\\ldots, a_k\\in A_k$, je roven $\\prod_{i=1}^k n_i$.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Poznámka 1.1 - Alternativní definice kombinatorického pravidla součinu\n",
    ":class: hint\n",
    "Počet všech uspořádaných $k$-tic, jejichž první člen lze vybrat $n_1$ způsoby, druhý člen po výběru prvního členu $n_2$ způsoby atd. až $k$-tý člen po výběru všech předchozích členů $n_k$ způsoby je roven $n_1 \\cdot n_2 \\cdot \\ldots \\cdot n_k$.\n",
    "```       "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.1\n",
    ":class: warning\n",
    "Určete počet všech přirozených dvojciferných čísel, v jejichž dekadickém zápisu se každá číslice vyskytuje nejvýše jednou.\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "```{admonition} Zobrazit řešení\n",
    ":class: dropdown warning\n",
    "Na místě desítek může být libovolná číslice kromě nuly (v takovém případě bychom neobdrželi dvojciferné číslo). Ke každé z těchto devíti možností pro výběr číslice na místě desítek existuje devět možností, jak vybrat číslici pro místo jednotek (tentokrát to může být $0$ a k tomu jakákoliv z osmi číslic, která se liší od číslice na místě desítek). \n",
    "\n",
    "Počet uvažovaných čísel je tak $9 \\cdot 9 = 81$.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Definice 1.2 - Kombinatorické pravidlo součtu\n",
    "Nechť množina $A_i$ má $n_i$ prvků pro $i=1, 2, \\ldots, k$ a nechť $A_i \\cap A_j = \\emptyset$ pro $i\\neq j$. Pak množina $\\bigcup_{i=1}^k A_i$ má $\\sum_{i=1}^k n_i$ prvků.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Poznámka 1.2 -Alternativní definice Kombinatorického pravidla součtu\n",
    ":class: hint\n",
    "Jsou-li $A_1, A_2, \\ldots , A_k$ konečné množiny, které mají po řadě $p_1, p_2, \\ldots, p_k$ prvků a jsou-li každé dvě disjunktní, pak počet prvků množiny $a_1 \\cup A_2 \\cup \\ldots \\cup A_k$ je roven $p_1 + p_2 + \\ldots + p_n$.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.1\n",
    ":class: warning\n",
    "Určete počet všech přirozených dvojciferných čísel, v jejichž dekadickém zápisu se každá číslice vyskytuje nejvýše jednou (s pomocí kombinatorického pravidla součtu).\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "```{admonition} Zobrazit řešení\n",
    ":class: dropdown warning\n",
    "Všechna přirozená čísla lze rozložit do dvou disjunktních skupin tak, že v první jsou dvojciferná čísla s různými a ve druhé dvojciferná čísla s týmiž číslicemi. Je zřejmé, že všech dvojciferných čísel je $90$ a dvojciferných čísel s týmiž číslicemi $9$ (jedná se o čísla $11, 22, 33, \\ldots ,99$); označíme-li $p$ hledaný počet dvojciferných čísel s různými číslicemi, platí $p + 9 = 90$, tedy $ p = 81$.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.2\n",
    ":class: warning\n",
    "Je dán čtverec $ABCD$ a na jeho každé straně $n$ vnitřních bodů. Určete počet všech trojúhelníků, jejichž vrcholy leží v daných bodech a na různých stranách čtverce $ABCD$.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.3\n",
    ":class: warning\n",
    "Z místa $A$ do místa $B$ vedou $4$ turistické značky, z místa $B$ do místa $C$ tři. Určete, kolika způsoby lze vybrat trasu z $A$ do $C$ a zpět tak, že z těchto sedmi cest je právě jedna použita dvakrát.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Variace bez opakování"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.4 - Motivační úloha\n",
    ":class: warning\n",
    "Kolika způsoby je možné rozdat červený, modrý a bílý balónek mezi $4$ děti? \n",
    "```\n",
    "\n",
    "```{admonition} Zobrazit řešení\n",
    ":class: dropdown warning\n",
    "Ptáme se v podstatě na to, kolika způsoby lze ze $4$ dětí sestavit uspořádanou trojici (děti si označme $a, b, c, d$ a nyní například uspořádaná trojice $(a, c, d)$ znamená, že dítě $a$ dostane červený balónek, dítě $c$ modrý balónek a dítě $d$ bílý balónek.\n",
    "\n",
    "Vypíšeme všechny možnosti: \n",
    "\n",
    "$(a, b, c), (a, c, b), (a, b, d), (a, d, b), (a, c, d), (a, d, c)$, \n",
    "\n",
    "$(b, a, c), (b, c, a), (b, a, d), (b, d, a), (b, c, d), (b, d, c)$,\n",
    "\n",
    "$(c, a, b), (c, b, a), (c, a, d), (c, d, a), (c, b, d), (c, d, b)$, \n",
    "\n",
    "$(d, a, b), (d, b, a), (d, a, c), (d, c, a), (d, b, c), (d, c, b)$. \n",
    "\n",
    "Celkem je tedy $24$ možností. K tomuto výsledku bychom dospěli rovněž užitím kombinatorického pravidla součinu: $4 \\cdot 3 \\cdot 2 = 24$.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Definice 1.3\n",
    "$k$-členná variace z $n$ prvků je uspořádaná $k$-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje nejvýše jednou.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Věta 1.1\n",
    ":class: attention\n",
    "Počet všech $k$-členných variací z $n$ prvků značíme $V(k,n)$, popřípadě $V_k(n)$ a platí \n",
    "\n",
    "$$V(k, n)= n \\cdot (n-1) \\cdot (n-2)\\cdot\\ldots\\cdot (n-k+1),$$\n",
    "\n",
    "případně s využitím faktoriálu\n",
    "\n",
    "$$V(k, n)= \\frac{n!}{(n-k)!}.$$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.5\n",
    ":class: warning\n",
    "K sestavení vlajky, která má být složena ze tří různobarevných vodorovných pruhů, jsou k dispozici látky barvy bílé, červené, modré, zelené a žluté. \n",
    "\n",
    "a) Určete počet vlajek, které lze z látek těchto barev sestavit.\n",
    "\n",
    "b) Kolik z nich má modrý pruh? \n",
    "\n",
    "c) Kolik jich má modrý pruh uprostřed? \n",
    "\n",
    "d) Kolik jich nemá uprostřed červený pruh? \n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.6\n",
    ":class: warning\n",
    "Určete počet všech nejvíce pěticiferných přirozených čísel, v jejichž dekadickém zápisu se každá z deseti číslic vyskytuje nejvýše jednou. \n",
    "\n",
    "Kolik z nich je menší než $50 000$?\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Permutace bez opakování"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Definice 1.4\n",
    "*Permutace* z $n$ prvků je každá $n$-členná variace z těchto prvků, tj. uspořádaná $n$-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje právě jednou.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Věta 1.2\n",
    ":class: attention\n",
    "Počet $P(n)$ všech permutací z $n$ prvků je \n",
    "\n",
    "$$P(n) = n \\cdot (n - 1) \\cdot (n - 2)\\cdot\\ldots\\cdot 3 \\cdot 2 \\cdot 1,$$\n",
    "\n",
    "případně s využitím faktoriálu\n",
    "\n",
    "$$P(n) = n!.$$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Poznámka 1.3\n",
    ":class: hint\n",
    "1. Symbol $n!$ čteme: $n$ faktoriál. \n",
    "\n",
    "2. $n!$ definujeme pro přirozená čísla, přičemž $0! = 1$. \n",
    "\n",
    "3. $\\displaystyle P(n) = V(n,n)$.\n",
    "\n",
    "4. $\\displaystyle V(k,n)={\\frac{n!}{(n-k)!}}$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.7\n",
    ":class: warning\n",
    "S připomínkami k navrhovanému zákonu chce v parlamentu vystoupit $6$ poslanců $A, B, C, D, E, F$. Určete počet \n",
    "\n",
    "a) všech možných pořadí jejich vystoupení; \n",
    "\n",
    "b) všech pořadí, v nichž vystupuje $A$ po $E$;\n",
    "\n",
    "c) všech pořadí, v nichž vystupuje $A$ ihned po $E$.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.8\n",
    ":class: warning\n",
    "Určete, kolika způsoby může $n$ táborníků při nástupu na ranní rozcvičku nastoupit \n",
    "a) do řady; \n",
    "\n",
    "b) do řady, v níž je táborník Adrian na kraji;\n",
    "\n",
    "c) do řady, v níž táborníci Adrian a Bedřich nestojí vedle sebe; \n",
    "\n",
    "d) do kruhu, v němž záleží jen na vzájemném rozmístění, nikoliv na umístění vzhledem k ostatním předmětům.\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.9\n",
    ":class: warning\n",
    "Určete počet všech pěticiferných čísel, v jejichž dekadickém zápisu je každá z číslic $0, 1, 3, 4, 7$. Kolik z těchto čísel je \n",
    "\n",
    "a) dělitelných $6$; \n",
    "\n",
    "b) větších než $70~134$?\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.10\n",
    ":class: warning\n",
    "V množině $\\mathbb{N}$ všech přirozených čísel řešte rovnici: \n",
    "\n",
    "$$(x+1)! = 110 (x - 1)!$$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Kombinace bez opakování\n",
    "\n",
    "Srovnejme variace bez opakování a kombinace bez opakování: \n",
    "\n",
    "- **variace bez opakování**: záleží na pořadí \n",
    "\n",
    "- **kombinace bez opakování**: nezáleží na pořadí"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.11\n",
    ":class: warning\n",
    "Šachového turnaje se zúčastní $4$ hráči $A, B, C, D$. Mají hrát systémem každý s každým jednokolově. Kolik sehrají partií?\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Definice 1.5\n",
    "*$k$-členná kombinace z $n$ prvků bez opakování* je neuspořádaná $k$-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje nejvýše jednou.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Věta 1.3\n",
    ":class: attention\n",
    "Počet všech $k$-členných kombinací z $n$ prvků značíme $K(k,n)$ a platí\n",
    "\n",
    "$$K(k,n) = \\frac{V(k,n)}{k!}=\\frac{n!}{k! (n-k)!}.$$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Definice 1.6\n",
    "Pro $k, n\\in \\mathbb{N}, k\\leq n$, definujeme kombinační číslo: \n",
    "\n",
    "$${n \\choose k}=\\frac{n!}{k! (n-k)!}.$$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Poznámka 1.4\n",
    ":class: hint\n",
    "1. Symbol ${n \\choose k}$ čteme: $n$ nad $k$. \n",
    "\n",
    "2. $\\displaystyle K(k,n)={n \\choose k}$. \n",
    "\n",
    "3. $\\displaystyle {n \\choose {n-k}}={n \\choose k}$.\n",
    "\n",
    "4. $\\displaystyle {n \\choose 0}={n \\choose n}=1$.\n",
    "\n",
    "5. $\\displaystyle {n \\choose 1}=n$.\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.12\n",
    ":class: warning\n",
    "Určete, kolika způsoby lze na šachovnici $8 \\times 8$ vybrat \n",
    "\n",
    "a) trojici políček; \n",
    "\n",
    "b) trojici políček neležících v témže sloupci; \n",
    "\n",
    "c) trojici políček neležících v témže sloupci ani v téže řadě;\n",
    "\n",
    "d) trojici políček, která nejsou všechna téže barvy.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.13\n",
    ":class: warning\n",
    "Určete, kolika způsoby je možno ze sedmi mužů a čtyř žen vybrat šestičlennou skupinu, v níž jsou \n",
    "\n",
    "a) právě dvě ženy;\n",
    "\n",
    "b) aspoň dvě ženy.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Variace s opakování\n",
    "\n",
    "**Záleží na pořadí, prvky se mohou opakovat.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Definice 1.7\n",
    "*$k$-členná variace s opakováním z $n$ prvků* je uspořádaná $k$-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje nejvýše $k$-krát.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Věta 1.4\n",
    ":class: attention\n",
    "Počet všech $k$-členných variací s opakováním z $n$ prvků je \n",
    "\n",
    "$$V'(k,n)=n^k.$$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.14\n",
    ":class: warning\n",
    "Určete, kolik značek Morseovy abecedy lze utvořit sestavením teček a čárek do skupin o jednom až čtyřech prvcích.\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.15\n",
    ":class: warning\n",
    "Určete počet všech podmnožin $k$-prvkové množiny.\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.16\n",
    ":class: warning\n",
    "Příklad. Dalibor zapomněl heslo. Pouze si pamatoval, že na prvních třech místech byla písmena a na dalších čtyřech místech číslice. Kolik by musel vyzkoušet možností? Je možné použít $26$ písmen.\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Permutace s opakování"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Definice 1.8\n",
    "$k$-členná permutace s opakováním z $n$ prvků je uspořádaná $k$-tice sestavená z těchto $n$ prvků tak, že jednotlivé prvky mají pevně daný počet opakování \n",
    "\n",
    "(tj. první prvek se vyskytuje $k_1$-krát, druhý prvek se vyskytuje $k_2$-krát,$\\ldots$, $n$-tý prvek se vyskytuje $k_n$ krát a musí platit $k_1+k_2+\\ldots+k_n=k$).\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Věta 1.5\n",
    ":class: attention\n",
    "Počet $P'(k_1, k_2, \\ldots, k_n)$ $k$-členných permutací s opakováním z $n$ prvků, v nichž se jednotlivé prvky opakují $k_1, k_2, \\ldots , k_n$-krát, je \n",
    "\n",
    "$$P'(k_1, k_2, \\ldots, k_n)=\\frac{(k_1+k_2+\\ldots+k_n)!}{k_1!\\cdot k_2!\\cdot \\ldots\\cdot k_n!}.$$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.17\n",
    ":class: warning\n",
    "Určete počet způsobů, jimiž lze přemístit písmena slova *ABRAKADABRA*. Určete, v kolika z nich \n",
    "\n",
    "a) žádná dvojice sousedních písmen není tvořena písmeny *A*; \n",
    "\n",
    "b) žádná pětice sousedních písmen není tvořena pěti písmeny *A*.\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.18\n",
    ":class: warning\n",
    "Určete počet všech čtyřciferných přirozených čísel dělitelných devíti, v jejichž dekadickém zápisu nejsou jiné číslice než $0, 1, 2, 5, 7$.\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Kombinace s opakování\n",
    "\n",
    "**Nezáleží na pořadí, prvky se mohou opakovat.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.19\n",
    ":class: warning\n",
    "Kolik částek můžeme zaplatit právě $2$ mincemi, máme-li k dispozici korunové, dvoukorunové, pětikorunové a desetikorunové mince a to každý druh alespoň ve dvou exemplářích?\n",
    "```\n",
    "```{admonition} Zobrazit řešení\n",
    ":class: dropdown warning\n",
    "Výčtem: $(1,1), (1,2), (1,5), (1,10), (2,2), (2,5), (2,10), (5,5), (5,10), (10,10)$.\n",
    "\n",
    "Příklad si trochu více rozebereme:\n",
    "\n",
    "Předchozí dvoučlenné kombinace ze $4$ prvků můžeme znázornit pomocí $4$ přihrádek (první pro koruny, druhou pro dvoukoruny, třetí pro pětikoruny, čtvrtou pro desetikoruny) následovně: \n",
    "\n",
    "$(1,1) \\ldots  \\circ\\circ│││$\n",
    "\n",
    "$(1,2) \\ldots \\circ│\\circ││$\n",
    "\n",
    "$(1,5) \\ldots \\circ││\\circ│ $\n",
    "\n",
    "$(1,10) \\ldots \\circ│││\\circ $\n",
    "\n",
    "$(2,2) \\ldots │\\circ\\circ││ $\n",
    "\n",
    "$(2,5) \\ldots │\\circ│\\circ│ $\n",
    "\n",
    "$(2,10) \\ldots │\\circ││\\circ$\n",
    "\n",
    "$(5,5) \\ldots ││\\circ\\circ│ $\n",
    "\n",
    "$(5,10) \\ldots ││\\circ│\\circ $\n",
    "\n",
    "$(10,10) \\ldots │││\\circ\\circ$\n",
    "\n",
    "Tudíž každé dvoučlenné kombinaci s opakováním ze $4$ prvků $1, 2, 5, 10$ odpovídá jediná uspořádaná pětice o dvou tečkách a třech čárkách a naopak. Pro počet všech dvoučlenných kombinací s opakováním ze $4$ prvků $K'(2,4)$ tak platí  $K'(2,4) = P'(2,3)$.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Definice 1.9\n",
    "$k$-členná kombinace s opakováním z $n$ prvků je neuspořádaná $k$-tice sestavená z těchto prvků tak, že každý prvek se v ní vyskytuje nejvýše $k$-krát.\n",
    "```\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Věta 1.5\n",
    ":class: attention\n",
    "Počet $K'(k, n)$ $k$-členných kombinací s opakováním z $n$ prvků je\n",
    "\n",
    "$$K'(k,n)=P'(k, n-1)=\\frac{(k+(n-1))!}{k!\\cdot (n-1)!}={n+k-1 \\choose k}.$$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.19\n",
    ":class: warning\n",
    "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 některým z čísel $n + 1$, $n + 2$, $n + 3$, $\\ldots$ , $2 n$, kde $n$ je přirozené číslo. Kolik těchto trojúhelníků je \n",
    "\n",
    "a) rovnoramenných; \n",
    "\n",
    "b) rovnostranných?\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.20\n",
    ":class: warning\n",
    "V sáčku jsou červené, modré a zelené kuličky, přičemž kuličky téže barvy jsou nerozlišitelné. Určete, kolika způsoby lze vybrat pět kuliček, jestliže v sáčku je \n",
    "\n",
    "a) aspoň pět kuliček od každé barvy; \n",
    "\n",
    "b) pět červených, čtyři modré a čtyři zelené?\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dirichletův přihrádkový princip"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "````{prf:theorem}\n",
    "Je-li aspoň $k+1$ předmětů rozmístěno do $k$ přihrádek, pak v některé přihrádce jsou aspoň $2$ předměty.\n",
    "````\n",
    "\n",
    "```{admonition} Věta 1.6\n",
    ":class: attention\n",
    "Je-li aspoň $k+1$ předmětů rozmístěno do $k$ přihrádek, pak v některé přihrádce jsou aspoň $2$ předměty.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.21\n",
    ":class: warning\n",
    "Kolikrát po sobě je třeba hodit třemi hracími kostkami, aby při těchto hodech padl aspoň čtyřikrát týž součet ok na všech třech hracích kostkách.\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.22\n",
    ":class: warning\n",
    "Každý z deseti přátel poslal pěti z ostatních přátel vždy po jedné pohlednici. Dokažte, že aspoň dva z nich si poslali pohlednice navzájem.\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.23\n",
    ":class: warning\n",
    "Šachista se $77$ dní připravoval na turnaj. V rámci přípravy odehrál každý den aspoň jednu partii. Celkově však nesehrál více než $132$ partií. Dokažte, že v několika po sobě jdoucích dnech odehrál dohromady právě $21$ partií.\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pascalův trojúhelník"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Poznámka 1.5\n",
    ":class: hint\n",
    "Pro konečnou množinu $A$ budeme symbolem $|A|$ značit počet jejích prvků.\n",
    "```       "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Věta 1.7\n",
    ":class: attention\n",
    "Nechť $a_i$ , $i=1, 2,  \\ldots, n$ jsou konečné množiny. Pak platí \n",
    "\n",
    "$$|A_1 \\cup A_2 \\cup \\ldots \\cup A_n|= \\sum_{i=1}^n |A_i| - \\sum_{1 \\leq i < j \\leq n} |A_i \\cap A_j|+  \\sum_{1 \\leq i < j < k \\leq n} |A_i \\cap A_j \\cap A_k|- \\ldots + (-1)^{n-1} |A_1 \\cap A_2 \\cap \\ldots \\cap A_n|.$$\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Poznámka 1.6\n",
    ":class: hint\n",
    "Speciálně pro tři množiny platí:\n",
    "\n",
    "$$|A_1 \\cup A_2 \\cup A_3|= |A_1|+|A_2|+|A_3|-|A_1 \\cap A_2|- |A_1\\cap A_3|-|A_2\\cap A_3|+|A_1 \\cap A_2 \\cap A_3|.$$\n",
    "```       "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.24\n",
    ":class: warning\n",
    "Ze $100$ dětí se $28$ učí angličtinu, $30$ němčinu a $42$ francouzštinu. Angličtinu a němčinu se současně učí $8$ žáků, angličtinu s francouzštinou $10$ žáků a francouzštinu s němčinou $5$ žáků, přitom $3$ žáci se učí všem třem jazykům současně. Určete, kolik z těchto $100$ dětí se neučí žádný z uvedených cizích jazyků.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.25\n",
    ":class: warning\n",
    "Ve třídě je $28$ žáků, z nichž každý řeší aspoň jednu ze tří olympiád: matematickou, fyzikální, chemickou. Každou z uvedených olympiád řeší právě $14$ žáků třídy. Počet žáků, kteří řeší aspoň dvě olympiády je šestkrát větší než počet žáků řešících všechny tři olympiády. Dokažte, že existuje aspoň $6$ žáků třídy, kteří soutěží právě v jedné a téže olympiádě.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pascalův trojúhelník a binomická věta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Poznámka 1.8\n",
    ":class: hint\n",
    "Již jsme zmínili symetrickou vlastnost kombinačního čísla:\n",
    "\n",
    "$\\displaystyle {n \\choose k}={n \\choose {n-k}}$.\n",
    "\n",
    "Ukažme další zajímavou vlastnost: \n",
    "\n",
    "$\\displaystyle {n \\choose k}+{n \\choose {k+1}}={{n+1} \\choose {k+1}}$.\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.26\n",
    "\n",
    ":class: warning\n",
    "Vyjádřete jediným kombinačním číslem součet:\n",
    "\n",
    "$\\displaystyle {3 \\choose 3}+{4 \\choose 3}+{5 \\choose 3}+{6 \\choose 3}+{7 \\choose 3}$\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Poznámka 1.8\n",
    ":class: hint\n",
    "Vlastnosti kombinačních čísel je možné promítnout do tzv. Pascalova trojúhelníku.\n",
    "\n",
    "$$ {0 \\choose 0}$$\n",
    "$$ {0 \\choose 1} {1 \\choose 1}$$\n",
    "$$ {0 \\choose 2} {1 \\choose 2} {2 \\choose 2}$$\n",
    "$$ {0 \\choose 3} {1 \\choose 3} {2 \\choose 3}{3 \\choose 3}$$\n",
    "$$ {0 \\choose 4} {1 \\choose 4} {2 \\choose 4}{3 \\choose 4}{4 \\choose 4}$$\n",
    "$$ {0 \\choose 5} {1 \\choose 5} {2 \\choose 5}{3 \\choose 5}{4 \\choose 5}{5 \\choose 5}$$\n",
    "$$\\ldots\\ldots\\ldots\\ldots\\ldots\\ldots\\ldots\\ldots\\ldots\\ldots\\ldots$$\n",
    "\n",
    "\n",
    "```     "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.26\n",
    ":class: warning\n",
    "Příklad. Ve čtvercové síti tvořené jednotkovými čtverci je dán obdélník $ABCD$, jehož strany leží v přímkách této sítě a mají velikost $│AB│=5$, $│BC│=4$. Určete, kolika různými způsoby je možné se dostat z bodu $A$ do bodu $C$, postupujeme-li pouze po přímkách dané sítě a můžeme jít nahoru nebo vpravo.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Věta 1.8 - Věta binomická\n",
    ":class: attention\n",
    "Pro všechna čísla $a, b$ a každé přirozené číslo $n$ platí:\n",
    "\n",
    "$$\\displaystyle (a+b)^n={n \\choose 0} a^n b^0 + {n \\choose 1} a^{n-1} b^1 + {n \\choose 2} a^{n-2} b^2 + \\ldots + {n \\choose k} a^{n-k} b^{k} + \\ldots + {n \\choose {n-1}} a^1 b^{n-1} + {n \\choose n} a^0 b^n. $$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Příklad 1.27\n",
    ":class: warning\n",
    "Pomocí binomické věty dokažte, že číslo \n",
    "\n",
    "$$11^{10} - 1$$\n",
    "\n",
    "je dělitelné $100$.\n",
    "```"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}