Wariacja bez powtórzeń

Niniejszy artykuł jest częścią cyklu kombinatoryka.

permutacja kombinacja bez powtórzeń kombinacja z powtórzeniami wariacja bez powtórzeń wariacja z powtórzeniami liczby Bella liczby Catalana liczby Stirlinga liczby Eulera zasada szufladkowa Dirichleta zasada włączeń i wyłączeń

Wariacją bez powtórzeń k-wyrazową zbioru n-elementowego A (1 ≤ k ≤ n) nazywa się każdy k-wyrazowy ciąg k różnych elementów tego zbioru (kolejność tych elementów ma znaczenie). Gdy k=n, wariację bez powtórzeń nazywa się permutacją.

Liczba wszystkich k-wyrazowych wariacji bez powtórzeń zbioru n-elementowego wyraża się wzorem:

$V_n^k = {n! \over (n-k)!} = n \cdot (n-1) \cdot ... \cdot (n-k+1)$

Każda k-wyrazowa wariacja bez powtórzeń zbioru n-elementowego jest funkcją różnowartościową, ze zbioru k-elementowego do zbioru n-elementowgo. Na kalkulatorach liczbę wszystkich wariacji bez powtórzeń ze zbioru r-elementowego do zbioru n-elementowego wyraża się znakiem nPr.

Przykład

Z cyfr 1, 2, 3, 4, 5 można utworzyć $\begin{matrix}\frac{5!}{(5-3)!}\end{matrix}=60$ liczb trzycyfrowych o różnych cyfrach.

Spostrzeżenie

$V_n^k = C_n^k \cdot P_k$ oraz $V_n^{n-1} = V_n^n = P_n$

(gdzie $C^k_n$ to liczba k-elementowych kombinacji ze zbioru n-elementowego a $P_n$ to ilość permutacji zbioru n-elementowego).