7. előadás tételei
Variáció
\[
\text{n elemű A halamza}
\]
\[
\text{k-adosztályú variációja (ismétlés nélküli):}
\]
\[
\text{k hosszú sorozat A elemeiből mind különböző.}
\]
\[
\{1,2,\ldots,k\} \rightarrow \text{ injektív függvény}
\]
Állítás
\[
V_n^k \text{, egy n elemű k-ad osztályű variációinak száma:}
\]
\[
\frac{n!}{(n-k)!} = n \cdot (n-1) \cdot (n-2) \dots (n-k+1)
\]
Bizonyítás
Soroljuk osztályokba az összes n hosszú Permutáció, aszerint, hogy az első k elemünk mi.
\[
perm_1 \~{}\, perm_2\text{, ha az első k poziciói megegyzenek}
\]
pl. k=4, k=2
"Vizuális" "segítség"
\[
\text{Ekivalencia osztályok száma} \xRightarrow{\text{?}} V_n^k
\]
Ekivalencia osztály mérete megegyezik a maradék (n-k) elem permutációjával, azaz (n-k)! Össz méret: n! $$ V_n^k = \frac{n!}{(n-k)!} \checkmark $$
Kombináció
\[
\text{n elemű halmaz}
\]
\[
\text{k-ad osztályú kombinációja: }
\]
\[
\text{k elemű részhalmaza}
\]
Állítás
n eleme k-ad osztályú Kombinációnak száma:
\[
C_n^k = \binom{n}{k} := \frac{n!}{k!(n-k)!} = \frac{n\cdot(n-1)\ldots(n-k+1)}{k!} = \frac{V_n^k}{k!}
\]
Bizonyítás
\[
\text{A variációkon: } var_1 \~{}\, var_2 \iff \text{ halmazként ugyanaz.}
\]
\[
\text{Ekvivalencia osztály mérete: k!}
\]
\[
\text{Ekivalencia osztály szána: } C_n^k
\]
\[
\text{Összesen: } V_n^k \Rightarrow C_n^k = \frac{V_n^k}{k!}
\]
"Vizuális" "Reprezentáció"
Ismétléses varáció
\[
\text{n elemből k hosszú sorozat.}
\]
\[
\text{Lehet ismétlés. } (\{1,2,\ldots\} \rightarrow \text{ A függvényv})
\]
Állítás
Bizonyítás
\[
\text{k szerinti indukció: } k=1 \checkmark
\]
\[
k \rightarrow k+1: var_1 \~{}\, var_2 \iff \text{ első elem egyezik}
\]
\[
\text{Ekvivalencia osztály mérete: indukció szerint: }n^k
\]
\[
\text{kvivalencia osztály száma: n}
\]
Ismétléses Permutáció
\[
\text{r elemű halmaz: } \{a_1,a_2,\ldots,a_r\}
\]
\[
i_1,i_2,i_3,\ldots,i_r \in \mathbb{N}^+
\]
\[
i_1+i_2+\ldots+i_r=n
\]
\[
\text{Hány olyan sorozat van, melyben pontosan}
\]
\[
i_1 \text{ db } a_1 \text{, } i_2 \text{ db} a_2 \text{, } \ldots i_r \text{ db } a_r \text{ db szerepel.}
\]
Állítás
\[
\text{Ezek száma: } P_n^{i_1,i_2,\ldots,i_r} = \frac{n!}{i_1!\cdot i_2! \ldots i_r!}
\]
Bizonyítás
\[
\text{r szerinti indukció: r=1} \checkmark
\]
\[
r = 2 \text{: }
\]
\[
i_1 \text{db A} i_2 \text{ db B} \rightarrow ABAA \ldots B \Rightarrow n hosszú.
\]
\[
\text{Sorozat kódolása: Megmondom hányadik poziíción van az "A"}
\]
\[
\text{AAAABBBB} \iff \{1,2,3,4\}
\]
\[
\text{ABABBBAA} \iff \{1,3,7,8\}
\]
\[
\iff \text{Lehetőségek: n-ből } i_1 \text{ db } i_2 \text{ elemű részhalmaz}
\]
\[
\binom{n}{i_1} = \frac{n!}{i_1!(n-i_1)!} = \frac{n!}{i_1! \cdot i_2!}
\]
\[
\text{Mert } n-i_1 = i_2
\]
\[
\checkmark
\]
\[
r \rightarrow (r+1) \text{ :}
\]
\[
\text{Adjuk meg! 1, Hol melyik pozíción van } a_{r+1} \text{?}
\]
\[
\binom{n}{i_r+1}
\]
\[
\text{2, A többi } n-i_{r+1} \text{ Poziíciókon milyen részsorozatot alkot az } i_1 \text{ db} a_1 \text{, } i_2 \text{ db} a_2 \ldots i_r \text{ db} a_r
\]
\[
\text{Indukció } \rightarrow \frac{(n - i_{r+1})!}{i_1! \cdot i_2! \cdot \ldots \cdot i_r!}
\]
\[
\Rightarrow \text{Össz lehetőség:}
\]
\[
\binom{n}{i_{r+1}} \cdot \frac{(n-i_{r+1})!}{i_1! \ldots i_r!} = \frac{n!}{i_{r+1}! \cdot \sout{(n-i_{r+1})!}} \cdot \frac{\sout{(n-i_{r+1})!}}{i_1! \ldots i_r!}
\]
\[
\checkmark
\]