Комбінації без повторень

У попередніх темах ти навчився впорядковувати всі n елементів (перестановки) й обирати k елементів, коли порядок серед них важливий (розміщення). Але в багатьох життєвих ситуаціях порядок не має значення: чи виберемо ми трьох чергових як {Іван, Марія, Петро} чи {Петро, Марія, Іван} — це та сама група. Саме такі задачі розв'язує комбінація без повторень.

Означення комбінації

Комбінацією з n елементів по k (записують Cₙᵏ) називають неупорядкований набір (підмножину) з k різних елементів, вибраних із заданої множини з n різних елементів. Ключова умова: порядок розташування елементів усередині набору не важливий. Два набори вважаються однаковими, якщо вони складаються з тих самих елементів, незалежно від того, в якому порядку ми їх перерахували.

Формула числа комбінацій

Кількість комбінацій з n елементів по k обчислюють за формулою:

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

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

Зв'язок із розміщеннями дуже простий: Cₙᵏ = Aₙᵏ / k!. Кожну неупорядковану групу з k елементів можна впорядкувати k! способами, тому кількість розміщень у k! разів більша. Наприклад, обираючи 3 осіб з 10 і призначаючи їм різні ролі, маємо A₁₀³ = 10·9·8 = 720 способів. А якщо ролі однакові, то кожні 3! = 6 способів впорядкування дають ту саму групу, тому C₁₀³ = 720 : 6 = 120.

Як швидко обчислювати Cₙᵏ

Використовуй практичний спосіб: у чисельнику запиши k спадних множників, починаючи від n, а в знаменнику — k!:

$$C_n^k=\frac{n\cdot (n-1)\cdot (n-2)\cdot \dots \cdot (n-k+1)}{1\cdot 2\cdot 3\cdot \dots \cdot k}$$

Подивись на приклади:

• C₁₀³ = (10·9·8) / (1·2·3) = 720 / 6 = 120

• C₈³ = (8·7·6) / (1·2·3) = 336 / 6 = 56

• C₆² = (6·5) / (1·2) = 30 / 2 = 15

• C₇³ = (7·6·5) / (1·2·3) = 210 / 6 = 35

• C₁₂² = (12·11) / (1·2) = 132 / 2 = 66

• C₁₅³ = (15·14·13) / (1·2·3) = 2 730 / 6 = 455

Поміть закономірність: Cₙ² — це півдобутку n і n−1, тобто n(n−1)/2. Це часто трапляється в задачах, тому варто запам'ятати.

Властивості числа комбінацій

Властивість симетричності надзвичайно корисна. Вибрати 18 учнів з 20 для екскурсії — це те саме, що вибрати 2 учнів, які залишаться. Набагато простіше порахувати C₂₀² = (20·19) / 2 = 190, ніж тягнути C₂₀¹⁸ через 18 множників! Завжди дивись: якщо k > n/2, то зручніше обчислити Cₙⁿ⁻ᵏ.

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

Групи з однаковими ролями

Якщо з-поміж людей вибирають групу, у якій усі мають однакову функцію (чергові, делегати, учасники олімпіади, команда без розподілу ролей), то порядок не важливий — це комбінація.

• Делегація з 4 учнів з 9: C₉⁴ = (9·8·7·6) / (1·2·3·4) = 3 024 / 24 = 126

• 3 книжки з 7 у подарунок (усі книжки різні, даруємо набір, без визначення, хто яку отримає): C₇³ = 35

• 5 яблук з 10 для компоту: C₁₀⁵

Сигнальні слова, які підказують, що перед тобою комбінація: «групу», «набір», «делегацію», «команду без ролей», «букет», «подарунок» (якщо не сказано, що кожен отримує щось конкретне).

Рукостискання й турніри в одне коло

Коли кожен учасник зустрічі потискає руку кожному іншому, кожне рукостискання — це неупорядкована пара з двох осіб (рукостискання Івана з Марією те саме, що Марії з Іваном). Отже, для n осіб кількість рукостискань дорівнює Cₙ².

• 10 осіб: C₁₀² = (10·9) / 2 = 45 рукостискань

• 8 команд в одноколовому турнірі (кожна грає з кожною один раз): C₈² = 28 матчів. Якби грали двоколовий турнір (кожна вдома й у гостях), то порядок важливий — це A₈² = 56 матчів.

