2. Методичні вказівки #

Цей розділ самодостатній: він містить усі означення та формули комбінаторики, потрібні для виконання завдань із 3task.md, а також прийоми, за якими задачу відносять до одного з типів. Кожен тип супроводжено одним демонстраційним прикладом на інших даних, ніж у варіантах, — щоб показати метод, не розв’язуючи жодного варіанта. Ширший виклад із доведеннями див. у Лекції 9.

Комбінаторика відповідає на запитання «скількома способами?»: скільки різних результатів має вибір, розстановка чи розподіл об’єктів. Майже кожна така задача зводиться до двох правил лічби й до чотирьох формул вибірки, які розрізняють двома запитаннями — чи важливий порядок? і чи дозволені повтори?.

2.1 Два правила лічби: сума й добуток #

Правило суми. Якщо об’єкт можна вибрати одним із кількох несумісних (взаємовиключних) способів — першим способом $m_1$ варіантів, другим $m_2$, …, $r$-м $m_r$ варіантів, — то загальна кількість варіантів дорівнює

$$m_1 + m_2 + \dots + m_r.$$

Ознака в тексті — сполучник «або»: беремо те або те, випадки не перетинаються.

Правило добутку. Якщо вибір складається з послідовних кроків, причому перший крок можна зробити $n_1$ способами, після нього другий — $n_2$ способами, …, $k$-й — $n_k$ способами (кількість варіантів кожного кроку не залежить від зробленого раніше вибору), то вся процедура має

$$n_1 \cdot n_2 \cdots n_k$$

результатів. Ознака в тексті — сполучник «і»: спершу одне, потім інше, і так далі.

Правило добутку зручно бачити як дерево вибору: кожен крок розгалужує кожну гілку на стільки нових, скільки варіантів має цей крок; кількість результатів — це кількість листків дерева.

Приклад 2.1 (правило суми). На полиці 4 різні підручники з математики та 3 різні — з фізики. Узяти один підручник можна $4 + 3 = 7$ способами: випадки «взяти математику» та «взяти фізику» несумісні, тож кількості додаються.

Приклад 2.2 (правило добутку). Макет візитівки складають, обираючи шрифт заголовка (4 варіанти) і колір тексту (3 варіанти). Оскільки вибір робиться у два кроки, усього макетів $4 \cdot 3 = 12$.

Зауваження. Правила суми й добутку часто працюють разом: складну задачу розбивають на несумісні випадки (сума), а кожен випадок лічать за кроками (добуток). Усі формули §§2.2–2.4 — це, по суті, правило добутку, згорнуте у компактний запис.

2.2 Впорядкований вибір: перестановки та розміщення #

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

Означення (перестановки). Перестановка — це впорядкований набір усіх $n$ різних елементів множини. Кількість перестановок

$$P_n = n! = 1 \cdot 2 \cdot 3 \cdots n, \qquad 0! = 1.$$

Кожну з $n$ позицій заповнюють по черзі: на першу є $n$ кандидатів, на другу — $n-1$ (один уже використано), далі $n-2$, і так до останньої позиції з єдиним кандидатом; за правилом добутку дістаємо $n(n-1)\cdots 1 = n!$.

Приклад 2.3 (перестановки). П’ять різних книжок розставляють у ряд на полиці. Кількість розстановок $P_5 = 5! = 120$.

Означення (розміщення). Розміщення з $n$ елементів по $k$ ($k \le n$) — це впорядкований набір із $k$ різних елементів, вибраних із $n$. Кількість розміщень

$$A_n^{k} = \frac{n!}{(n-k)!} = \underbrace{n(n-1)\cdots(n-k+1)}_{k \text{ множників}}.$$

Перша позиція має $n$ варіантів, друга $n-1$, …, $k$-та $n-k+1$; це $k$ спадних множників, що й дає $\dfrac{n!}{(n-k)!}$. Перестановки — окремий випадок розміщення при $k = n$: $\; A_n^{n} = \dfrac{n!}{0!} = n! = P_n$.

Приклад 2.4 (розміщення). У редакції 7 працівників; треба призначити трьох на різні посади: головного редактора, коректора та верстальника. Оскільки посади різні (порядок важливий), а одна людина обіймає одну посаду (без повторів), це розміщення: $A_7^{3} = \dfrac{7!}{4!} = 7 \cdot 6 \cdot 5 = 210$.

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

$$\overline{A}_n^{k} = n^{k}.$$

Це буквально правило добутку з однаковим числом варіантів $n$ на кожному з $k$ кроків. Такий тип упізнають за словами «кожен незалежно», «можуть повторюватися», «з поверненням».

Приклад 2.5 (кортеж, повтори дозволені). Кодовий замок відмикає тризначний код, кожен розряд якого — одна з чотирьох кнопок $\{A, B, C, D\}$; кнопки можуть повторюватися. Різних кодів $\overline{A}_{4}^{3} = 4^{3} = 64$.

2.3 Невпорядкований вибір: сполучення #

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

Означення (сполучення). Сполучення з $n$ елементів по $k$ — це $k$-елементна підмножина множини з $n$ елементів (вибір без урахування порядку, без повторів). Кількість сполучень

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

