Permutációk, variációk, kombinációk

Definíció — Faktoriális

Ha \(n \in \mathbb{N}\), akkor \(n! = 1 \cdot 2 \cdot \dots \cdot n\), valamint \(0! = 1\).

Tétel — Stirling-formula

Ha \(n \in \mathbb{N}\), akkor a faktoriális nagyságrendje:

\[ \sqrt{2\pi n} \cdot \left(\frac{n}{e}\right)^n \cdot e^{\frac{1}{12n+1}} < n! < \sqrt{2\pi n} \cdot \left(\frac{n}{e}\right)^n \cdot e^{\frac{1}{12n}} \]

ahol \(\pi \approx 3{,}14\) és \(e \approx 2{,}71\).

Tétel — egyszerűsített Stirling-formula \[ \sqrt{n^n} \le n! \le \left(\frac{n+1}{2}\right)^n \]

Emlékeztető — számtani és mértani közép közötti egyenlőtlenség

Bármely \(a, b > 0\) valós számokra:

\[ \sqrt{ab} \le \frac{a+b}{2} \]

Bizonyítás — az egyszerűsített Stirling-formula

Írjuk fel az \((n!)^2\) szorzatot a következő módon:

\[ (n!)^2 = (1 \cdot 2 \cdots (n-1) \cdot n) \cdot (1 \cdot 2 \cdots (n-1) \cdot n) \]

Párosítsuk össze a tényezőket az alábbiak szerint:

\[ (n!)^2 = (1 \cdot n) \cdot (2 \cdot (n-1)) \cdots (k \cdot (n+1-k)) \cdots (n \cdot 1) \]

Mindegyik tényező \(k(n+1-k)\) alakú, ahol \(k \in \{1, 2, \dots, n\}\).

1. Alsó becslés: Alakítsuk át a \(k(n+1-k)\) kifejezést:

\[ k(n+1-k) = (k-1)(n-k) + n \ge n \]

Mivel mindkét tényező nemnegatív, \(n \le k(n+1-k)\). Ebből \(n\) db tényező szorzataként:

\[ n^n \le (n!)^2 \implies \sqrt{n^n} \le n! \]

2. Felső becslés: Alkalmazzuk a számtani-mértani közép közötti egyenlőtlenséget:

\[ k(n+1-k) \le \left( \frac{k + (n+1-k)}{2} \right)^2 = \left(\frac{n+1}{2}\right)^2 \]

Ezt mind az \(n\) tényezőre alkalmazva:

\[ (n!)^2 \le \left(\frac{n+1}{2}\right)^{2n} \implies n! \le \left(\frac{n+1}{2}\right)^n \]

Definíció — Binomiális együttható

Legyen \(n, k \in \mathbb{N} \cup \{0\}\) és \(k \le n\). Ekkor az

\[ \binom{n}{k} = \frac{n!}{k!(n-k)!} \]

kifejezést binomiális együtthatónak nevezzük (olvasd: "\(n\) alatt a \(k\)").

Megjegyzés — Pascal-háromszög

A binomiális együtthatókat táblázatba rendezhetjük: \(\binom{n}{k}\) kerül az \(n\)-edik sor \(k\)-adik helyére. A sorok és az elemek számozása 0-val kezdődik:

\[ \begin{array}{ccccccc} & & & \binom{0}{0} & & & \\ & & \binom{1}{0} & & \binom{1}{1} & & \\ & \binom{2}{0} & & \binom{2}{1} & & \binom{2}{2} & \\ \binom{3}{0} & & \binom{3}{1} & & \binom{3}{2} & & \binom{3}{3} \end{array} \]

Definíció — Ismétlés nélküli permutáció

Legyen \(n \in \mathbb{N}\) és \(X\) egy \(n\) elemű halmaz. Az \(X\) elemeinek egy ismétlés nélküli permutációja egy olyan rendezett \(n\)-es, amiben \(X\) minden eleme pontosan egyszer szerepel.

Tétel

Ha \(n \in \mathbb{N}\), akkor \(n\) db elem ismétlés nélküli permutációinak száma:

\[ P_n = n! \]

Bizonyítás

Az első helyre \(n\) féle elem kerülhet, a második helyre \((n-1)\) féle elem, és így tovább — az \(n\)-edik helyre már csak 1 elem kerülhet. Így a lehetőségek száma:

\[ P_n = n \cdot (n-1) \cdots 1 = n! \]

Definíció — Ismétléses permutáció

Legyen \(n \in \mathbb{N}\) és \(X\) egy \(n\) elemű multihalmaz. Az \(X\) elemeinek egy ismétléses permutációja egy olyan rendezett \(n\)-es, melyben \(X\) minden eleme annyiszor szerepel, amennyi a multiplicitása.

