Перестановки

У комбінаториці часто трапляються задачі, у яких потрібно впорядкувати всі елементи деякої множини. Скількома способами можна поставити 6 книжок на полицю? Скількома способами можуть стати в чергу 5 людей? Відповідь дає поняття факторіала й формула перестановки.

Що таке факторіал?

Факторіал натурального числа n — це добуток усіх натуральних чисел від 1 до n включно. Його позначають n! і читають «ен факторіал».

$$n!=1\cdot 2\cdot 3\cdot \dots \cdot n$$

Ось значення факторіалів, які варто запам'ятати для НМТ:

Зверни увагу: $0!=1$. Це не інтуїтивне, але необхідне означення — воно забезпечує узгодженість комбінаторних формул. Такою самою є домовленість для багатьох розділів математики.

Рекурентна властивість: n! = n · (n − 1)!. Наприклад, 6! = 6 · 5! = 6 · 120 = 720.

Перестановка: означення

Перестановкою з n різних елементів називають упорядкований набір, у який входить кожен із цих елементів рівно один раз. Інакше кажучи, перестановка — це будь-який спосіб розташувати всі n елементів у певному порядку. Порядок має значення: (A, B, C) і (B, A, C) — це різні перестановки.

Кількість усіх можливих перестановок n різних елементів позначають Pₙ і обчислюють за формулою:

$$P_n=n!$$

Ця формула є в довідкових матеріалах НМТ. Чому вона правильна? На перше місце можна поставити будь-який із n елементів. Після цього на друге місце залишається n − 1 кандидат, на третє — n − 2, і так далі, поки на останнє місце не залишиться єдиний елемент. За правилом добутку загальна кількість варіантів дорівнює n · (n − 1) · (n − 2) · … · 1 = n!.

Найпростіші задачі на перестановки

Розгляньмо кілька прикладів.

• 6 книжок на полиці: P₆ = 6! = 720 способів.

• Черга з 5 осіб: 5! = 120 способів.

• Скільки «слів» (довільних послідовностей літер) можна скласти з усіх літер слова КНИГА? У слові 5 різних літер — отже, 5! = 120 слів.

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

Спрощення виразів із факторіалами

Факторіали ростуть дуже швидко, але вирази з ними часто можна спростити, не обчислюючи кожен окремо.

• $$\frac{10!}{8!}=\frac{1\cdot 2\cdot \dots \cdot 10}{1\cdot 2\cdot \dots \cdot 8}=9\cdot 10=90$$

• $$\frac{7!}{5!}=6\cdot 7=42$$

• $$\frac{(n+1)!}{(n-1)!}=n(n+1)$$

• $$5!+4!=4!\cdot (5+1)=24\cdot 6=144$$

• $$\frac{10!}{5!}=6\cdot 7\cdot 8\cdot 9\cdot 10=30240\ne 2!$$

• $$2!+3!=2+6=8\ne 5!$$

Не плутай: 10! / 5! = 30 240, а не 2!. Скорочувати факторіали як звичайні числа — груба помилка. 2! + 3! = 8, а не 5!, тому що факторіали не додаються безпосередньо.

У багатьох задачах на впорядкування накладають додаткові умови: певний елемент має стояти на конкретному місці, або деякі елементи не можуть опинитися на початку. Такі задачі зводяться до перестановки решти елементів.

Один елемент на фіксованому місці

Якщо один з n елементів уже стоїть на визначеній позиції, то інші n − 1 елементів можна переставляти довільно. Отже, кількість способів дорівнює P_{n-1} = (n-1)!.

Приклад: 6 учасників шикуються в ряд, капітан команди стоїть першим. Капітан фіксований — решту 5 учасників переставляємо: P₅ = 120 способів.

Складніший приклад: у розкладі з 5 різних уроків математика завжди перша, а фізика — остання. Тоді на першому й останньому місцях усе визначено, і ми переставляємо лише 3 середні уроки: 3! = 6 варіантів.

Два елементи на кінцях ряду

