Розміщення

Розміщення використовуємо тоді, коли з певної множини об'єктів вибираємо певну кількість об'єктів і при цьому важливо, в якому порядку ми їх вибираємо.

Виведення формули

Почнімо з типової задачі на розміщення: у селі щороку проводять змагання з поїдання вареників із вишнями. До фінального туру вийшло сім замащених маслом учасників. Підрахуй, скількома способами ці сім учасників можуть посісти перші три місця.

Важливо усвідомити, що в цій задачі порядок має значення. Наприклад, якщо ми знаємо, що на перших трьох місцях опиняться Тарас, Матвій і Остап, то ця трійка дає нам шість різних розподілів місць:

• Тарас, Матвій, Остап;
• Тарас, Остап, Матвій;
• Матвій, Тарас, Остап;
• Матвій, Остап, Тарас;
• Остап, Тарас, Матвій;
• Остап, Матвій, Тарас.

Усе це різні розподіли місць, і ми хочемо підрахувати, скільки всього різних розподілів можна скласти, якщо учасників 7.

Для цього використаємо комбінаторне правило добутку. Скажімо, що вибираємо трійки вигляду (x₁; x₂; x₃), де x₁ — учасник, який посів перше місце, і так далі. Яких учасників можна підставити замість x₁? Усіх, тобто замість x₁ можна підставити 7 учасників. Яких можна підставити замість x₂? Усіх, крім того, якого ми вже поставили на перше місце, тож замість x₂ можна підставити 7 − 1 = 6 учасників. Замість x₃ можна підставити тих учасників, які не на першому і не на другому місці, отже, маємо 7 − 2 = 5 можливостей. Застосуємо комбінаторне правило добутку й отримаємо загальну кількість можливостей: 7 · 6 · 5 = 210.

Можемо помітити: якщо ми захочемо знати кількість усіх можливостей для перших 4 місць, то замість x₄ можна підставити 7 − 3 = 4 учасників, тож загальна кількість можливостей дорівнюватиме 7 · 6 · 5 · 4 = 840. Що з цього випливає?

Якщо маємо множину з n елементів (у нашому прикладі це 7 поїдачів) і вибираємо 3 елементи, причому порядок важливий, то результат дорівнює n · (n − 1) · (n − 2). На перше місце можуть претендувати всі, на наступне — на одного менше, і так далі. Звідси можна вивести загальну формулу для вибору k елементів із множини з n елементів: кількість можливостей дорівнюватиме n · (n − 1) · (n − 2) · … · (n − k + 1).

Цю формулу ще спростимо за допомогою факторіала. Якщо подивитися на факторіал числа сім: 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1, і на те, як ми рахували кількість усіх призових розподілів 7 · 6 · 5, то побачимо певну схожість. Потрібно лише позбутися кінця, тобто потрібно 7! поділити на 4 · 3 · 2 · 1, і залишиться лише 7 · 6 · 5. А чому дорівнює вираз 4 · 3 · 2 · 1? Він дорівнює 4!.

Тож можемо записати: якщо маємо множину з n елементів і вибираємо k елементів, причому порядок важливий, то всього є

$$ A_n^k = \frac{n!}{(n-k)!} $$

можливостей. Якщо підставити в цю формулу числа зі змагання з вареників:

$$ A_7^3 = \frac{7!}{(7-3)!}=\frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{4 \cdot 3 \cdot 2 \cdot 1} = 7 \cdot 6 \cdot 5 = 210. $$

Калькулятор

Наведений нижче калькулятор обчислить кількість розміщень для заданих n і k.

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

1. Залишимося на змаганні з поїдання вареників. Як змінилася б кількість можливих призових розподілів, якби ми знали, що на змагання приїхав Данило Шніцель, справжній майстер, який завжди перемагає? Тобто скільки існує різних призових розподілів, якщо учасників 7 і Данило неодмінно посяде перше місце?

Це знову просте розміщення: перше місце вже визначене, а із 6 учасників, що залишилися, нам треба визначити, як вони можуть зайняти друге й третє місця. Вибираємо 2 елементи із 6-елементної множини, що веде до розміщення

$$ A_6^2 = \frac{6!}{(6-2)!}=30 $$