Tétel — ismétléses permutációk száma

Ha \(n \in \mathbb{N}\) és az adott \(n\) elem között \(r\)-féle elem van, melyek multiplicitása \(k_1, k_2, \dots, k_r\) (ahol \(k_1 + k_2 + \dots + k_r = n\)), akkor ezek ismétléses permutációinak száma:

\[ P_n^{k_1, k_2, \dots, k_r} = \frac{n!}{k_1! \cdot k_2! \cdot \dots \cdot k_r!} \]

Bizonyítás

Ideiglenesen megkülönböztetjük az azonos elemeket. Álljon relációban az új elemek két ismétlés nélküli permutációja, ha a megkülönböztetés elhagyásával ugyanazt az ismétléses permutációt adják.

Példa a relációra: ha az elemek \(a, a, a, b, c, c \implies a^{(1)}, a^{(2)}, a^{(3)}, b^{(1)}, c^{(1)}, c^{(2)}\), akkor:

\[ (c^{(2)}, a^{(1)}, a^{(3)}, b^{(1)}, c^{(1)}, a^{(2)}) \sim (c^{(1)}, a^{(2)}, a^{(3)}, b^{(1)}, c^{(2)}, a^{(1)}) \]

Ez a reláció reflexív, szimmetrikus, tranzitív \(\implies\) ekvivalenciareláció \(\implies\) osztályozást hoz létre az új elemek ismétlés nélküli permutációinak körében.

• Az ekvivalenciaosztályok az eredeti elemek ismétléses permutációinak felelnek meg.
• Egy ekvivalenciaosztályban \(k_1! \cdot k_2! \cdots k_r!\) db ismétlés nélküli permutáció van, hiszen az \(i\)-edik típusú elem helye ugyan rögzített, de egymás közt \(k_i!\)-féleképpen permutálhatók (\(i = 1, \dots, r\)).

Ebből adódóan:

\[ P_n^{k_1, \dots, k_r} = \text{ekv. oszt. száma} = \frac{P_n}{k_1! \cdots k_r!} = \frac{n!}{k_1! \cdots k_r!} \]

Definíció

Legyen \(n, k \in \mathbb{N}, k \le n\) és \(X\) egy \(n\) elemű halmaz. \(X\) elemeinek egy \(k\)-ad osztályú ismétlés nélküli variációja olyan rendezett \(k\)-as, amelyben különböző \(X\)-beli elemek állnak.

Tétel

Ha \(n, k \in \mathbb{N}, k \le n\), akkor \(n\) db elem \(k\)-ad osztályú ismétlés nélküli variációinak száma:

\[ V_n^k = \frac{n!}{(n-k)!} \]

Bizonyítás

Az 1. elem \(n\)-féleképpen választható, a 2. elem \((n-1)\)-féleképpen, ..., a \(k\)-adik elem \((n-k+1)\)-féleképpen. Így:

\[ V_n^k = n \cdot (n-1) \cdots (n-k+1) = \frac{n!}{(n-k)!} \]

Definíció

Legyen \(n, k \in \mathbb{N}\) és \(X\) egy \(n\) elemű halmaz. \(X\) elemeinek egy \(k\)-ad osztályú ismétléses variációja egy olyan rendezett \(k\)-as, amelyben \(X\)-beli elemek állnak.

Tétel

Ha \(n, k \in \mathbb{N}\), akkor \(n\) db elem \(k\)-ad osztályú ismétléses variációinak száma:

\[ V_n^{k, \text{ism}} = n^k \]

Bizonyítás

Az 1. elem \(n\)-féleképpen választható, és a többi is mind \(n\)-féleképpen választható (\(n \cdot n \cdots n = n^k\)).

Definíció

Legyen \(n, k \in \mathbb{N}, k \le n\) és \(X\) egy \(n\) elemű halmaz. \(X\) elemeinek egy \(k\)-ad osztályú ismétlés nélküli kombinációja az \(X\)-nek egy \(k\) elemű részhalmaza.

Tétel

Ha \(n, k \in \mathbb{N}, k \le n\), akkor \(n\) db elem \(k\)-ad osztályú ismétlés nélküli kombinációinak száma:

\[ C_n^k = \binom{n}{k} \]

Bizonyítás — ekvivalenciarelációval

Ideiglenesen tegyük fel, hogy számít a választott elemek sorrendje. Két ilyen ismétlés nélküli variáció álljon relációban, ha ugyanazokat az elemeket tartalmazzák, csak esetleg más sorrendben. Pl.: \(X = \{a, b, c, d, e\} \implies (c, e, a) \sim (e, a, c)\).

