Часто нужны не сами комбинации, а их количество: «Сколько вариантов существует?», «Сколькими способами это можно сделать?». Например, 7 команд играют турнир в один круг — каждая с каждой по разу. Сколько будет игр? Запишем игры в таблицу: команда сама с собой не играет (прочерк), а каждую игру пишем один раз, меньший номер первым:
| № | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 1 | — | ||||||
| 2 | 1–2 | — | |||||
| 3 | 1–3 | 2–3 | — | ||||
| 4 | 1–4 | 2–4 | 3–4 | — | |||
| 5 | 1–5 | 2–5 | 3–5 | 4–5 | — | ||
| 6 | 1–6 | 2–6 | 3–6 | 4–6 | 5–6 | — | |
| 7 | 1–7 | 2–7 | 3–7 | 4–7 | 5–7 | 6–7 | — |
Игр 6 + 5 + 4 + 3 + 2 + 1 = 21. Чем больше команд, тем труднее выписывать все пары, поэтому полезно иметь общие правила подсчёта.
Определение. Комбинаторика — раздел математики, изучающий способы подсчёта количества комбинаций, составленных из элементов конечных множеств по заданным правилам.
Пример 1. У Димы 4 рубашки и 3 галстука. Сколько у него пар «рубашка + галстук»? К каждой из 4 рубашек подходит любой из 3 галстуков: на «дереве» от каждой рубашки идут 3 ветки, всего веток 4 · 3 = 12.
Пример 2. Сколько двузначных чисел, у которых первая цифра чётная, а вторая больше 5? Первая цифра — 2, 4, 6 или 8; при любой из них вторая — 6, 7, 8 или 9: 4 · 4 = 16 чисел.
Вывод. Если первый элемент пары можно выбрать A способами и при каждом из них второй элемент можно выбрать B способами, то пару можно выбрать A · B способами.
Пример 3. Забор красят одним из 3 цветов, калитку — одним из 2 других цветов, крышу беседки — одним из 5 цветов. Пар «забор + калитка» 3 · 2 = 6, и к каждой паре — 5 вариантов крыши: 6 · 5 = 3 · 2 · 5 = 30.
Правило произведения. Если элемент a₁ можно выбрать A₁ способами, элемент a₂ — A₂ способами, …, элемент a_n — A_n способами и выбор каждого элемента не зависит от того, как выбраны остальные, то набор (a₁; a₂; …; a_n) можно выбрать A₁ · A₂ · … · A_n способами.
Пример 4. Пары команд турнира: первая команда — любая из 7, вторая — любая из 6 оставшихся, 7 · 6 = 42. Но так каждая игра посчитана дважды (как пара «1–2» и как пара «2–1»), поэтому игр (7 · 6)/2 = 21. Для n команд игр (n(n - 1))/2, для 12 команд — 66.