Розміщення з повтореннями

Розміщення з повтореннями схожі на звичайні розміщення, лише ми дозволяємо елементам з основної множини M повторюватися.

Означення і формула

Почнімо з класичного прикладу: скільки різних слів можна утворити з літер англійського алфавіту (abc … xyz, їх 26), якщо слово має мати довжину 6? Шість літер — небагато, але слів усе одно буде досить багато. Значення слів нас не цікавить, тому й «weqrww» вважаємо допустимим словом довжини шість.

Для обчислення потрібно знати лише комбінаторне правило добутку. Маємо всього 26 різних літер, які можна використати. На перше місце можна поставити одну з 26 літер. На друге місце теж можна поставити одну з 26 літер, бо ми не ставили умови, що літери не повинні повторюватися. Тож на кожній позиції ми вибираємо з 26 літер, і загальна кількість розміщень за правилом добутку дорівнює 26⁶ = 308,915,776. Це досить багато, хоча ми використали лише 26 літер.

Скажімо, що розміщення з повтореннями з множини M з n елементів по k — це кожен впорядкований набір з k елементів, елементи якого належать множині M, і кожен елемент у наборі може зустрічатися до k разів. Якщо маємо множину M = {1, 2, 3}, то всі ці набори є допустимими розміщеннями з повтореннями по 4: (1; 1; 1; 1), (1; 2; 3; 1), (2; 2; 3; 3). Кількість таких розміщень з повтореннями, яку позначаємо $\overline{A}_n^k$, дорівнює

$$ \overline{A}_n^k = n^k. $$

Розв'язані приклади

1. Скільки шестицифрових чисел можна скласти з цифр {2, 4, 6, 8}, якщо цифри можуть повторюватися? Просто підставимо у формулу: множина має розмір 4, і вибираємо шістки:

   $$ \overline{A}_4^6 = 4^6=4096. $$

2. У комп'ютерах зазвичай використовують двійкову систему числення, тобто систему, що використовує лише цифри 0 та 1. Там запроваджують нові одиниці, наприклад, один біт — це ніби комірка, в яку можна записати або нуль, або одиницю. Більша одиниця виміру — байт (англ. byte), який містить 8 бітів. Отже, 1 — це один біт, а 01110001 — це один байт. Скількома різними способами можна заповнити один байт 8 бітами?

   Вибираємо з множини {0, 1}, тобто з двох елементів. Вибираємо набір з k = 8 елементів, тому кількість усіх можливостей дорівнює

   $$ \overline{A}_2^8 = 2^8 = 256. $$

3. З попереднього прикладу знаємо, що один байт може розрізнити до 256 різних значень. Скількома способами можна заповнити 4 байти?

   Чотири байти містять 4 · 8 = 32 біти, і ми все ще вибираємо з множини розміру 2. Отже, результат такий:

   $$ \overline{A}_2^{32} = 2^{32} = 4{,}294,967{,}296. $$

   Бачимо, що лише чотири байти можуть розрізнити понад чотири мільярди значень. Для порівняння: сучасні комп'ютери мають диски розміром у сотні гігабайтів або й терабайти. Один терабайт містить 1,000,000,000,000 байтів, а отже, 8,000,000,000,000 бітів. На терабайтний диск ми тому можемо записати до 2^{8,000,000,000,000} різних значень.

   Зауваження: нині є невелика плутанина з поняттям кілобайт (мегабайт тощо). З технологічних причин один кілобайт не містив 1000 байтів, як заведено в інших одиницях (один кілограм дорівнює тисячі грамів), а дорівнював 2¹⁰ байтів, тобто 1024 байтам. Один мегабайт тоді дорівнював 2²⁰ байтів, або 2¹⁰ кілобайтів.

   Тому нині розрізняють два види записів: 1 кБ (читаємо кілобайт) — це 1000 байтів, а 1 КіБ (читаємо кібібайт) — це 2¹⁰ = 1024 байти.

4. Ще один приклад є в окремій статті про безпеку пароля.