7. előadás
Variáció
Variáció: \(n\) elemű \(A\) halmaz \(k\)-ad osztályú variációja (ismétlés nélkül): \(k\) hosszú sorozat \(A\) elemeiből mind különböző. (\(\{1, 2, \dots, k\} \to A\) injektív függvény).
Áll:
\(V_n^k\), egy \(n\) elemű halmaz \(k\)-ad osztályú variációinak száma:
\[ \frac{n!}{(n-k)!} = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1) \]Szerint, hogy az első \(k\) elemünk mi
\(perm_1 \sim perm_2\), ha az első \(k\) pozíció megegyezik.
Ekvivalencia osztályok száma: \(V_n^k\)
Ekvivalencia osztályok mérete: a maradék \((n-k)\) elem permitációja: \((n-k)!\)
Össz méret: \(n!\)
Tehát, \(V_n^k = \frac{n!}{(n-k)!}\)
Kombináció
\(n\) elemű halmaz \(k\)-ad osztályú kombinációja
Áll: \(n\) elem \(k\)-ad osztályú kombinációk száma:
\(\binom{n}{k} := \frac{n!}{k! \cdot (n-k)!} = \frac{n(n-1)(n-2)~\cdots~(n-k+1)}{k!}=\frac{V_n^k}{k!}\)
Ismétléses variáció
Ha \(n\) elemből visszatevéssel választunk ki k db elemet, akkor az n elem ismétléses variációja.
Ennek száma:
\(n^k\)
Ismétléses permutáció
Adott \(r\) elemű halmaz: \(\{a_1, a_2, \dots, a_r\}\) és \(i_1, i_2, \dots, i_r \in \N^+ \quad i_1+i_2+\dots+i_r = n\) (azaz vannak azonos elemek)
Hány olyan sorozat van, amelyben pontosan \(i_1\) db \(a_1\), \(i_2\) db \(a_2\), \(\cdots\) ,\(i_r\) db \(a_r\) szerepel.
Ezek száma: \(P_n^{i_1, i_2, \dots, i_r} = \frac{n!}{i_1! \; \cdot \; i_2! \; \cdot \; \dots \; \cdot \; i_r!}\)
| Permutáció | Variáció | Kombináció | |
|---|---|---|---|
| Ismétlés nélküli | \(n!\) | \(\frac{n!}{(n-k)!}\) | \(\binom{n}{k}=\frac{n!}{n! \; \cdot \; (n-k)!}\) |
| Ismétléses | \(\frac{n!}{i_1! \; \cdot \; i_2! \; \cdots \; i_3!}\) | \(n^k\) | \(\binom{n+k-1}{k}\) |
Binomiális tétel
Ha \(x, y\), ahol \(xy=yx\)
\(n\in\N^+\):
Polinomiális tétel
\((x_1+x_2+x_3+\cdots+x_n)^n\) kifejezésből, az \(x_1^{i_1}x_2^{i_2} \ldots x_n^{i_n}\) ta együtthatója: \(\frac{n!}{i_1! \; \cdot \; i_2! \; \cdot \; \ldots \; \cdot \; i_n!}\)
Pascal háromszög
A pascal háromszög egy sorában lévő elemek összege \(2^n\):
?????