Wariacje z powtórzeniami

Wariacje z powtórzeniami są podobne do zwykłych wariacji, tylko pozwalamy, żeby elementy zbioru M, z którego wybieramy, mogły się powtarzać.

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, a mimo to słów będzie całkiem sporo. Nie interesuje nas znaczenie słów, więc nawet „weqrww” uznajemy za poprawne słowo o długości sześć.

Do obliczenia wystarczy znać regułę mnożenia. Mamy łącznie 26 różnych liter, których możemy użyć. Na pierwszym miejscu możemy więc postawić jedną z 26 liter. Na drugim miejscu również możemy postawić jedną z 26 liter, bo nie postawiliśmy warunku, że litery nie mogą się powtarzać. W ten sposób dochodzimy do tego, że na każdej pozycji wybieramy spośród 26 liter, a łączna liczba wariacji wynosi, zgodnie z regułą mnożenia, 26⁶ = 308 915 776. To całkiem dużo, biorąc pod uwagę, że użyliśmy tylko 26 liter.

Powiemy, że k-wyrazowa wariacja z powtórzeniami zbioru M, który ma n elementów, to każdy ciąg k-wyrazowy, którego wyrazy należą do zbioru M, przy czym każdy element może w nim wystąpić nawet k razy. Jeśli więc mamy zbiór M = {1, 2, 3}, to wszystkie te ciągi są poprawnymi 4-wyrazowymi wariacjami z powtórzeniami: (1, 1, 1, 1), (1, 2, 3, 1), (2, 2, 3, 3). Liczba takich wariacji z powtórzeniami, oznaczana W_n^k, jest równa

$$ W_n^k = n^k. $$

Rozwiązane przykłady

1. Ile liczb sześciocyfrowych można ułożyć z cyfr {2, 4, 6, 8}, jeśli cyfry mogą się powtarzać? Po prostu podstawiamy do wzoru: zbiór ma 4 elementy, a wybieramy szóstki:

   $$ W_4^6 = 4^6=4096. $$

2. W komputerach powszechnie używa się dwójkowego systemu liczbowego, czyli systemu, który używa tylko cyfr 0 i 1. Wprowadza się tam nowe jednostki, np. jeden bit to coś w rodzaju komórki, w której można zapisać albo zero, albo jedynkę. Większy jest bajt (po angielsku byte), który zawiera 8 bitów. Tak więc 1 to jeden bit, a 01110001 to jeden bajt. Na ile sposobów można wypełnić jeden bajt 8 bitami?

   Wybieramy ze zbioru {0, 1}, czyli spośród dwóch elementów. Tworzymy ciąg o długości k = 8, więc liczba wszystkich możliwości jest równa

   $$ W_2^8 = 2^8 = 256. $$

3. Z poprzedniego przykładu wiemy, że jeden bajt może rozróżnić aż 256 różnych wartości. Na ile sposobów można wypełnić 4 bajty?

   Cztery bajty zawierają 4 · 8 = 32 bity, nadal wybieramy ze zbioru dwuelementowego. Wynik jest więc taki:

   $$ W_2^{32} = 2^{32} = 4{,}294,967{,}296. $$

   Widzimy, że zaledwie cztery bajty potrafią rozróżnić ponad cztery miliardy wartości. Dla porównania: 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 więc 8 000 000 000 000 bitów. Na dysku o pojemności jednego terabajta możemy więc zapisać aż 2^{8 000 000 000 000} różnych wartości.

   Uwaga: obecnie panuje pewne zamieszanie wokół pojęcia kilobajt (megabajt itd.). Z przyczyn technicznych przyjmowano, że jeden kilobajt nie zawiera 1000 bajtów, jak to bywa w innych jednostkach (jeden kilogram to tysiąc gramów), lecz 2¹⁰ bajtów, czyli 1024 bajty. Jeden megabajt to wtedy 2²⁰ bajtów, czyli 2¹⁰ kilobajtów.

   Obecnie rozróżniamy więc dwa rodzaje zapisu: 1 kB (czytamy kilobajt) to 1000 bajtów, a 1 KiB (czytamy kibibajt) to 2¹⁰ = 1024 bajty.

4. Kolejny przykład znajdziesz w osobnym artykule poświęconym bezpieczeństwu haseł.