Основы комбинаторики

Комбинаторика отвечает на вопрос «сколькими способами?»: сколько можно составить чисел, выбрать групп, получить расстановок. На этом подсчёте держится и теория вероятностей. Главная трудность — понять не формулу, а какую формулу выбрать: важен ли порядок, есть ли повторения?

§1. Правила суммы и произведения

• Правило произведения («и»): если выбор делается по этапам — первый этап m способами, второй n способами, — всего m·n способов.
• Правило суммы («или»): если объект берётся либо из первой группы (m способов), либо из второй (n способов) и группы не пересекаются — m + n способов.

Эти два правила лежат в основе всех формул.

Пример

Сколько существует трёхзначных чисел с различными цифрами?

1. Разряд сотен: 0 быть не может — 9 способов.
2. Разряд десятков: 0 можно, но первая цифра не повторяется — 9 способов.
3. Разряд единиц: оставшиеся 8 цифр.
4. 9·9·8 = 648.

Если цифры могут повторяться: четырёхзначных чисел из цифр 1, 2, 3, 4, 5 будет 5⁴ = 625.

§2. Перестановки

Число способов расставить в ряд n различных элементов:

Почему? На первое место n вариантов, на второе n − 1, …, на последнее 1 — правило произведения.
Перестановки с повторениями: если среди элементов есть одинаковые, их взаимная перестановка не даёт нового порядка:

Например, из букв слова МАМА получается 4!/(2!·2!) = 6 различных «слов».
По кругу n человек рассаживаются (n − 1)! способами (повороты считаются одинаковыми).

Пример

На полку ставят 5 различных книг, причём две определённые должны стоять рядом. Сколько способов?

1. Считаем две книги одним «блоком»: 4 объекта → 4! = 24.
2. Внутри блока книги стоят 2! = 2 способами.
3. 24·2 = 48.

§3. Размещения и сочетания

Выбираем k элементов из n.

Почему делим на k!? Каждую группу можно записать k! способами, а в сочетаниях все они считаются одной.
Как различать: если у выбранных разные «роли» или «места» (председатель, заместитель; позиции цифр) — A; если выбирается просто «набор» (команда, группа, рукопожатия) — C.

Пример

Сколькими способами из 10 учеников можно выбрать: а) группу из 3 человек; б) председателя, заместителя и секретаря?

1. а) Порядок не важен: C₁₀³ = 10·9·8/6 = 120.
2. б) Должности различны: A₁₀³ = 10·9·8 = 720.

Пример

Сколько диагоналей у десятиугольника?

1. Отрезков, соединяющих две вершины: C₁₀² = 45.
2. Из них 10 — стороны: 45 − 10 = 35.

Общая формула: n(n − 3)/2.

§4. Составной выбор и «хотя бы один»

Если выбор делается из нескольких групп независимо — перемножаем. При условии «хотя бы один» удобно вычесть противоположный случай.

Пример

Сколькими способами из 6 юношей и 5 девушек можно составить комиссию из 3 юношей и 2 девушек?

1. C₆³ = 20, C₅² = 10.
2. 20·10 = 200.

Пример

Из тех же 11 человек выбирают 3, среди которых должна быть хотя бы одна девушка.

1. Всего способов: C₁₁³ = 165.
2. Только юноши: C₆³ = 20.
3. 165 − 20 = 145.

§5. Бином Ньютона

• Коэффициенты — строка треугольника Паскаля; их сумма 2ⁿ.
• Сумма коэффициентов любого многочлена — его значение при x = 1.

Пример

Найдите коэффициент при x³ в разложении (2x − 1)⁵.

1. Общий член: C₅ᵏ(2x)⁵⁻ᵏ(−1)ᵏ.
2. 5 − k = 3 → k = 2.
3. C₅²·2³·(−1)² = 10·8 = 80.

Пример

Найдите свободный член (не содержащий x) в разложении (x + 1/x)⁶.

1. Общий член: C₆ᵏ x⁶⁻ᵏ (1/x)ᵏ = C₆ᵏ x⁶⁻²ᵏ.
2. Для свободного члена степень равна нулю: 6 − 2k = 0 → k = 3.
3. C₆³ = 20. Заодно сумма коэффициентов (при x = 1): 2⁶ = 64.

§6. Размещения и сочетания с повторениями

Предыдущие формулы опирались на то, что элементы не повторяются. Но в задачах про PIN-код, номер телефона или автомобильный номер одна и та же цифра может использоваться многократно. Тогда число вариантов для каждой позиции не меняется, и правило произведения сразу даёт формулу.

Например, четырёхзначных PIN-кодов из цифр от 0 до 9 ровно 10⁴ = 10 000, потому что на каждую позицию можно поставить любую из 10 цифр.
Встречаются и выборы, в которых порядок не важен, но один вид можно брать несколько раз: купить 3 порции мороженого из 4 сортов (один сорт можно взять дважды). Такие выборки называются сочетаниями с повторениями:

Идея формулы: составляем ряд из k «звёздочек» (выбранные предметы) и n − 1 «перегородок» между видами; достаточно выбрать для звёздочек k мест из n + k − 1. Например, 3 порции из 4 сортов: C(6, 3) = 20 способов.
Чтобы выбрать формулу, ответьте на два вопроса: 1) важен ли порядок? 2) разрешены ли повторения? Эти два ответа определяют один из четырёх случаев — Aₙᵏ, Cₙᵏ, nᵏ или C(n + k − 1, k).

Пример

Четырёхзначный PIN-код составляется из цифр 0–9. Во скольких кодах хотя бы одна цифра повторяется?

1. Все коды (повторения разрешены, порядок важен): 10⁴ = 10 000.
2. Коды без повторяющихся цифр: A₁₀⁴ = 10·9·8·7 = 5040.
3. «Хотя бы один повтор» — противоположное событие: 10 000 − 5040 = 4960.

Проверьте себя

1. Вычислите 6!/4!.

2. Сколько двузначных чисел с неповторяющимися цифрами можно составить из 1, 2, 3, 4, 5?

3. Сколькими способами можно выбрать 2 блюда из 7?

4. Сколько различных «слов» можно составить из букв слова АНАНАС?

5. Коэффициент при x² в разложении (1 + x)⁸.

6. Найдите n, если Cₙ² = 15.

7. Сколько трёхзначных чисел можно составить из цифр 0, 1, 2, 3 (цифры могут повторяться)?

8. Нужно взять 2 пирожных из 5 видов (один вид можно взять дважды). Сколько способов?

Типичные ошибки

• Выбирать формулу, не решив, важен ли порядок (C вместо A или наоборот).
• Забывать, что первая цифра числа не может быть 0.
• Забывать, что 0! = 1.
• Писать n! при наличии одинаковых элементов.
• Считать «хотя бы один» напрямую и учитывать некоторые случаи дважды.
• Терять знак (−1)ᵏ в члене бинома с отрицательным вторым слагаемым.
• Применять Aₙᵏ или Cₙᵏ там, где повторения разрешены: если на каждую позицию можно поставить любой из n вариантов, ответ nᵏ.