# Практична робота 5 — Основи комбінаторики

> П'яте практичне заняття курсу **«Основи дискретної математики»**. Працюючи
> **самостійно за варіантом**, ви вчитеся **лічити** кількість способів зробити
> вибір: розпізнавати **перестановки**, **розміщення** та **сполучення**,
> застосовувати **правило суми** й **правило добутку** та вибірки **з повтореннями**.
> Це комбінаторний фундамент, на якому далі будується класична **теорія
> ймовірностей**.

## Стисло

| | |
|---|---|
| **Тема** | Правила суми й добутку; перестановки $P_n=n!$; розміщення $A_n^{k}$; сполучення $C_n^{k}$; вибірки з повтореннями ($n^{k}$, $\overline{C}_n^{k}$); розпізнавання типу задачі |
| **Передумова** | [Лекція 9 — Теорія ймовірностей](../../Lectures/ODM-L09.md) (комбінаторика; класичне означення ймовірності) |
| **Формат** | Індивідуальне **домашнє завдання за варіантом** — без аудиторного розбору |
| **Результат** | Оформлені підрахунки до **трьох** задач (по одній із кожного блоку [3task.md](3task.md)) із зазначенням типу вибірки та формули |

## Зміст

| № | Частина | Файл |
|:--:|---|---|
| 1 | Мета роботи | [1purpose.md](1purpose.md) |
| 2 | Методичні вказівки (самодостатня теорія + приклади методу) | [2method.md](2method.md) |
| 3 | **Завдання за варіантами** (домашнє, без розв'язків) | [3task.md](3task.md) |
| 6 | Контрольні запитання | [6questions.md](6questions.md) |

## Домовленості

- **Мова** — уся робота українською.
- **Домашнє завдання за варіантом.** Це **індивідуальна** робота: студент визначає
  свій варіант за формулою $v = N \bmod 10 + 1$ (де $N$ — номер за списком) і виконує
  **лише свій** варіант у кожному з трьох блоків. Тому **розв'язків не наведено** —
  файли містять лише умови завдань.
- **Позначення фіксовані й самодостатні.** $n!$ — факторіал; $P_n = n!$ —
  **перестановки**; $A_n^{k} = \dfrac{n!}{(n-k)!}$ — **розміщення**;
  $C_n^{k} = \dfrac{n!}{k!\,(n-k)!}$ — **сполучення**; риска над символом
  ($\overline{A}_n^{k} = n^{k}$, $\overline{C}_n^{k} = C_{n+k-1}^{k}$) означає
  «з повтореннями». Усі означення — у [2method.md](2method.md).
- **Оформлення відповіді.** До кожної задачі зазначають **тип** (перестановка /
  розміщення / сполучення, з повторами чи без), **формулу з підстановкою** та
  обчислення; дуже великі числа дозволено лишати добутком або факторіалом.
- **Самодостатність.** Уся теорія та по одному **демонстраційному прикладу кожного
  типу** (на інших даних, ніж у варіантах) наведені в [2method.md](2method.md), тож
  роботу можна виконати без сторонніх джерел.

## Підсумок

Комбінаторика відповідає на запитання **«скількома способами?»**, і майже кожна така
задача зводиться до двох ідей. Перша — **дві правила лічби**: несумісні випадки
(«або») **додають**, послідовні кроки («і») **перемножують**. Друга — **два
запитання**, що обирають формулу: *чи важливий порядок?* і *чи дозволені повтори?*.
Їхні чотири відповіді дають чотири схеми — розміщення $A_n^{k}$ (а при $k=n$ —
перестановки $P_n$), кортежі $n^{k}$, сполучення $C_n^{k}$ і сполучення з
повтореннями $\overline{C}_n^{k}$. Навчившись правильно ставити ці два запитання, ви
зведете кожну з тридцяти задач роботи до однієї короткої формули — і водночас
підготуєтеся до класичної ймовірності, де відповідь є відношенням двох таких
підрахунків.