Kółeczko z kombinatoryki - teoria  29 października 2009

Definicja 1. Permutacja to bijekcja ze zbioru {1, 2, …, n} na samego siebie. n! (n silnia) oznacza liczbę wszystkich możliwych permutacji zbioru {1, 2, …, n}.

n! = 1 · 2 · 3 · . . . · n dla n ∈ ℕ oraz 0! = 1.

Definicja 2. k-wyrazowa wariacja bez powtórzeń zbioru {1, 2, …, n} to przypisanie elementom z tego zbioru różnych elementów ze zbioru {1, 2, …, k}. Liczba wszystkich takich możliwych wariacji z powtórzeniami to \frac{n!}{(n−k)!}.

Definicja 3. k-wyrazowa wariacja z powtórzeniami zbioru {1, 2, …, n} to przypisanie elementom z tego zbioru pewnych elementów ze zbioru {1, 2, …, k}. Liczba wszystkich takich możliwych wariacji z powtórzeniami to k^{n}.

Definicja 4. k-elementowa kombinacja zbioru {1, 2, …, n} to k-elementowy podzbiór tego zbioru. \binom{n}{k} oznacza liczbę wszystkich takich możliwych kombinacji.

\binom{n}{k} = \frac{n!}{k!(n−k)!} dla n ≥ k ≥ 0 oraz \binom{n}{k} = 0 w przeciwnym przypadku.

Definicja 5. Permutacja z powtórzeniami to bijekcja ze zbioru {1, 2, …, n} w n-elementowy multizbiór. Jeśli zbiór elementów tego multizbioru oznaczymy jako {1, 2, …, s}, a jako n_{i} oznaczymy liczbę wystąpień i w tym multizbiorze, to liczba wszystkich takich możliwych permutacji wyniesie \frac{n!}{n_{1}!n_{2}!...n_{s}!}.

Zasada szufladkowa Dirichleta. Jeśli zbiór nk + 1 różnych elementów podzielimy na n parami rozłącznych podzbiorów, to co najmniej jeden z nich będzie miał co najmniej k + 1 elementów.

Wzór dwumianowy. Dla n ∈ ℕ:

(a + b)^{n} = ∑_{k=0}^{n} \binom{n}{k}a^{k}b^{n−k}.

Zasada włączeń i wyłączeń. Dla zbiorów S_{1}, S_{2}, …, S_{n}:

|S_{1} ∪ S_{2} ∪ … ∪ S_{n}| = ∑_{k=1}^{n} ∑_{1≤i_{1}<...<i_{k}≤n}(−1)^{k}|S_{i_{1}} ∩ S_{i_{2}} ∩ … ∩ S_{i_{k}}|.