Binomiális együtthatók és azonosságaik

Tétel

Legyen \(k, n \in \mathbb{N}\), \(|A| = k, |B| = n\).

1. Az \(f: A \to B\) függvények száma: \(n^k\).
2. Az \(f: A \to B\) injektív függvények száma: \[ \begin{cases} \frac{n!}{(n-k)!}, & \text{ha } k \le n \\ 0, & \text{ha } k > n \end{cases} \]
3. Az \(f: A \to B\) bijektív függvények száma: \[ \begin{cases} n!, & \text{ha } k = n \\ 0, & \text{ha } k \neq n \end{cases} \]

Bizonyítás

Legyen \(A = \{a_1, \dots, a_k\}\). Egy \(f: A \to B\) függvény leírható az értéktáblázattal:

\[ \begin{array}{c|c|c|c} a_1 & a_2 & \dots & a_k \\ \hline f(a_1) & f(a_2) & \dots & f(a_k) \end{array} \]

1. A táblázat második sora a \(B\)-beli elemek egy \(k\)-ad osztályú ismétléses variációja \(\implies n^k\).
2. Ha \(k > n\), akkor a skatulya-elv szerint lesz két \(A\)-beli elem, melyek képe azonos \(\implies f\) nem injektív. Ha \(k \le n\), akkor a második sor a \(B\)-beli elemek egy \(k\)-ad osztályú ismétlés nélküli variációja \(\implies \frac{n!}{(n-k)!}\).
3. Ha \(k \neq n\), nincs bijektív fv. Ha \(k = n\), a második sor a \(B\)-beli elemek egy ismétlés nélküli permutációja \(\implies n!\).

Tétel

Ha \(n \in \mathbb{N} \cup \{0\}\), akkor \(\binom{n}{0} = 1\).

Bizonyítás

Láttuk, hogy \(\binom{n}{k}\) az \(n\) elemű halmaz \(k\) elemű részhalmazainak száma. Egy \(n\) elemű halmaznak egyetlen 0 elemű részhalmaza van: \(\emptyset\). Algebrailag: \(\binom{n}{0} = \frac{n!}{0! \cdot n!} = 1\).

Tétel

Ha \(n \in \mathbb{N} \cup \{0\}\), akkor \(\binom{n}{n} = 1\).

Bizonyítás

\(n\) elemű halmaznak egyetlen \(n\) elemű részhalmaza van, önmaga.

Tétel

Ha \(n \in \mathbb{N}\), akkor \(\binom{n}{1} = n\) és \(\binom{n}{n-1} = n\).

Bizonyítás

\(n\) elemű halmaz 1 elemű részhalmazainak száma \(= n\). Az \((n-1)\) elemű részhalmazok száma szintén \(n\), hiszen pontosan 1 elem hiányzik belőlük.

Tétel — szimmetria

Ha \(n, k \in \mathbb{N} \cup \{0\}\) és \(k \le n\), akkor:

\[ \binom{n}{k} = \binom{n}{n-k} \]

Bizonyítás

Legyen \(|X| = n\) és vegyük a következő leképezést:

\[ A \in \mathcal{P}_k(X) \mapsto X \setminus A \in \mathcal{P}_{n-k}(X) \quad (A \text{ komplementere}) \]

Ez a függvény injektív (különböző részhalmazok komplementere különböző) és szürjektív (minden \(n-k\) elemű részhalmaz egy \(k\) eleműnek a komplementere) \(\implies\) bijektív.

\[ \implies |\mathcal{P}_k(X)| = |\mathcal{P}_{n-k}(X)| \implies \binom{n}{k} = \binom{n}{n-k} \]

Tétel — a Pascal-háromszög additív tulajdonsága

Ha \(n, k \in \mathbb{N}\) és \(k \le n\), akkor:

\[ \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k} \]

Bizonyítás

Legyen \(|X| = n+1\). Ennek \(\binom{n+1}{k}\) darab \(k\) elemű részhalmaza van.

Másképp számolva: rögzítsünk egy \(y \in X\) elemet. \(X\) egy \(k\) elemű részhalmaza kétféle lehet:

