%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%% file:      v2.tex                                                        %%%
%%% author:    Ján Komara                                                    %%%
%%% email:     komara@fmph.uniba.sk                                          %%%
%%% copyright: public domain                                                 %%%
%%% version:   2019/10/27                                                    %%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[12pt,a4paper]{article}

\usepackage[slovak]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage{amsmath}
\usepackage{amssymb}

\usepackage{lmodern}
\usepackage{indentfirst}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{Vzorový príklad pre 2. domácu úlohu}

\author{Ján Komara}

%\date{}
\date{\today}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Príklad}

Koľko permutácií množiny $\{ 1,2,\dotsc,n \}$ nenecháva žiadne číslo na svojom 
mieste?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Riešenie}

Nech $U$ je množina všetkých permutácií množiny
\(
S = \{ 1,2,\dotsc,n \}
\).
Symbolom $A_i$ pre $1 \leq i \leq n$ označme množinu tých permutácií z $U$,
ktoré nechajú $i$-tý prvok množiny $S$ na svojom mieste.
Množiny
\(
A_{i_1} \cap A_{i_2} \cap \dotsm \cap A_{i_k} 
\)
majú rovnako veľa prvkov pre ľubovolný výber $k$ čísel
\(
1 \leq i_1 < i_2 < \dotsc < i_k \leq n
\).
Platí totiž
\begin{align*}
|A_{i_1} \cap A_{i_2} \cap \dotsm \cap A_{i_k}| =
|A_1 \cap A_2 \cap \dotsm \cap A_k| = 
(n-k)!
.
\end{align*}
Hľadaný počet je preto rovný číslu
\begin{align*}
\left| \overline{A_1} \cap \overline{A_2} \cap \dotsm \cap \overline{A_n} \right| & =
\sum_{k=0}^{n} (-1)^k \binom{n}{k} |A_{1} \cap A_{2} \cap \dotsm \cap A_{k}| =
\\ & =
\sum_{k=0}^{n} (-1)^k \binom{n}{k} (n-k)!
.
\end{align*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
