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

У комбінаториці ми часто стикаємося із ситуацією, коли з кількох різних об’єктів треба вибрати кілька й розставити їх у певному порядку. Наприклад, з 25 учнів класу обрати старосту й заступника — це не просто "двоє людей", а конкретні ролі: та сама пара в різних ролях дає різний результат. Саме для таких задач існує поняття розміщення без повторень.

Що таке розміщення без повторень

Розміщенням з n елементів по k (позначають Aₙᵏ) називають упорядкований набір із k різних елементів, вибраних із даної множини, що містить n різних елементів, причому k ≤ n. Слово «упорядкований» — ключове: зміна порядку елементів дає нове розміщення, навіть якщо склад вибраних той самий.

Формула для обчислення числа розміщень:

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

Ця формула є в довідкових матеріалах НМТ, тому запам’ятовувати її не обов’язково — важливо розуміти, як нею користуватися.

Як обчислювати: добуток k спадних множників

На практиці зручніше не обчислювати факторіали окремо, а записати Aₙᵏ як добуток k послідовних спадних множників, починаючи з n:

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

Чому так? За правилом добутку: на першу позицію можна поставити будь-якого з n кандидатів; після цього на другу позицію залишається n − 1 кандидатів (одного вже використали); на третю — n − 2; і так далі, поки не виберемо всі k позицій. Перемноживши ці числа, отримуємо шукану кількість.

Приклади:

• $$A_7^3=7\cdot 6\cdot 5=210$$

• $$A_{10}^2=10\cdot 9=90$$

• $$A_6^4=6\cdot 5\cdot 4\cdot 3=360$$

Окремі випадки

Зверни увагу: Aₙⁿ = n! = Pₙ. Перестановка — це окремий випадок розміщення, коли вибирають усі елементи.

Приклад: староста й заступник

У класі 25 учнів. Треба обрати старосту та його заступника. Скількома способами це можна зробити?

Маємо n = 25 учнів, вибираємо k = 2 особи на різні посади. Порядок важливий: «староста Іван, заступник Олена» і «староста Олена, заступник Іван» — це два різні варіанти. Тому:

$$A_{25}^2=25\cdot 24=600$$

Отже, існує 600 способів обрати старосту й заступника.

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

Посади та призові місця

Якщо з n людей треба призначити на k різних посад, кількість способів — це Aₙᵏ. Кожна посада — унікальна роль, тому порядок призначення має значення.

• Голова, секретар і скарбник з 12 членів клубу: $$A_{12}^3=12\cdot 11\cdot 10=1320$$ способів.

• Золото, срібло й бронза серед 8 команд: $$A_8^3=8\cdot 7\cdot 6=336$$ варіантів розподілу медалей.

Розклад занять і прапори

Коли з набору предметів чи кольорів треба вибрати кілька й розташувати їх у певному порядку (наприклад, у розкладі уроків або на прапорі), знову працюють розміщення.

• 4 різні уроки в понеділок з 9 предметів: $$A_9^4=9\cdot 8\cdot 7\cdot 6=3024$$ варіанти розкладу.

• Прапор із трьох горизонтальних смуг різних кольорів, якщо є тканина 6 кольорів: $$A_6^3=6\cdot 5\cdot 4=120$$ різних прапорів.

Турнір у два кола

У спортивних турнірах, де кожна пара команд грає двічі (вдома й на виїзді), кількість матчів дорівнює Aₙ². Для n команд кожна зустріч — це впорядкована пара (господар, гість), тому порядок важливий.

Наприклад, для 10 команд: $$A_{10}^2=10\cdot 9=90$$ матчів.

Коди й числа з різних цифр

Особливість задач із цифрами — нуль не може стояти на першому місці числа (бо тоді це не число, а набір цифр). Розгляньмо два випадки.

Чотирицифровий код (пін-код) із різних цифр 0–9: тут код може починатися з нуля, тому просто $$A_{10}^4=10\cdot 9\cdot 8\cdot 7=5040$$.

Тризначні числа з різними цифрами: нуль на першому місці не можна. Є два способи розв'язання:

• Безпосередньо: на перше місце — 9 цифр (1–9), на друге — 9 (будь-яка з 10, крім першої), на третє — 8. Разом: 9 · 9 · 8 = 648

• Через розміщення: спочатку A₁₀³ = 720, потім віднімаємо ті, що починаються з нуля: A₉² = 9 · 8 = 72. 720 − 72 = 648

Запам'ятай: коли обчислюєш кількість чисел (не кодів!), завжди перевіряй, чи може нуль стояти на першому місці. Якщо ні — відніми варіанти з нулем попереду.

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