2. Колись давно, коли Данило ще не був таким майстром, він регулярно потрапляв у першу трійку. Скільки існує різних призових розподілів, якщо учасників 7 і Данило неодмінно отримає якусь медаль?

   Цей приклад відрізняється від попереднього тим, що ми не знаємо, на якому місці опинився Данило; він міг посісти друге або навіть третє, чого досі соромиться. Тому нам потрібно підрахувати разом три різні розміщення: коли Данило переміг, потім коли Данило здобув срібну медаль і, нарешті, бронзову. Проте щоразу залишаються лише два місця, де може опинитися хтось інший. Наприклад, якщо Данило був другим, то решта учасників могла посісти або перше, або третє місце. Отже, рахуємо знову розміщення двох із шести, тільки підрахувати його треба тричі, для трьох різних місць Данила. Кількість усіх розподілів тому дорівнює:

   $$ 3 \cdot A_6^2 = 3 \cdot \frac{6!}{(6-2)!} = 3 \cdot 30 = 90 $$

   Зверни увагу: трійку перед розміщенням можна записати як A₃¹, бо насправді ми вибираємо один елемент (одне конкретне місце) з триелементної множини (три призові позиції).

3. У школі разом 20 вчителів. Незабаром випускні іспити, і треба скласти комісію такого складу: один голова, один добрий асистент і один суворий асистент. Скільки існує всього можливостей?

   Спершу відповімо на питання, чи важливий порядок: так, важливий, трьох учителів можна переставити шістьма різними способами. Тепер усе просто: вибираємо розміщення з 20 елементів по 3:

   $$ A_{20}^3 = \frac{20!}{17!}=6840. $$

4. Скільки трицифрових чисел можна скласти з цифр {0, 1, 2, 3, 4, 5}, якщо жодна цифра не повинна повторюватися?

   Чи важливий порядок? Так, 123 — інше число, ніж 321. Скільки існує різних трійок? Це просте розміщення з 6 по 3:

   $$ A_6^3 = \frac{6!}{3!}=120. $$

   Але ще треба відняти ті розміщення, які мають на першому місці нуль, бо 012 не є трицифровим числом. Тож питання тепер таке: скільки існує різних трійок, що починаються з нуля? У такому разі змінюються цифри лише на двох місцях, що залишилися (трійки мають вигляд (0; x₂; x₃)), тому шукаємо, скільки різних пар можна утворити з чисел {1, 2, 3, 4, 5}. Це знову просто: A₅² = 5!/3! = 20. Отже, існує 20 трійок, що починаються з нуля.

   Загальна кількість трицифрових чисел, складених із цифр {0, 1, 2, 3, 4, 5}, дорівнює 120 − 20 = 100.

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

   Порядок важливий, адже 123 — інше число, ніж 321. Ми складаємо трицифрове число, яке має бути непарним, а це означає, що на перших двох позиціях може стояти будь-яка цифра, а на останній — одна з цифр {1, 3, 5}. Спершу підрахуємо кількість усіх трійок, які можна скласти з п'яти цифр: A₅³ = 5! / 2! = 60.

   Кожна цифра стоятиме на останньому місці однаково часто, тож якщо маємо 5 цифр, то кожна цифра стоятиме на останньому місці 60 / 5 = 12 разів. Маємо три цифри {1, 3, 5}, які можуть стояти на останньому місці, тому існує 12 різних чисел, що закінчуються на 1, 12 чисел, що закінчуються на 3, і 12 чисел, що закінчуються на 5. Застосуємо комбінаторне правило суми й отримаємо разом 12 + 12 + 12 = 36 можливостей.

6. Знайди x, якщо відомо, що A_x² = 72. Інакше кажучи: із множини розміру x вибираємо пари і знаємо, що можемо вибрати разом 72 різні пари. Який розмір мала множина, з якої ми вибирали пари? Розпишемо:

   $$ A_x^2 = \frac{x!}{(x-2)!} = 72 $$

   Далі спростимо:

   $$\begin{eqnarray} \frac{x!}{(x-2)!} &=& 72\\ \frac{x \cdot (x-1)\cdot(x-2)!}{(x-2)!} &=& 72 \\ x \cdot (x-1) &=&72\\ x^2-x&=&72\\ x^2-x-72&=&0 \end{eqnarray}$$

   Це вже звичайне квадратне рівняння, тож розв'яжемо його за допомогою дискримінанта або можемо переписати рівняння у вигляді

   $$ (x+8)\cdot(x-9)=0 $$

   з якого вже можна прочитати розв'язок: x₁ = −8 і x₂ = 9. Від'ємний розв'язок нас не цікавить, адже кількість елементів множини не може бути від'ємною, тому розв'язком початкового рівняння є x = 9, множина мала дев'ять елементів.