Формулу дістають зі співвідношення $A_n^{k} = C_n^{k} \cdot k!$: кожній підмножині з $k$ елементів відповідає рівно $k!$ її впорядкувань (розміщень), тож розміщень рівно у $k!$ разів більше, ніж сполучень; звідси $C_n^{k} = \dfrac{A_n^{k}}{k!} = \dfrac{n!}{k!\,(n-k)!}$. Корисна симетрія: $C_n^{k} = C_n^{\,n-k}$.

Приклад 2.6 (сполучення). З 8 підготованих статей до одного номера журналу відбирають 3. Порядок відбору неістотний (важливо лише, які три статті), тож це сполучення: $C_8^{3} = \dfrac{8!}{3!\,5!} = \dfrac{8 \cdot 7 \cdot 6}{1 \cdot 2 \cdot 3} = 56$.

2.4 Вибірки з повтореннями (коротко) #

Два випадки, у яких елементи можуть повторюватися.

Перестановки з повтореннями. Якщо серед $n$ об’єктів є однакові — $n_1$ об’єктів одного сорту, $n_2$ другого, …, $n_m$ $m$-го, причому $n_1 + n_2 + \dots + n_m = n$, — то кількість різних перестановок

$$P_n(n_1, n_2, \dots, n_m) = \frac{n!}{n_1!\,n_2! \cdots n_m!}.$$

(Ділимо $n!$ на факторіали кратностей, бо перестановки однакових об’єктів усередині свого сорту не дають нового набору.)

Приклад 2.7 (перестановки з повтореннями). Скільки різних «слів» можна отримати, переставляючи букви слова МАМА? Тут $n = 4$, буква М повторюється $2$ рази й буква А — $2$ рази, тож $P_4(2,2) = \dfrac{4!}{2!\,2!} = 6$ (а саме: МАМА, ММАА, МААМ, АМАМ, АММА, ААММ).

Сполучення з повтореннями (мультимножини). Вибір $k$ об’єктів із $n$ типів, коли порядок неважливий, а повтори дозволені (рівносильно — розподіл $k$ однакових предметів по $n$ різних скриньках), лічать за формулою

$$\overline{C}_n^{k} = C_{n+k-1}^{\,k}.$$

Наочна модель — «зорі та риски»: $k$ зірочок і $n-1$ рисок-роздільників у ряд.

Приклад 2.8 (сполучення з повтореннями). У кав’ярні 4 види тістечок; купують 6 тістечок, види можуть повторюватися, порядок неважливий. Способів $\overline{C}_4^{6} = C_{4+6-1}^{6} = C_9^{6} = C_9^{3} = 84$.

2.5 Як розпізнати тип задачі #

Тип вибірки визначають два запитання.

1. Чи важливий порядок? Якщо переставляння елементів дає інший результат (посади, місця, цифри номера, послідовність) — порядок важливий. Якщо результат той самий (склад команди, набір кольорів, підмножина) — неважливий.
2. Чи дозволені повтори? Чи може той самий елемент з’явитися двічі (той самий колір на кількох об’єктах, та сама цифра в коді)? Якщо об’єкти вибирають «без повернення» (кожен використовують щонайбільше раз) — повторів немає.

Відповіді на ці два запитання однозначно обирають формулу:

Різницю між трьома основними схемами найкраще видно на одному й тому самому наборі $\{1,2,3\}$: перестановки впорядковують усі елементи, розміщення — упорядкована частина, сполучення — неврахований порядок.

Зауваження (та сама задача — різні типи). Візьмемо 9 різних олівців. «Скількома способами покласти 4 з них у пенал?» — порядок неважливий, це сполучення $C_9^{4}$. «Скількома способами розкласти 4 з них по 4 позначених комірках органайзера?» — тепер порядок (комірки різні) важливий, це розміщення $A_9^{4} = C_9^{4}\cdot 4!$. Змінилося одне слово умови — змінився тип.

Типова помилка (плутати розміщення й сполучення). Якщо в умові фігурують різні ролі, місця чи позиції (капітан і заступник, посади, розряди номера) — порядок важливий, беруть $A_n^{k}$. Якщо ж усі вибрані рівноправні (просто «група», «набір», «команда») — порядок неважливий, беруть $C_n^{k}$. Питання «чи міняє щось перестановка вибраних?» вирішує суперечку.

2.6 Робочий алгоритм #

1. Прочитати умову й виділити множину, з якої вибирають ($n$), і скільки вибирають чи розставляють ($k$).
2. Поставити два запитання (§2.5): порядок? повтори? — і за таблицею назвати тип і формулу.
3. Якщо задача складена — розбити її на кроки (правило добутку) або на несумісні випадки (правило суми), знайти кількість у кожному й перемножити / додати.
4. Підставити числа й обчислити. Дуже великі результати (як-от $28!$ чи $3^{13}$) дозволено лишати у вигляді добутку або факторіала разом із формулою — головне правильно вказати тип і вираз, а не довести множення до останньої цифри.
5. Перевірити здоровим глуздом: чи не переплутано «важливий/неважливий порядок», чи не полічено той самий результат двічі.

Practical/Practical5/2method.md · 15.8 KB · updated 2026-08-04 14:37