Тест «поміняй двох місцями»

Уяви, що ти вже вибрав k об'єктів. Поміняй двох із них місцями. Якщо отримав інший варіант — це розміщення. Якщо той самий — це комбінація.

Зв'язок між розміщеннями та комбінаціями

Існує простий зв'язок:

$$A_n^k=C_n^k\cdot k!$$

Спершу ми вибираємо k елементів без урахування порядку — це можна зробити Cₙᵏ способами. Потім упорядковуємо вибрану групу — це можна зробити k! способами. Перемноження дає кількість розміщень.

Наприклад: A₂₅² = 600, а двох однакових чергових з 25 учнів можна вибрати C₂₅² = 600 / 2! = 600 / 2 = 300 способами. Формула Cₙᵏ також є в довідкових матеріалах НМТ, а докладно ми розглянемо її в наступному юніті «Комбінації без повторень».

Розміщення чи перестановка?

Тут усе просто:

• Якщо вибирають усі n елементів — це перестановка Pₙ (або Aₙⁿ, що те саме).

• Якщо вибирають лише частину (k < n) — це розміщення Aₙᵏ.

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

Іноді в задачі дано кількість варіантів, а треба знайти n. Наприклад:

$$A_n^2=56\Rightarrow n(n-1)=56\Rightarrow n^2-n-56=0$$

Корені: n = 8 або n = −7. Від'ємний корінь відкидаємо, бо кількість елементів — натуральне число. Отже, n = 8.

Ще один приклад: турнір у два кола, зіграно 30 матчів. Скільки команд?

$$A_n^2=n(n-1)=30\Rightarrow n^2-n-30=0\Rightarrow n=6$$ (корінь −5 відкидаємо).

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

Приклад 1. Конкурс проєктів

Завдання. У конкурсі беруть участь 9 проєктів. Журі визначає переможця, друге й третє місця. Скільки існує варіантів розподілу цих місць?

Розв'язання. Маємо 9 проєктів (n = 9), і треба розподілити 3 різні місця (k = 3). Кожне місце унікальне: бути першим — не те саме, що другим. Отже, порядок важливий — це розміщення.

$$A_9^3=9\cdot 8\cdot 7=504$$

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

Чому інші варіанти неправильні:

• 84 — це C₉³ (комбінація), тобто вибір трьох проєктів без урахування місць. Порядок місць тут проігноровано.

• 729 — це 9³, коли припускають, що один проєкт може зайняти кілька місць (повторення), але проєкти різні.

• 27 — це 9 · 3, примітивне множення n на k.

• 362 880 — це 9!, тобто перестановка всіх 9 проєктів, а не вибір трьох.

Приклад 2. Чотирицифрові числа з непарними цифрами

Завдання. Скільки існує чотирицифрових чисел, у записі яких усі цифри різні й непарні?

Розв'язання. Непарні цифри: 1, 3, 5, 7, 9 — усього 5 цифр. Оскільки нуля серед них немає, проблема першої цифри не виникає. Маємо n = 5, k = 4, порядок важливий (різні числа — різний порядок цифр).

$$A_5^4=5\cdot 4\cdot 3\cdot 2=120$$

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

Поширені помилки: 625 = 5⁴ — допускають повторення цифр, а за умовою всі цифри різні. 5 = C₅⁴ — вибирають чотири цифри без урахування порядку, але різний порядок дає різні числа.

Приклад 3. Прапор із трьох смуг

Завдання. Скільки різних прапорів із трьох горизонтальних смуг можна скласти з тканини 7 кольорів, якщо всі смуги різного кольору?

Розв'язання. Маємо 7 кольорів (n = 7), обираємо 3 смуги (k = 3). Смуги розташовані в певному порядку: верхня, середня, нижня — зміна порядку кольорів дає інший прапор. Отже, це розміщення.

$$A_7^3=7\cdot 6\cdot 5=210$$

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

Дистрактори: 35 = C₇³ (комбінація — не враховують порядок смуг); 343 = 7³ (повторення кольорів дозволені); 21 = 7 · 3 (просте множення); 5 040 = 7! (перестановка всіх семи кольорів).

Приклад 4. Шаховий турнір

Завдання. У шаховому турнірі кожен учасник зіграв з кожним по дві партії — білими й чорними. Усього зіграно 132 партії. Скільки було учасників?

Розв'язання. Для n учасників кожна пара грає дві партії (одну білими, одну чорними); партію задає впорядкована пара «хто грає білими, хто — чорними», тому кількість партій — це Aₙ²:

$$A_n^2=n(n-1)=132$$

