Wariacje
Wariacje bez powtórzeń
Definicja
WERSJA 1: Wariacją bez powtórzeń k-wyrazową zbioru n-elementowego A 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ą.
WERSJA 2: Niech zbiór A składa się z n różnych elementów. Każdy k wyrazowy
(k≤n) i różnowartościowy ciąg elementów z A nazywamy
wariacją bez powtórzeń zbioru A.
Liczba wszystkich k-wyrazowych wariacji bez powtórzeń zbioru n-elementowego wyraża się wzorem:
Spostrzeżenie
Vnk=Cnk·Pk oraz Vnn-1=Vnn=Pn, gdzie
Cnk to liczba k-elementowych kombinacji ze zbioru n-elementowego a Pn to ilość permutacji zbioru n-elementowego).
Przykłady
- Z cyfr 1, 2, 3, 4, 5 można utworzyć liczb trzycyfrowych o różnych cyfrach.
- W zawodach sportowych startuje 10 zawodników.
Zakładając, że szanse na medale wszystkich zawodników są
równe na ile sposobów można wyłoniż pierwszż trójkę w
zawodach?
Definicja
Wariacją z powtórzeniami k-wyrazową zbioru n-elementowego A nazywa się każdy k-wyrazowy ciąg elementów tego zbioru (dowolny element może wystąpić wielokrotnie w ciągu).
Liczba wszystkich k-wyrazowych wariacji z powtórzeniami zbioru n-elementowego jest równa:
Różnice
Różnica względem wariacji bez powtórzeń polega na tym, że uwzględniamy wszystkie k-elementowe ciągi (również te z powtarzającymi się elementami).
Wyjaśnienie
W liczbie dwucyfrowej mamy dwa „pola”, które wypełniamy cyframi. Na każdym z nich może znaleźć się dowolna z dostępnych cyfr (nie ma żadnych wymagań odnośnie występowania dowolnej cyfry – każda może się pojawić wielokrotnie lub wcale). Wobec tego, na pierwszym polu możemy umieścić którąkolwiek z dostępnych pięciu cyfr . Podobnie postępujemy na kolejnym wolnym polu.
Ostatecznie otrzymujemy:
.
Przykłady
- Za pomocą cyfr 1, 2, 3, 4, 5 można zapisać 52 = 25 liczb dwucyfrowych (niekoniecznie różnocyfrowych).
- Ile istnieje możliwosci dla 10 znakowego hasła
logowania na serwer (dopuszczalne jest 26 znaków alfabetu
łacińskiego oraz 10 cyfr)?
Liczba możliwosci dla silnego hasła to
.
Gdyby haker logował się 1000 razy na sekunde to sprawdzenie wszystkich haseł zajełoby 115936 lat!