• Ha \(y\) benne van: a többi \(n\) elemből kell még választani \(k-1\) darabot. Ez \(\binom{n}{k-1}\) lehetőség.
• Ha \(y\) nincs benne: a többi \(n\) elemből kell választani \(k\) darabot. Ez \(\binom{n}{k}\) lehetőség.

Összesen: \(\binom{n}{k-1} + \binom{n}{k}\) lehetőség van.

Tétel — 1. elnyelési tulajdonság

Ha \(n, k \in \mathbb{N}\) és \(k \le n\), akkor:

\[ \binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1} \iff k \binom{n}{k} = n \binom{n-1}{k-1} \]

Bizonyítás

Legyen \(|X| = n\). Számoljuk össze az olyan \((A, a)\) párokat, ahol \(A \subseteq X\), \(|A| = k\) és \(a \in A\).

• 1. módszer: Először az \(A\) részhalmazt választjuk ki \(\binom{n}{k}\)-féleképpen, majd ebből az \(a\) elemet \(k\)-féleképpen. Így \(\binom{n}{k} \cdot k\) darab pár van.
• 2. módszer: Először az \(a\) elemet választjuk ki \(n\)-féleképpen. Ezután \(A\) többi \(k-1\) elemét a maradék \(n-1\) elemből \(\binom{n-1}{k-1}\)-féleképpen választhatjuk ki. A párok száma: \(n \cdot \binom{n-1}{k-1}\).

A két számlálás eredménye egyenlő: \(k \binom{n}{k} = n \binom{n-1}{k-1}\).

Tétel — 2. elnyelési tulajdonság

Ha \(n, k \in \mathbb{N}\) és \(k \le n\), akkor:

\[ \binom{n}{k} = \frac{n-k+1}{k} \binom{n}{k-1} \iff k \binom{n}{k} = (n-k+1) \binom{n}{k-1} \]

Bizonyítás

Ugyanazokat az \((A, a)\) párokat számoljuk össze, mint az előző tételben (\(|A| = k, a \in A\)).

• Tudjuk, hogy a párok száma: \(\binom{n}{k} \cdot k\).
• Másrészt: először kiválasztjuk az \(A\)-nak az \(a\)-tól különböző \(k-1\) elemét \(\binom{n}{k-1}\)-féleképpen. Majd az \(a\) elem kiválasztása a maradék \(n-(k-1) = n-k+1\) elemből történhet.

Így a párok száma: \(\binom{n}{k-1} \cdot (n-k+1)\), amiből az állítás adódik.

Tétel — hatványhalmaz elemszáma

Ha \(n \in \mathbb{N} \cup \{0\}\), akkor:

\[ \sum_{k=0}^{n} \binom{n}{k} = 2^n \]

Bizonyítás

Legyen \(X = \{x_1, \dots, x_n\}\). \(X\) összes részhalmazának száma egyrészt a \(k\) elemű részhalmazok összege: \(\sum_{k=0}^n \binom{n}{k}\). Másrészt bijekció adható meg a részhalmazok és a \(2^n\) darab \(n\) hosszúságú \(\{0,1\}\) karakterisztikus vektorok között.

\[ |\mathcal{P}(X)| = V_2^{n, \text{ism}} = 2^n \implies \sum_{k=0}^{n} \binom{n}{k} = 2^n \]

Tétel — előjeles sorösszeg

Legyen \(n \in \mathbb{N}\). Ekkor:

\[ \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 \iff \binom{n}{0} + \binom{n}{2} + \dots = \binom{n}{1} + \binom{n}{3} + \dots \]

Bizonyítás

Legyen \(|X| = n\) és rögzítsünk egy \(y \in X\) elemet. Tekintsük a következő leképezést a páros elemszámú részhalmazokból a páratlan elemszámú részhalmazokba:

\[ f: A \in \mathcal{P}_{\text{páros}}(X) \mapsto \begin{cases} A \setminus \{y\}, & \text{ha } y \in A \\ A \cup \{y\}, & \text{ha } y \notin A \end{cases} \in \mathcal{P}_{\text{páratlan}}(X) \]