Буває й обернена задача: відомо кількість рукостискань, потрібно знайти кількість учасників. Наприклад, в одне коло зіграли 45 матчів. Скільки команд? Розв'язуємо рівняння n(n − 1) / 2 = 45 ⇒ n(n − 1) = 90 ⇒ n² − n − 90 = 0 ⇒ n = 10 (від'ємний корінь не підходить).

Геометричні фігури з точок

Якщо на площині позначено n точок, з яких жодні три не лежать на одній прямій, то:

• Кількість відрізків з кінцями в цих точках: Cₙ² (відрізок AB — це те саме, що BA). Для 6 точок: C₆² = 15.

• Кількість трикутників з вершинами в цих точках: Cₙ³ (набір із трьох вершин задає трикутник, порядок вершин не важливий). Для 6 точок: C₆³ = 20.

Для точок на колі умова «жодні три не лежать на одній прямій» виконується автоматично. Тому для 9 точок на колі кількість трикутників — C₉³ = 84.

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

Дерево рішень

Перше запитання: чи беремо ми всі n елементів без винятку? Якщо так — це перестановка Pₙ. Якщо ні (вибираємо лише частину) — переходимо до другого запитання.

Друге запитання: чи важливий порядок розташування вибраних елементів? Чи мають вони різні ролі, місця, посади? Якщо так — розміщення Aₙᵏ. Якщо ні (усі вибрані рівноправні) — комбінація Cₙᵏ.

Порівняння на одних даних

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

Перевірка малим випадком

Візьми 4 літери: A, B, C, D. Скільки можна утворити пар?

• Без урахування порядку (комбінації): AB, AC, AD, BC, BD, CD — усього 6. Це C₄² = 6.

• З урахуванням порядку (розміщення): AB, BA, AC, CA, AD, DA, BC, CB, BD, DB, CD, DC — усього 12. Це A₄² = 12.

Різниця вдвічі — саме тому в знаменнику Cₙᵏ є k! (тут 2! = 2).

Частково важливий порядок

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

• Спершу вибрати 5 гравців (C₁₀⁵ = 252), а потім з них вибрати капітана (5 способів): 252 · 5 = 1 260

• Спершу вибрати капітана (10 способів), а потім решту 4 гравців з 9, які залишилися (C₉⁴ = 126): 10 · 126 = 1 260

Зверни увагу: це не «чиста» комбінація й не «чисте» розміщення — тут комбінується правило добутку з комбінацією.

Рідко коли задача зводиться до однієї комбінації. Найчастіше доводиться комбінувати Cₙᵏ з правилами суми й добутку, які ти вже знаєш.

Правило добутку: склад з частин

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

Приклад 1. У класі 5 хлопців і 6 дівчат. Скількома способами можна вибрати 2 хлопців і 3 дівчат для прибирання території? Хлопців обираємо C₅² = 10 способами, дівчат — C₆³ = 20 способами. Оскільки вибір хлопців не залежить від вибору дівчат, ці числа перемножуємо: 10 · 20 = 200.

Приклад 2. З 8 різних книжок і 6 різних журналів потрібно вибрати 3 книжки й 2 журнали. C₈³ · C₆² = 56 · 15 = 840 способів.

Правило суми: кілька складів

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

Приклад. У групі 4 хлопці й 5 дівчат. Скількома способами можна вибрати 3 осіб так, щоб дівчат серед них було не менше двох? Це означає: або 2 дівчини й 1 хлопець, або 3 дівчини (і 0 хлопців):

• 2 дівчини з 5 і 1 хлопець з 4: C₅² · C₄¹ = 10 · 4 = 40

• 3 дівчини з 5 (хлопців не беремо): C₅³ = 10

• Загалом: 40 + 10 = 50 способів

Прийом «хоча б один» — доповнення

Найелегантніший спосіб розв'язати задачу, де сказано «хоча б один», — порахувати всі можливі групи без жодного обмеження, а потім відняти ті, у яких немає потрібного елемента.

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

• Без обмежень: C₁₀⁴ = 210

• Групи без жодної дівчини (самі хлопці): C₆⁴ = 15

• Групи з хоча б однією дівчиною: 210 − 15 = 195

Чому не можна рахувати інакше?