$$n^2-n-132=0$$

$$n=\frac{1\pm \sqrt{1+528}}{2}=\frac{1\pm 23}{2}$$

Корені: n = 12 та n = −11. Від'ємний корінь відкидаємо.

Відповідь: 12 учасників.

Пастка: деякі учні помилково ділять на 2, розв'язуючи рівняння n(n−1)/2 = 132. Воно не має натурального розв'язку, бо n² − n − 264 = 0 дає дискримінант 1 + 1 056 = 1 057, який не є повним квадратом.

Приклад 5. Прибираємо чи чергуємо?

Завдання. З 8 учнів вибирають двох. У першому випадку обоє прибирають клас, у другому один миє дошку, а другий поливає квіти. Скільки способів вибору в кожному випадку?

Розв'язання. Перший випадок: обоє виконують однакову роботу. Порядок неважливий — це комбінація:

$$C_8^2=\frac{8\cdot 7}{2}=28$$

Другий випадок: роботи різні (мити дошку ≠ поливати квіти). Порядок важливий — це розміщення:

$$A_8^2=8\cdot 7=56$$

Відповідь: 28 і 56 (спочатку для однакових ролей, потім для різних).

Дистрактори: «56 і 28» — переплутали місцями; «56 і 56» — не помітили різниці в ролях; «16 і 64» — примітивне множення; «28 і 28» — не врахували, що в другому випадку ролі різні.

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

• Застосовують комбінації замість розміщень. Коли ролі різні (посади, призові місця), учні іноді обчислюють C₂₅² = 300 замість A₂₅² = 600. Перевіряй тестом «поміняй двох місцями».

• Множать n на k або підносять n до степеня k. Наприклад, замість A₉³ = 504 пишуть 9 · 3 = 27 або 9³ = 729. Запам'ятай: розміщення — це добуток k спадних множників, а не множення на k.

• Беруть неправильну кількість множників. Наприклад, A₁₀³ = 10 · 9 = 90 (тільки 2 множники замість 3) або 10 · 9 · 8 · 7 = 5 040 (4 множники замість 3). Кількість множників має дорівнювати k.

• Рахують числа, не враховуючи нуль на першому місці. У тризначних числах з різними цифрами часто отримують 720 (A₁₀³) замість правильних 648. Не забувай: нуль не може бути першою цифрою числа.

• Плутають знаменник у формулі. Пишуть n! / k! замість n! / (n − k)!. Наприклад, A₇³ = 7! / 3! = 840 (неправильно) замість 7! / 4! = 210 (правильно). Перевіряй через добуток k множників.

• У рівнянні Aₙ² = 56 розв'язують n² = 56. Це дає n ≈ 7,5, що не є цілим числом. Правильно: n(n − 1) = 56, тобто квадратне рівняння n² − n − 56 = 0. Також не забувай відкидати від'ємний корінь.

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

Довідкові матеріали

На НМТ ти отримаєш довідкові матеріали, у яких є всі три формули:

• $$P_n=n!$$ — перестановки

• $$A_n^k=\frac{n!}{(n-k)!}$$ — розміщення

• $$C_n^k=\frac{n!}{k!(n-k)!}$$ — комбінації

Увага! Довідка не підказує, яку з формул застосувати. Це вирішує питання «чи важливий порядок». Якщо порядок має значення — бери розміщення. Якщо ні — комбінації. Якщо використовуються всі елементи — перестановки.

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

Стратегія

• Факторіали не обчислюй повністю. Відразу скорочуй до добутку k множників. Наприклад, A₁₀³ = 10! / 7! = 10 · 9 · 8 = 720 — не треба розписувати 10! повністю.

• Застосовуй тест «поміняй двох місцями». Це займає 2 секунди, але рятує від найпоширенішої помилки — вибору комбінації замість розміщення.

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

• Розміщення Aₙᵏ — вибираємо k з n різних елементів, і порядок (ролі) важливий.

• $$A_n^k=\frac{n!}{(n-k)!}=n\cdot (n-1)\cdot \dots \cdot (n-k+1)$$ — рівно k множників.

• $$A_n^n=P_n=n!$$ — перестановка, $$A_n^1=n$$.

• Поміняли двох вибраних місцями й отримали новий варіант — розміщення; той самий — комбінація.

• $$A_n^k=C_n^k\cdot k!$$ — зв'язок між розміщеннями та комбінаціями.

• У задачах на числа нуль не може бути першою цифрою — враховуй це при обчисленні.

• Рівняння Aₙ² = m зводиться до квадратного рівняння n² − n − m = 0; від'ємний корінь відкидай.