Розміщення

За правилами ФІФА у фінальній частині чемпіонату світу з футболу беруть участь 32 команди. З’ясуємо, скількома способами можуть бути розподілені золоті, срібні та бронзові медалі (три призових місця) між командами.

Перше місце може посісти будь-яка з 32 команд, друге місце — будь-яка з решти 31 команди, третє — будь-яка з 30 команд, що залишилися. За узагальненим правилом добутку кількість можливих варіантів розподілу призових місць дорівнює $32 \cdot 31 \cdot 30 = 29\,760$ .

Кожну з таких упорядкованих підмножин називають розміщенням з 32 елементів по 3 елементи.

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

📐Означення — Розміщення

Будь-яку $k$ -елементну впорядковану підмножину даної $n$ -елементної множини називають розміщенням з $n$ елементів по $k$ елементів.

Кількість усіх можливих розміщень з $n$ елементів по $k$ елементів позначають символом $A_n^k$ , використовуючи першу літеру французького слова arrangement — розміщення.

⚡Теорема — Формула кількості розміщень

Для будь-яких натуральних $n$ і $k$ таких, що $k \leqslant n$ , справедливою є формула

A_n^k = n(n-1)(n-2) \cdot \ldots \cdot (n-k+1)

Доведення. Розглянемо $n$ -елементну множину та сформуємо її $k$ -елементну впорядковану підмножину. Існує $n$ способів вибору першого елемента. Після того як вибрано перший елемент, другий можна вибрати вже тільки $n - 1$ способами. Після вибору першого та другого елементів залишається $n - 2$ способи для вибору третього елемента. Продовжуючи ці міркування, отримуємо, що вибір $k$ -го елемента можна здійснити $n - k + 1$ способами.

Таким чином, за узагальненим правилом добутку:

A_n^k = n(n-1)(n-2) \cdot \ldots \cdot (n-k+1).

Зв’язок із факторіалом та перестановками

Оскільки існує лише одна $n$ -елементна підмножина даної $n$ -елементної множини, то число $A_n^n$ — це кількість перестановок $n$ -елементної множини, тобто

A_n^n = P_n.

Помножимо й поділимо вираз у правій частині формули на $(n - k)!$ (це можна зробити, оскільки $(n - k)! \neq 0$ ). Отримуємо формулу:

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

✎Приклад — Правильні дроби з простими чисельниками і знаменниками

Умова. Скільки існує правильних дробів, чисельник і знаменник яких — прості числа, які менші від 30?

Розв’язання. Множина $\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29\}$ складається з усіх простих чисел, які менші від 30. Кількість 2-елементних упорядкованих підмножин цієї множини дорівнює кількості звичайних дробів, відмінних від одиниці, чисельник і знаменник яких — зазначені прості числа. Половина із цих дробів є правильними.

Отже, шукане число дорівнює $\dfrac{1}{2} A_{10}^2 = \dfrac{1}{2} \cdot 10 \cdot 9 = 45$ .

Відповідь: 45.

✏Вправа — Задачі на розміщення

У футбольній команді (11 чоловік) потрібно обрати капітана та його заступника. Скількома способами це можна зробити?
Комісія, що складається з 15 осіб, має обрати голову, його заступника та секретаря. Скількома способами це можна зробити?
У 9 класі вивчають 18 предметів. Денний розклад містить 6 уроків. Скількома способами можна скласти денний розклад так, щоб усі 6 уроків були різними?