Типове хибне міркування: «вибрати одну дівчину, а решту трьох — з решти 9 осіб будь-як» дає 4 · C₉³ = 4 · 84 = 336 ≠ 195. Чому результат завищений? Тому що групу, де є, наприклад, дві дівчини, пораховано кілька разів: спершу дівчину №1 як «ту саму одну», а потім дівчину №2 як частину «решти»; потім навпаки. Для групи з трьома дівчатами — ще більше повторів. Тому метод «спершу одну, потім решту» не працює.

Запам'ятай: «хоча б один» = усі групи — групи без нього. Це універсальний і безпомилковий прийом.

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

Приклад 1. Делегація на олімпіаду

Умова: Скількома способами можна вибрати 3 учнів з 12 для участі в олімпіаді? (усі учні різні, ролі однакові).

Розв'язання: Беремо частину (3 з 12), порядок не важливий (усі просто «учасники»). Отже, C₁₂³ = (12·11·10) / (1·2·3) = 1 320 / 6 = 220.

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

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

• 1 320 — це A₁₂³ = 12·11·10 (розміщення, порядок урахували, а він не важливий)

• 1 728 — це 12³ (вибір з повтореннями, не підходить)

• 36 — це 12·3 (безглузде множення)

• 4 — це 12 : 3 (ділення замість комбінації)

Приклад 2. Яблука й груші

Умова: У кошику 7 різних яблук і 5 різних груш. Скількома способами можна вибрати 3 яблука й 2 груші?

Розв'язання: Це комбінація з правилом добутку. Яблука: C₇³ = (7·6·5) / (1·2·3) = 35. Груші: C₅² = (5·4) / (1·2) = 10. Разом: 35 · 10 = 350.

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

Типові пастки: 45 (C₇³ + C₅² — додавання замість множення) і 792 (C₁₂⁵ — вибрали 5 предметів з усіх 12, не врахувавши, що склад має бути саме 3 яблука й 2 груші, а не будь-які 5 фруктів).

Приклад 3. Трикутники на колі

Умова: На колі позначено 9 точок. Скільки існує трикутників з вершинами в цих точках?

Розв'язання: Трикутник визначається трьома вершинами, порядок вершин не важливий. Оскільки точки на колі, жодні три не лежать на одній прямій. Отже, C₉³ = (9·8·7) / (1·2·3) = 504 / 6 = 84.

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

Дистрактори: 504 (A₉³ — порядок вершин уважали важливим), 36 (C₉² — порахували відрізки, а не трикутники), 27 (9·3), 3 (9 : 3).

Приклад 4. Хоча б одна дівчина

Умова: У класі 8 хлопців і 6 дівчат. Скількома способами можна вибрати 4 учнів так, щоб серед них була хоча б одна дівчина?

Розв'язання: Застосовуємо прийом доповнення. Всі способи вибрати 4 учнів з 14: C₁₄⁴ = (14·13·12·11) / (1·2·3·4) = 24 024 / 24 = 1 001. Способи вибрати 4 учнів без жодної дівчини (самих хлопців): C₈⁴ = (8·7·6·5) / (1·2·3·4) = 1 680 / 24 = 70. Отже, груп з хоча б однією дівчиною: 1 001 − 70 = 931.

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

Поширена пастка: 6 · C₁₃³ = 6 · 286 = 1 716. Так рахують ті, хто пробує «вибрати одну дівчину, а решту будь-як». Це не працює, бо групи з двома й більше дівчатами пораховані кілька разів.

Приклад 5. Рукостискання

Умова: Кожен учасник зустрічі потиснув руку кожному іншому. Усього було 66 рукостискань. Скільки було учасників?

Розв'язання: Кількість рукостискань для n учасників дорівнює Cₙ² = n(n − 1) / 2. Маємо рівняння: n(n − 1) / 2 = 66 ⇒ n(n − 1) = 132 ⇒ n² − n − 132 = 0. Дискримінант D = 1 + 528 = 529 = 23². Корені: n = (1 ± 23) / 2. Натуральний корінь: n = 12.

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

