---
# System prepended metadata

title: Domácí úkol 6.2 - satna

---

# Domácí úkol 6.2 - satna
## 1. Počet permutací s právě jedním pevným bodem
***Š***$(n)$ je počet permutací bez pevného bodu na množině o $n$ prvcích. Můžeme tedy zvolit pevný bod ($n$ způsoby) a spočítat počet permutací bez pevného bodu na množinách o $n-1$ prvcích.
Počet permutací množiny o $m$ prvcích s alespoň jedním pevným bodem je obecně roven:
$$\sum^{m}_{k=1}(-1)^{k-1}*\frac{m!}{k!}$$
takže v případě množiny o $n-1$ prvcích to bude $\sum^{n-1}_{k=1}((-1)^{k-1}*\frac{(n-1)!}{k!})$
Jelikož počítáme doplněk (tedy množiny, které mají 0 pevných bodů), pak toto odečteme od celkového počtu permutací a dostáváme:
$(n-1)!-\sum^{n-1}_{k=1}((-1)^{k-1}*\frac{(n-1)!}{k!}) =$ ***Š***$(n-1)$
(Obecně platí, že ***Š***$(n-x)$ = $(n-x)!-\sum^{n-x}_{k=1}((-1)^{k-1}*\frac{(n-x)!}{k!})$.)
a jelikož je $n$ možností, jak vybrat náš pevný bod, je celkový počet roven 
$n*(n-1)!-\sum^{n-1}_{k=1}((-1)^{k-1}*\frac{(n-1)!}{k!})$ =
$n!-\sum^{n-1}_{k=1}((-1)^{k-1}*\frac{(n-1)!}{k!})$
## 2. Důkaz (ještě nedořešen)
Množinu rozdělíme na dvě strany: množinu o $k$ prvcích a $n-k$ prvcích. Dále ***Š***$(n-k)$ vyjadřuje, kolik je možných permutací o $k$ pevných bodech. Budou-li všechny pevné body na levé straně, je těchto permutací ***Š***$(n-k)$ (tzn. všechny permutace pravé strany bez pevného bodu).
Možností, jak rozdělit tuto množinu je $n \choose k$$= \frac{n!}{k!(n-k)!}$
Vynásobíme-li tyto dvě možnosti (zvolení pevných bodů $*$ počet permutací) dohromady, dostaneme ***Š***$(n-k)\frac{n!}{k!(n-k)!}$ = $[(n-k)!-\sum^{n-k}_{j=1}((-1)^{j-1}*\frac{(n-k)!}{j!})]$$*\frac{n!}{k!(n-k)!}$.