Ez a leképezés bijektív, amiből következik, hogy a páros és páratlan elemszámú részhalmazok száma megegyezik:

\[ |\mathcal{P}_{\text{páros}}(X)| = |\mathcal{P}_{\text{páratlan}}(X)| \implies |\mathcal{P}_{\text{páros}}(X)| - |\mathcal{P}_{\text{páratlan}}(X)| = 0 \]

Tétel — Vandermonde-azonosság speciális esete

Ha \(n \in \mathbb{N} \cup \{0\}\), akkor:

\[ \sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n} \]

Bizonyítás

Legyen \(X = \{x_1, \dots, x_n, y_1, \dots, y_n\}\) egy \(2n\) elemű halmaz. Ennek \(\binom{2n}{n}\) darab \(n\) elemű részhalmaza van.

Másképp: válasszunk ki az \(x_i\)-k közül \(k\) darab elemet \(\binom{n}{k}\)-féleképpen, majd az \(y_j\)-k közül \(n-k\) darabot \(\binom{n}{n-k} = \binom{n}{k}\)-féleképpen. Adott \(k\)-ra a lehetőségek száma \(\binom{n}{k}^2\). Summázva \(k=0\)-tól \(n\)-ig megkapjuk az állítást.

Tétel — hokiütő-szabály

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

\[ \sum_{j=k}^{n} \binom{j}{k} = \binom{n+1}{k+1} \]

Bizonyítás

Legyen \(X = \{x_1, \dots, x_n, x_{n+1}\}\). \(X\) \(k+1\) elemű részhalmazainak száma \(\binom{n+1}{k+1}\).

Csoportosítsuk ezen részhalmazokat a bennük lévő legnagyobb sorszámú elem (\(x_j\)) szerint (\(j = k+1, \dots, n+1\)). Ha a legnagyobb elem \(x_j\), akkor az \(x_1, \dots, x_{j-1}\) elemekből kell \(k\) darabot kiválasztani, ami \(\binom{j-1}{k}\) lehetőség. Összegezve megkapjuk az azonosságot.

Tétel — binomiális tétel

Legyen \(R\) kommutatív gyűrű (pl. \(\mathbb{Z}, \mathbb{R}, \mathbb{Q}\)), \(a, b \in R\) és \(n \in \mathbb{N}\). Ekkor:

\[ (a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k} \]

Bizonyítás

\((a+b)^n = (a+b)(a+b)\cdots(a+b)\) (\(n\) db tényező). A beszorzás elvégzése után minden tag \(a^k b^{n-k}\) alakú. Egy ilyen taghoz az \(n\) db tényező közül \(k\) db-ban kell az \(a\)-t választani (a többiben \(b\)-t), ami \(\binom{n}{k}\)-féleképpen lehetséges.

Tétel — polinomiális (multinomiális) tétel

Legyen \(R\) kommutatív gyűrű, \(a_1, \dots, a_r \in R\) és \(n \in \mathbb{N}\). Ekkor:

\[ (a_1 + a_2 + \dots + a_r)^n = \sum_{\substack{k_1, \dots, k_r \in \mathbb{N} \cup \{0\} \\ k_1 + \dots + k_r = n}} \frac{n!}{k_1! \cdot k_2! \cdots k_r!} a_1^{k_1} a_2^{k_2} \cdots a_r^{k_r} \]

Bizonyítás

Az \(n\) tényezős szorzat kibontásakor a tagok \(a_{i_1} a_{i_2} \cdots a_{i_n}\) alakúak. Egy adott \(a_1^{k_1} \cdots a_r^{k_r}\) tag előfordulási száma megegyezik azon sorozatok számával, ahol \(k_1\) db 1-es, \(k_2\) db 2-es, …, \(k_r\) db \(r\)-es szerepel. Ez pontosan az ismétléses permutációk száma: \(P_n^{k_1, \dots, k_r} = \frac{n!}{k_1! \cdots k_r!}\).