Definicja 1

Kombinacja

Kombinacją k-elementową bez powtórzeń n-elementowego zbioru A nazywamy dowolny k-elementowy (k\le n) podzbiór zbioru A utworzony z różnych elementów zbioru A.

Twierdzenie 1

Liczba kombinacji

Liczba k-elementowych kombinacji zbioru n-elementowego (k\le n) wyraża się wzorem:

(0)C_n^k=\binom{n}{k}=\frac{n!}{k!(n-k)!}

gdzie k,n\in\mathbb{N}.

Definicja 2

Symbol Newtona

Symbolem Newtona nazywamy funkcję dwóch argumentów n,k\in\mathbb{N} daną wzorem:

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

Symbol \binom{n}{k} czytamy: “n po k” lub “k z n”.

Twierdzenie 2

Własności symbolu Newtona

Zachodzą następującego własności:

Dla dowolnego n\in\mathbb{N}:
(0)\binom{n}{0}=1,\quad\binom{n}{n}=1
Dla dowolnych n,k\in\mathbb{N}, k\le n:
(0)\binom{n}{k}=\binom{n}{n-k}
Dla dowolnych n,k\in\mathbb{N}, k\le n-1:
(0)\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}

Przykład 1

Przykład

2-elementowe kombinacje zbioru 3-elementowego \left\{a,b,c\right\}:
(0)\left\{a,b\right\}\\ \left\{a,c\right\}\\ \left\{b,c\right\}

(0)C_3^2=\binom{3}{2}= \frac{3!}{2!\left(3-2\right)!}= 3
3-elementowe kombinacje zbioru 4-elementowego: \left\{a,b,c,d\right\}
(0)\left\{a,b,c\right\}\\ \left\{a,b,d\right\}\\ \left\{a,c,d\right\}\\ \left\{b,c,d\right\}(0)C_4^3=\binom{4}{3}= 4

Twierdzenie o liczbie kombinacji