Wariacja bez powtórzeń

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
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 ≤ kn) 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[edytuj | edytuj kod]

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

Spostrzeżenie[edytuj | edytuj kod]

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).