Якщо два певні елементи мають стояти на краях ряду (першому й останньому місцях), але їхній порядок на цих краях не зафіксовано, то спочатку вибираємо, хто з двох буде першим, а хто останнім — це 2! способів. Потім переставляємо решту n − 2 елементів на внутрішніх місцях: (n − 2)! способів. За правилом добутку маємо 2! · (n − 2)! варіантів.

Наприклад, для 6 осіб, де Андрій і Олена стоять на кінцях у будь-якому порядку: 2! · 4! = 2 · 24 = 48 розстановок.

Числа з усіх заданих цифр

Особливий клас задач — складання чисел, використовуючи кожну з кількох різних цифр рівно один раз. Це фактично перестановка цифр, але з обмеженням: першою цифрою не може бути нуль.

Якщо нуля серед цифр немає — просто переставляємо всі цифри. Наприклад, з цифр 1, 3, 5, 7 можна скласти 4! = 24 чотирицифрові числа.

Якщо серед цифр є нуль, то з усіх n! перестановок потрібно відняти ті, у яких нуль стоїть першим. Поставивши нуль на перше місце, решту n − 1 цифр переставляємо довільно — це (n − 1)! варіантів. Отже, кількість чисел дорівнює n! − (n − 1)!.

Приклад: з цифр 0, 2, 4, 6 складаємо чотирицифрові числа. 4! − 3! = 24 − 6 = 18 чисел. Той самий результат дає міркування: на перше місце можна поставити будь-яку з трьох ненульових цифр, а решту 3 цифри переставити довільно: 3 · 3! = 18.

Умова на останню цифру

Якщо в задачі вимагається, щоб число було, наприклад, парним, то спочатку вибираємо останню цифру з доступних парних, а потім переставляємо решту цифр.

Приклад: скільки п'ятицифрових чисел можна скласти з цифр 1, 2, 3, 4, 5 (кожну використовуючи рівно один раз) так, щоб число було парним? Остання цифра має бути 2 або 4 — це 2 варіанти. Решту 4 цифри переставляємо довільно: 4! = 24. Разом: 2 · 4! = 48 чисел.

Задачі, у яких два (або більше) елементи мають обов'язково стояти разом або, навпаки, ніколи не стояти поруч, розв'язують методом склеювання.

Два елементи поруч

Коли два певні елементи A і B мають стояти поруч, уяви, що їх «склеюють» в один блок. Тоді замість n об'єктів ми маємо n − 1 об'єкт (блок AB та решта n − 2 елементів). Ці n − 1 об'єктів можна переставити (n − 1)! способами.

Однак усередині блоку A і B теж можна переставити — у порядку AB або BA. Це дає ще 2! способи. За правилом добутку:

$$\text{Кількість розстановок «поруч»}=2!\cdot (n-1)!=2\cdot (n-1)!$$

Приклад: 6 різних книжок ставлять на полицю, причому дві з них мають стояти поруч. 2 · 5! = 2 · 120 = 240 способів.

Типова помилка: забути, що склеєні елементи теж можна переставляти між собою. Не пиши 5! = 120 замість 2 · 5! = 240. Множник 2! обов'язковий!

Блок із трьох і більше елементів

Якщо поруч мають стояти три певні елементи, склеюємо їх в один блок. Тоді загальна кількість об'єктів стає n − 2, а всередині блоку ці три елементи можна переставити 3! способами.

Приклад: з 7 книжок три певні книжки стоять поруч. 3! · 5! = 6 · 120 = 720 способів.

Кілька блоків

Коли є кілька груп, що мають стояти поруч, кожну групу склеюємо в окремий блок. Переставляємо блоки, а всередині кожного блоку — його елементи.

Приклад: 3 хлопці й 2 дівчини стають у ряд так, що всі хлопці стоять поруч і обидві дівчини стоять поруч. Склеюємо хлопців в один блок, дівчат — в інший. Маємо 2 блоки, їх можна переставити 2! способами. Усередині блоку хлопців — 3! перестановок, усередині блоку дівчат — 2! перестановок. Разом: 2! · 3! · 2! = 2 · 6 · 2 = 24 способи.