Ez a reláció reflexív, szimmetrikus, tranzitív \(\implies\) ekvivalenciareláció \(\implies\) osztályozást hoz létre a \(k\)-ad osztályú ismétlés nélküli variációk körében.

• Az ekvivalenciaosztályok a \(k\)-ad osztályú ismétlés nélküli kombinációknak felelnek meg.
• Egy ekvivalenciaosztályban \(k!\) db \(k\)-ad osztályú ismétlés nélküli variáció van, hiszen a \(k\) db elem ennyiféleképpen rakható sorba.

\[ C_n^k = \text{ekv. oszt. száma} = \frac{V_n^k}{k!} = \frac{\frac{n!}{(n-k)!}}{k!} = \frac{n!}{k!(n-k)!} = \binom{n}{k} \]

Bizonyítás — karakterisztikus vektorokkal (bijekcióval)

Kódoljuk el a \(k\)-ad osztályú ismétlés nélküli kombinációkat a következőképp: legyen \(X = \{x_1, \dots, x_n\}\). A kódja legyen egy \(A \in \mathcal{P}_k(X) \mapsto (b_1, \dots, b_n) \in \{0, 1\}^n\) karakterisztikus vektor (\(k\) db 1-esből és \(n-k\) db 0-ból álló rendezett \(n\)-es), ahol:

\[ b_i = \begin{cases} 1, & \text{ha } x_i \in A \\ 0, & \text{ha } x_i \notin A \end{cases} \]

Ez a függvény injektív (különböző részhalmazok karakterisztikus vektora különböző) és szürjektív (minden \(k\) db 1-esből álló vektor egy \(k\) elemű részhalmaz kódja) \(\implies\) bijektív.

Így a \(k\) elemű részhalmazok száma megegyezik a \(k\) db 1-esből és \(n-k\) db 0-ból álló sorozatok számával:

\[ C_n^k = P_n^{k, n-k} = \frac{n!}{k!(n-k)!} = \binom{n}{k} \]

Definíció

Legyen \(n, k \in \mathbb{N}\) és \(X\) egy \(n\) elemű halmaz. \(X\) elemeinek egy \(k\)-ad osztályú ismétléses kombinációja egy \(k\) elemű multihalmaz, melynek elemei \(X\)-ből valók.

Tétel

Ha \(n, k \in \mathbb{N}\), akkor \(n\) elem \(k\)-ad osztályú ismétléses kombinációinak száma:

\[ C_n^{k, \text{ism}} = \binom{n+k-1}{k} \]

Bizonyítás — eltolásos indexelés

Legyen \(X = \{x_1, \dots, x_n\}\) és legyen \(Y = \{y_1, \dots, y_{n+k-1}\}\) segédhalmaz. Vegyük a következő hozzárendelést:

\[ \{x_{i_1}, x_{i_2}, \dots, x_{i_k}\} \quad (1 \le i_1 \le i_2 \le \dots \le i_k \le n) \]

(az elemek felsorolva növekvő sorszámmal). A sorszámokhoz adjunk rendre \(0, 1, 2, \dots, k-1\)-et:

\[ \mapsto \{y_{i_1}, y_{i_2+1}, \dots, y_{i_k+k-1}\} \quad (1 \le i_1 < i_2+1 < \dots < i_k+k-1 \le n+k-1) \]

Ez a függvény injektív és szürjektív \(\implies\) bijektív (visszafelé levonjuk a \(0, 1, \dots, k-1\)-et). Így:

\[ C_n^{k, \text{ism}} = C_{n+k-1}^k = \binom{n+k-1}{k} \]

Bizonyítás — golyó-fal kódolás

Kódoljuk el a \(k\)-ad osztályú ismétléses kombinációkat a következőképpen: legyen \(X = \{x_1, \dots, x_n\}\).

• Leírunk annyi 1-est, ahányszor \(x_1\)-et választottuk;
• elválasztó 0;
• leírunk annyi 1-est, ahányszor \(x_2\)-t választottuk;
• elválasztó 0;
• …
• leírunk annyi 1-est, ahányszor \(x_n\)-et választottuk.

Így a kód: \(k\) db 1-esből és \(n-1\) db 0-ból álló rendezett \((k+n-1)\)-es.

Ez a függvény bijektív, ezért az ismétléses kombinációk száma:

\[ C_n^{k, \text{ism}} = P_{n+k-1}^{k, n-1} = \frac{(k+n-1)!}{k! \cdot (n-1)!} = \binom{k+n-1}{k} \]