Пастки: 33 (66 : 2 — просто поділили кількість рукостискань на 2 замість розв'язати рівняння n(n − 1) / 2 = 66); рівняння n(n − 1) = 66 (забули про ділення на 2) не має натурального розв'язку (8·7 = 56, 9·8 = 72).

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

• Розміщення замість комбінацій. Коли вибирають групу без ролей (наприклад, 3 учнів з 12 на олімпіаду), іноді рахують A₁₂³ = 1 320 замість C₁₂³ = 220. Завжди питай себе: «Чи важливий порядок?» Якщо ні — діли на k!.

• Забувають k! у знаменнику. Формула n! / (n − k)! дає розміщення, а не комбінації. Комбінація вимагає ще одного ділення на k!. Якщо сумніваєшся — перевір малим випадком (наприклад, 4 літери A, B, C, D: пар має бути 6, а n!/(n−k)! дає 12).

• Додають комбінації частин складу. Наприклад, вибрати 3 яблука з 7 і 2 груші з 5. Хтось рахує C₇³ + C₅² = 35 + 10 = 45. Правильно: C₇³ · C₅² = 350. Коли склад складається з незалежних частин — множ, а не додавай.

• «Хоча б одна дівчина» рахують як «одна дівчина, а решта будь-хто». Це дає 6 · C₁₃³ = 1 716 замість 931. Помилка в тому, що групи з двома й більше дівчатами пораховані кілька разів. Єдино правильний шлях: усі групи мінус групи без жодної дівчини.

• Не користуються рівністю Cₙᵏ = Cₙⁿ⁻ᵏ. Замість того щоб порахувати C₂₀¹⁸ як C₂₀² = 190, витрачають час на довге обчислення й часто помиляються. Якщо k > n/2 — заміни на n − k.

• Рукостискання рахують як n(n − 1). Це подвоює кількість, тому що кожне рукостискання пораховане двічі (Іван→Марія і Марія→Іван). Правильно: n(n − 1) / 2, тобто Cₙ².

Програма НМТ з математики включає означення комбінації (без повторень) і вимагає вміння «розв'язувати задачі на перестановки, комбінації, розміщення (без повторень) і комбінаторні правила суми та добутку». Саме цю навичку перевіряють у завданні 20 демоваріанта НМТ-2026.

Формат завдання: коротка відповідь (число), яке оцінюють у 2 бали без часткових балів — або ти отримав правильне число, або 0. У розібраних тестах 2023–2024 років на цій позиції траплялася як комбінаторика, так і середнє значення вибірки. Тому готуватися треба до обох тем.

Особливості запису відповіді: на НМТ коротку відповідь записують десятковим дробом, ураховуючи положення коми (наприклад, 2,5); знак «мінус» ставлять перед першою цифрою. Ціле число пишуть цифрами без пробілів між розрядами (931, а не «дев'ятсот тридцять один») і без одиниць вимірювання. Формулу Cₙᵏ ти знайдеш у довідкових матеріалах, виданих на тестуванні, разом із Pₙ і Aₙᵏ.

Стратегія розв'язування

• Уважно прочитай умову. Постав собі два запитання: «Чи беруть усі елементи?» і «Чи важливий порядок?».

• Визнач n (загальну кількість) і k (скільки вибирають).

• Якщо це комбінація — запиши дріб Cₙᵏ = n·(n−1)·…·(n−k+1) / (1·2·…·k) одразу скорочуючи, де можна.

• Якщо є підгрупи (яблука + груші) — перемнож окремі комбінації.

• Якщо в умові «хоча б один» — порахуй усі варіанти й відніми небажані.

• Cₙᵏ — вибираємо k різних елементів з n, порядок усередині вибраних не важливий.

• Cₙᵏ = n! / (k!(n−k)!) = Aₙᵏ / k!. Зручніше: у чисельнику k спадних множників від n, у знаменнику k!.

• Корисні властивості: Cₙᵏ = Cₙⁿ⁻ᵏ; Cₙ¹ = n; Cₙ² = n(n−1)/2.

• Алгоритм вибору формули: усі елементи → Pₙ; частина й порядок важливий → Aₙᵏ; частина й порядок не важливий → Cₙᵏ.

• Склад з незалежних частин (2 хлопці й 3 дівчини) — добуток комбінацій; різні взаємовиключні склади — сума.

• «Хоча б один» = усі можливі групи − групи без жодного потрібного елемента.

• Типові задачі: делегація, рукостискання, трикутники з точок, вибір книжок/фруктів.