Елементи не поруч

Задачі на те, що два певні елементи не стоять поруч, найпростіше розв'язувати через доповнення: від загальної кількості перестановок віднімаємо кількість розстановок, у яких ці елементи стоять поруч.

$$\text{«не поруч»}=n!-2\cdot (n-1)!$$

Приклад: 6 книжок ставлять на полицю так, щоб дві збірки віршів не стояли поруч.

Загальна кількість перестановок: 6! = 720. Кількість розстановок, де збірки поруч: 2 · 5! = 240. Тоді «не поруч»: 720 − 240 = 480 способів.

Не намагайся рахувати «не поруч» напряму — це набагато складніше. Завжди використовуй формулу: усі мінус ті, що поруч.

Розв'яжемо п'ять типових задач на перестановки. Кожна супроводжується покроковим поясненням.

Приклад 1. Скількома способами 7 учасників можуть стати в чергу до каси?

Це завдання з вибором однієї відповіді з п'яти (А–Д).

Умова: учасники — 7 різних людей, усі мають стати в чергу. Ми впорядковуємо всі 7 елементів, тому це перестановка. P₇ = 7! = 5 040.

Кроки: 7! = 1 · 2 · 3 · 4 · 5 · 6 · 7. Зручно порахувати: 7! = 7 · 6! = 7 · 720 = 5 040.

Відповідь: 5 040.

Розбір дистракторів: 49 (7 · 7 — плутанина з добутком, а не факторіалом), 28 (сума 1 + 2 + … + 7), 720 (6! — взяли n − 1 замість n), 823 543 (7⁷ — переставили місцями факторіал і степінь).

Приклад 2. Скільки існує п'ятицифрових чисел, у записі яких кожна з цифр 0, 1, 3, 5, 7 використана рівно один раз?

Це завдання з короткою відповіддю (ціле число).

У нас є 5 різних цифр, але серед них — нуль. Першою цифрою числа нуль бути не може, тому кількість чисел = загальна кількість перестановок п'яти цифр мінус ті, де нуль стоїть першим.

Загалом перестановок: 5! = 120. Якщо нуль стоїть першим, то решту 4 цифри переставляємо: 4! = 24.

Отже, 5! − 4! = 120 − 24 = 96 чисел.

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

Пастка: 120 (не врахували обмеження на нуль).

Приклад 3. Скількома способами можна посадити 5 друзів на 5 крісел у ряд так, щоб Оля й Марко сиділи поруч?

Це завдання з вибором однієї відповіді з п'яти.

Склеюємо Олю й Марка в один блок. Разом з трьома іншими друзями маємо 4 об'єкти. Їх можна переставити 4! = 24 способами.

Усередині блоку Оля й Марко можуть сидіти в порядку (Оля, Марко) або (Марко, Оля) — це 2! = 2 способи.

За правилом добутку: 2 · 4! = 2 · 24 = 48 способів.

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

Розбір дистракторів: 24 (забули помножити на 2! — не врахували перестановку всередині блоку), 120 (5! без жодної умови), 72 (це кількість розстановок «не поруч»: 5! − 2 · 4! = 120 − 48 = 72).

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

Це завдання з короткою відповіддю (ціле число).

Рахуємо через доповнення: «не поруч» = усі − «поруч».

Усі перестановки 6 книжок: 6! = 720.

Кількість розстановок, де дві збірки поруч: 2 · 5! = 2 · 120 = 240.

Отже, «не поруч»: 720 − 240 = 480.

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

Пастки: 240 (дали відповідь на «поруч»), 600 (720 − 120 — забули множник 2, тобто не врахували, що збірки можна переставити всередині блоку).

Приклад 5. Обчисліть (8! − 7!) / 6!

Це завдання з вибором однієї відповіді з п'яти.

Спочатку винесемо спільний множник 7! у чисельнику:

$$\frac{8!-7!}{6!}=\frac{7!\cdot (8-1)}{6!}=\frac{7!\cdot 7}{6!}$$

Тепер 7! = 7 · 6!, тому:

$$\frac{7\cdot 6!\cdot 7}{6!}=7\cdot 7=49$$

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

Розбір дистракторів: 56 (8! / 6! = 8 · 7 — не врахували віднімання в чисельнику), 55 (56 − 1 — вважали, що 7! / 6! = 1, а насправді 7! / 6! = 7), 63 (56 + 7 — додали замість віднімання), 7 (7! / 6! = 7 — після винесення 7! за дужки забули множник 8 − 1 = 7).

Нижче наведено найпоширеніші помилки, яких припускаються учні під час розв'язування задач на перестановки. Уважно прочитай кожну — і ти не втратиш бали на НМТ.

• Забувають переставити склеєні елементи між собою: у задачі «двоє поруч» дають відповідь (n − 1)! замість правильної 2 · (n − 1)!. Наприклад, для 6 книжок пишуть 120 замість 240.

• «Не поруч» рахують як n! − (n − 1)!, забувши множник 2. Правильно: n! − 2 · (n − 1)!. Наприклад, для 6 книжок отримують 600 замість 480.

• У числах з цифрою 0 рахують n! замість n! − (n − 1)!. Для цифр 0, 1, 3, 5, 7 дають 120 замість 96 — не відкидають варіанти з нулем на першому місці.

• Вважають 0! = 0. Насправді 0! = 1. Запам'ятай це як факт — він знадобиться для формул із комбінаціями.

• Скорочують факторіали як звичайні числа: 10! / 5! = 2! (насправді 10! / 5! = 30 240) або 2! + 3! = 5! (насправді 2! + 3! = 8). Факторіали — це не числа, які можна скорочувати без розкриття.

• Застосовують Pₙ, коли впорядковують не всі елементи: якщо в задачі з 8 учнів вибирають і ставлять у чергу лише 5 — це вже не перестановка, а розміщення (наступна тема). Перестановка — це коли беруть усі n елементів.

Завдання на перестановки входять до теми програми «Перестановки, комбінації, розміщення (без повторень)…» розділу «Елементи комбінаторики, початки теорії ймовірностей та елементи математичної статистики». Програма вимагає знати означення перестановки (без повторень) і вміти «розв'язувати задачі на перестановки». Перестановок з повтореннями програма не містить, тому на НМТ їх не буде.

Формула Pₙ = n! є в довідкових матеріалах, які ти отримаєш на тестуванні. Проте значення факторіалів до 8! варто знати напам'ять — це заощадить час: не доведеться щоразу перемножувати 1 · 2 · 3 · … під час тесту.

Формат завдань:

• У завданнях 1–15 — вибір однієї відповіді з п'яти (А–Д), 0 або 1 бал. Тут можуть дати просту факторіальну задачу або спрощення виразу з факторіалами.

• Комбінаторна задача з короткою відповіддю — у демоваріанті 2026 це завдання 20, 2 бали без часткових балів. Відповідь — ціле число.

Стратегія

• Велику відповідь (5 040, 40 320) звіряй з варіантами за порядком величини — іноді досить прикинути, скільки нулів у числі.

• Формулу перевір на малому випадку: 3 елементи дають 6 перестановок. Якщо твоя формула для n = 3 дає щось інше — ти помилився.

• Уважно читай умову: чи всі елементи впорядковуються? Чи є серед цифр нуль? Чи мають елементи стояти поруч?

• n! = 1 · 2 · … · n, 0! = 1, n! = n · (n − 1)!

• Pₙ = n! — упорядковуємо всі n різних елементів.

• Фіксований елемент — переставляємо решту: (n − 1)!.

• «Поруч» — склеюємо в блок: 2! · (n − 1)!.

• «Не поруч» = n! − 2 · (n − 1)!.

• З нулем серед цифр: n! − (n − 1)!.