✖

Wariacje z powtórzeniami

Kapitoly: Kombinatoryka, Wariacje, Permutacja, Kombinacja, Wariacje z powtórzeniami, Kombinacje z powtórzeniami, Ile jest różnych kodów PIN?, Kalkulator.

Wariacje z powtórzeniami są podobne do klasycznych wariacji, tylko pozwalamy na powtarzanie elementów ze zbioru podpierającego M.

Definicja i wzór

Zacznijmy od klasycznego przykładu: ile różnych słów możemy utworzyć z liter alfabetu angielskiego (abc ... xyz, jest ich 26), jeśli słowo ma mieć długość 6? Sześć liter to niewiele, ale słów będzie całkiem sporo. Nie dbamy o znaczenie słów, więc nawet "weqrww" uznamy za poprawne słowo o długości sześciu.

Do wykonania obliczeń wystarczy nam znajomość reguły iloczynu kombinatorycznego. Mamy w sumie 26 różnych liter, których możemy użyć. Możemy więc umieścić jedną z liter 26 na pierwszym miejscu. Ale możemy również umieścić jedną z 26 liter na drugim miejscu, ponieważ nie ustaliliśmy warunku, że litery nie mogą się powtarzać. To prowadzi nas do faktu, że na każdej pozycji wybieramy spośród 26 liter, a całkowita liczba wariantów wynosi, zgodnie z regułą iloczynu, 266 = 308 915 776. To całkiem sporo jak na fakt, że użyliśmy tylko 26 liter.

Mówimy, że wariacja k-elementowa z powtórzeniami ze zbioru M o rozmiarze n jest dowolną uporządkowaną k-kostką, której elementy pochodzą ze zbioru M i każdy element może wystąpić do k-razy w k-kostce. Jeśli więc mamy zbiór M = {1, 2, 3}, to są to wszystkie poprawne 4-członowe wariacje z powtórzeniami: [1, 1, 1, 1], [1, 2, 3, 1], [2, 2, 3, 3]. Liczba takich wariacji z powtórzeniami, oznaczana V'(k, n), jest więc równa

$$ V'(k, n) = n^k. $$

Rozwiązane przykłady

  1. Ile liczb sześciocyfrowych można zbudować z cyfr {2, 4, 6, 8}, jeśli cyfry mogą się powtarzać? Wystarczy podstawić do wzoru zbiór o rozmiarze 4 i wybrać szóstki:

    $$ V'(6, 4) = 4^6=4096. $$

  2. W komputerach powszechnie stosuje się binarny system liczbowy, tj. system wykorzystujący tylko cyfry 0 i 1. Wprowadzono nowe jednostki, np. jeden bit reprezentuje rodzaj komórki, w której przechowuje się zero lub jedynkę. Większy jest bajt, który zawiera 8 bitów. Tak więc 1 to jeden bit, a 01110001 to jeden bajt. Na ile różnych sposobów można wypełnić jeden bajt 8 bitami?

    Wybieramy ze zbioru {0, 1}, czyli dwa elementy. Wybieramy k- jest to rozmiar k = 8, więc liczba wszystkich możliwości jest równa

    $$ V'(8, 2) = 2^8 = 256. $$

  3. Z poprzedniego przykładu wiemy, że na jednym bajcie można zapisać do 256 różnych wartości. Na ile sposobów można zapełnić 4 bajty?

    Cztery bajty zawierają 4 · 8 = 32 bitów, wciąż wybierając ze zbioru o rozmiarze 2. Wynik jest więc następujący:

    $$ V'(32, 2) = 2^{32} = 4{,}294,967{,}296. $$

    Widzimy, że zaledwie cztery bajty mogą rozróżnić ponad cztery miliardy wartości. Aby dać ci wyobrażenie: dzisiejsze komputery mają dyski o pojemności setek gigabajtów, a nawet terabajtów. Jeden terabajt zawiera 1 000 000 000 000 bajtów, a zatem 8 000 000 000 000 bitów. Na dysku o pojemności terabajta możemy więc przechowywać do 28 000 000 000 000 różnych wartości.

    Uwaga: obecnie istnieje pewne zamieszanie wokół terminu kilobajt (megabajt itp.). Ze względów technologicznych jeden kilobajt nie zawierał 1000 bajtów, jak to zwykle bywa w innych jednostkach (jeden kilogram jest równy tysiącowi gramów), ale jeden kilobajt był równy 210 bajtów, czyli 1024 bajtów. Jeden megabajt był wtedy równy 220 bajtów lub 210 kilobajtów.

    Dlatego dziś rozróżniamy dwa rodzaje notacji: 1 kB (czytaj kilobajt) to 1000 bajtów, a 1 KiB (czytaj kibajt) to 210 = 1024 bajtów.

  4. Inny przykład można znaleźć w osobnym artykule dotyczącym bezpieczeństwa haseł.

Zasoby i dalsza lektura