\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
