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

Цей розділ **самодостатній**: він містить усі означення та формули комбінаторики,
потрібні для виконання завдань із [3task.md](3task.md), а також прийоми, за якими
задачу відносять до одного з типів. Кожен тип супроводжено **одним демонстраційним
прикладом на інших даних**, ніж у варіантах, — щоб показати метод, не розв'язуючи
жодного варіанта. Ширший виклад із доведеннями див. у
[Лекції 9](../../Lectures/ODM-L09.md).

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

## 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 $$
> результатів. Ознака в тексті — сполучник **«і»**: спершу одне, *потім* інше, *і*
> так далі.

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

![Дерево вибору для правила добутку: перший крок дає 3 гілки, другий — по 2, разом 6 листків](img/p5_tree.png)

**Приклад 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. **Чи дозволені повтори?** Чи може той самий елемент з'явитися двічі (той самий
   колір на кількох об'єктах, та сама цифра в коді)? Якщо об'єкти вибирають «без
   повернення» (кожен використовують щонайбільше раз) — повторів немає.

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

| | **без повторів** | **з повтореннями** |
|---|:--:|:--:|
| **порядок важливий** | $A_n^{k} = \dfrac{n!}{(n-k)!}$   (при $k=n$: $P_n = n!$) | $\overline{A}_n^{k} = n^{k}$ |
| **порядок неважливий** | $C_n^{k} = \dfrac{n!}{k!\,(n-k)!}$ | $\overline{C}_n^{k} = C_{n+k-1}^{\,k}$ |

![Схема вибору формули за двома запитаннями: порядок? повтори?](img/p5_decision.png)

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

![Порівняння перестановок, розміщень і сполучень на множині {1,2,3}](img/p5_compare.png)

> **Зауваження (та сама задача — різні типи).** Візьмемо 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. **Перевірити** здоровим глуздом: чи не переплутано «важливий/неважливий порядок»,
   чи не полічено той самий результат двічі.