\input /home/pasky/school/fastex/lib.tex

\subchapter{Permutace a faktoriál}{

	{\bf Permutace} konečné množiny $X$: Libovolná bijekce $\pi\colon X\bijection X$.

	\example{
		Mějme množinu $X = \{a,b,c,d\}$, definujme permutaci
		$\pi(a)=b$, $\pi(b)=d$, $\pi(c)=c$, $\pi(d)=a$. Matice
		permutace pak je
		$$\pmatrix{a & b & c & d\cr b & d & c & a},$$
		permutace tvoří uspořádání
		$$(b, d, c, a)$$
		a dá se vyjádřit na grafu jako
		\asciiart{
a * ---> * b
     _   |
    |\   |
       \ v
c *<-\   * d
   \-/
}
	}

	\shortdef{$n$ faktoriál}{$n! = 1\cdot2\cdot3\cdots n$, $0! = 1$}

	\declaration{
		Počet permutací $n$-prvkové množiny je $n!$.

		\proof{
			$n$ možností, kam se zobrazí první prvek.

			$n-1$ možností, kam se zobrazí druhý prvek.

			\dots
		}
	}

	\theorem{}{}{
		$|X| = n$, $|Y| = k$. Pak existuje:
		\list{
			\olistItem{$k^n$ zobrazení $X \to Y$.}
			\olistItem{$k(k-1)(k-2)\ldots(k-n+1)$ prostých zobrazení $X \to Y$.}
			\olistItem{$k!=n!$ bijekcí $X \bijection Y$, pokud $k = n$.}
			\olistItem{$0$ bijekcí $X \bijection Y$, pokud $k \ne n$.}
		}
	}

}

\subchapter{Kombinační čísla}{

	\definition{
		Kombinační číslo (neboli {\bf binomický koeficient}):
		$$ \cn{n}{k} = {n!\over k!(n-k)!} = {n(n-1)\ldots(n-k+1)\over k(k-1)\ldots1}\qquad n,k\in\nat_0,\ n\ge k $$
	}

	\scpart{Alternativní definice:}{
		$\displaystyle{\cn{n}{k}}$ je počet $k$-prvkových podmnožin $n$-prvkové množiny.
	}

	\declaration{
		Obě definice jsou ekvivalentní.

		\proof{
			Nechť $|X|=n$. Pak počet uspořádaných $k$-tic různých prvků z $X$
			je kombinatorickou úvahou $$n(n-1)(n-2)\ldots(n-k+1) = {n!\over (n-k)!}.$$
			Zároveň však tento počet můžeme spočítat přes kombinační čísla
			jako $($počet $k$-prv\-ko\-vých
			podmnožin $X)\times($počet možných uspořádání$) = \displaystyle{\cn{|X|}{k}k! = {n!\over(n-k)!}}$.

			\qed
		}
	}

	\scpart{Značení:}{
		Buď $X$ množina. Pak $\displaystyle{\cn{X}{k}}$ je množina všech $k$-prvkových podmnožin
		množiny $X$. Navíc $$\left|\cn{X}{k}\right| = \cn{|X|}{k}.$$
	}

	Platí:
	\list{
		\listItem{Symetrie:
			$$\cn{n}{k} = \cn{n}{n-k}\qquad n \ge k \ge 0$$
			\proof{Z definice kombinačního čísla (algebraicky nebo doplňky).}
		}
		\listItem{Sousední čísla:
			$$\cn{n}{k} = \cn{n-1}{k-1} + \cn{n-1}{k}$$
			\proof{Z množinové definice kombinačního čísla:
				$$\left|\cn{X}{k}\right|
					= \undernote{\left|\cn{X\setminus\{x_n\}}{k-1}\right|
						     }{\textbox{\eightrm počet $k$-prvkových podm.}\atop
						       \textbox{\eightrm množiny $X$ obs. $x_n$}}
					+ \undernote{\left|\cn{X\setminus\{x_n\}}{k}\right|
						     }{\textbox{\eightrm počet $k$-prvkových podm.}\atop
						       \textbox{\eightrm množiny $X$ neobs. $x_n$}}
					$$

				\qed
			}
		}
	}

	\scpart{Pascalův trojúhelník}{
		Ve vrcholu $\triangle$ je 1, okraje jsou lemovány nulami,
		každý prvek je součtem dvou prvků nad ním.

		\tabskip5pt
		$$\vbox{\halign{
			\hfil$\displaystyle{#}$&&
			\hfil$\displaystyle{#}$\cr
			 & & & &1\cr
			   & & &1&&1\cr
			     & &1&&2&&1\cr
			       &1&&3&&3&&1\cr
			        1&&4&&6&&4&&1\cr
			}
		}$$

		Pohled přes kombinační čísla:
		%\def\M#1{$\displaystyle{#1}$}
		\def\M#1{#1}
		$$\vbox{\halign{
			\hfil$\displaystyle{#}$&&
			\hfil$\displaystyle{#}$\cr
			 & & & &\M{\cn{0}{0}}\cr
			   & & &\M{\cn{1}{0}}&&\M{\cn{1}{1}}\cr
			     & &\M{\cn{2}{0}}&&\M{\cn{2}{1}}&&\M{\cn{2}{2}}\cr
			       &\M{\cn{3}{0}}&&\M{\cn{3}{1}}&&\M{\cn{3}{2}}&&\M{\cn{3}{3}}\cr
			        \M{\cn{4}{0}}&&\M{\cn{4}{1}}&&\M{\cn{4}{2}}&&\M{\cn{4}{3}}&&\M{\cn{4}{4}}\cr
			}
		}$$
		neboť $\displaystyle{\cn{n}{k} = \cn{n-1}{k-1}+\cn{n-1}{k}}$.
	}

	\scpart{Binomická věta}{
		\scpart{Víme:}{
			$\displaystyle{(x+y)^2 = x^2 + 2xy + y^2}$

			$\displaystyle{(x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3}$
		}
		$$ (x+y)^n = \sum_{k=0}^n \cn{n}{k} x^ky^{n-k}\qquad n \in \nat_0,\ x,y \in \real $$

		\proof{
			Indukcí podle $n$:
			\list{
				\nlistItem{$n = 0$, $n = 1$

					$$\eqalign{(x + y)^0 &= \cn{0}{0}x^0y^0 = 1\cr
					           (x + y)^1 &= \cn{1}{0}x^0y^1 + \cn{1}{1}x^1y^0}$$
				}
				\nlistItem{$n \Rightarrow n+1$

					$$ (x+y)^{n+1} = (x+y)^n(x+y)
						= (x+y)\left(\cn{n}{0}x^0y^n+\cdots+\cn{n}{n}x^ny^0\right) = $$
					$$ = \cn{n}{0}x^1y^n+\cdots+\cn{n}{n}x^{n+1}y^0
						+ \cn{n}{0}x^0y^{n+1} + \cdots + \cn{n}{n}x^ny^1 = $$
					$$ = \cn{n+1}{0}x^0y^{n+1} + \cn{n+1}{1}x^1y^n
						+ \cdots + \cn{n+1}{n}x^ny^1 + \cn{n+1}{n+1}x^{n+1}y^0 = $$
					$$ = \sum_{k=0}^{n+1} \cn{n+1}{k} x^ky^{(n+1)-k} $$
				}
			}
		}

		\impl{
			$$ (1+x)^n = \sum_{k=0}^n \cn{n}{k} x^k $$
		}
	}

}


\bend