Комбинаторика

Отец даёт двухлетней дочери
ложку и спрашивает:
— Сколько у тебя ложек?
— Одна.
Даёт другую:
— Теперь сколько?
— Две.
Даёт третью.
— Теперь сколько?
— Много.
— Нет, ты скажи.
Девочка с преувеличенным выражением
брезгливости отодвигает от себя третью ложку:
— Возьми, она грязная!

Комбинаторика — это раздел математики, в котором изучают, сколько комбинаций, подчинённых тем или иным условиям, можно составить из данных объектов. Прежде чем переходить к общим принципам, рассмотрим несколько примеров. Попробуйте сначала сами ответить на поставленные вопросы, а потом обязательно прочитайте решения.

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

Решение

Решение. Самое большое трёхзначное число — это 999. Самое большое двузначное — 99. Поэтому существует 999 - 99 = 900 трёхзначных чисел. Тот же ответ можно получить и другим способом. Вообразите, что мы пишем, цифра за цифрой, трёхзначное число. Сначала напишем любую из девяти цифр 1, 2,..., 9 в разряд сотен. Затем любую из десяти цифр — в разряд десятков; наконец, какую-нибудь (любую) цифру — в разряд единиц. Ответ: 9 · 10 · 10 = 900.

2) Сколько способов проехать из A в C, если система дорог такова, как показано на рисунке?

Решение

Решение. Прежде чем попасть из A в C(?), надо любым из трёх возможных способов попасть из A в B, а затем — любым из пяти способов из B в C. Общее количество способов равно 3 · 5 = 15.

3) Сколькими способами можно расположить на шахматной доске белую и чёрную ладьи, чтобы они не били одна другую?

Решение

Решение. Сначала поставим на любую из 64 клеток доски белую ладью. Для чёрной ладьи останется 49 полей. Ответ: 64 · 49 = 3136. Заметьте: мы перемножаем числа 64 и 49, а не складываем их. Одна из стандартных ошибок, которую делает начинающие, состоит в том, что они путают, когда надо складывать, а когда умножать. Между тем всё просто: сумма m + n есть количество элементов объединения двух непересекающихся множеств, одно из которых состоит из m, а другое — из n элементов. А произведение mn — это количество пар вида (x;y), где x может быть любым из m элементов некоторого множества (например, это может быть множество 64 возможных полей для белой ладьи), а y, при каждом фиксированном x, может быть любым из некоторых n элементов (например, y — одно из 49 возможных полей для чёрной ладьи). Иногда необходимо использовать и сумму, и произведение: например, количество путей, ведущих на рисунке из точки K в точку M, равно 2 · 2 + 3 · 3 = 13.

4) Сколькими способами можно выложить в ряд красный, жёлтый и зелёный шарики?

Решение

Решение. Вот все 6 способов: к ж з; к з ж; ж к з; ж з к; з к ж; з ж к.

5) Сколькими способами можно пройти из левой нижней клетки изображённого на рисунке квадрата 9×9 в правую верхнюю, ни разу не побывав ни на одной закрашенной клетке и двигаясь только вверх или вправо?

Решение

Решение. Нет ни сил, ни желания рисовать все варианты: это пример не так прост, как предыдущий! Что же делать? Давайте поставим перед собой более скромную цель: найдём количество путей из левой нижней клетки не в правую верхнюю, а, например, в клетку A. Очевидно, таких путей два. Столько же путей ведут в точку B. Теперь легко понять, что в клетку C можно пройти четырьмя способами (два из них ведут через A, а два — через B). Таким образом, клетку за клеткой, мы можем заполнять доску, используя правило суммы: если в некоторую клетку Z можно попасть справа из клетки X и снизу — и Y, то количество способов попасть в клетку Z есть сумма количеств способов попасть в X и Y. Например, в клетку D можно попасть 17 + 7 = 24 способами. Так потихонечку и заполним всю доску. Ответ: 678.

6) Сколько слов (не обязательно осмысленных) можно получить, переставляя буквы слова МАМА?

Решение

Решение. МАМА, МААМ, ММАА, АМАМ, АММА и ААММ — всего 6 способов.

7) Сколько среди первых 1000 натуральных чисел таких, которые не кратны ни 2, ни 5?

Решение

Решение. Как известно, число не кратно ни 2, ни 5, если его последняя цифра — это одна из четырёх цифр 1, 3, 7, 9. Значит, в каждом десятке ровно четыре интересующих нас числа, а всего таких чисел 400. Есть и другой способ. Рассмотрим множество U = {1,2,3,...,1000} и два его подмножества: A = {2,4,6,...,1000} и B = {5,10,15,...,1000}. Нас интересует число элементов множества U, не принадлежащих ни A, ни B. Легко видеть, что ответ |U| - |A| - |B| (где |U|, |A| и |B| — количества элементов множеств U, A и B соответственно) неправильный. Дело в том, что элементы, входящие в оба множества A и B (то есть числа, оканчивающиеся цифрой 0), были выброшены дважды, хотя следовало их выбросить только один раз. А вот правильный ответ: |U| – |A| – |B| + |AЗB|, где AЗB — пересечение множеств A и B. Давайте проверим эту формулу: 1000 - 500 - 200 + 100 = 400.

8) Сколько сторон и диагоналей в выпуклом пятнадцатиугольнике?

Решение

Решение. Можно, конечно, нарисовать 15-угольник на большом листе бумаги, посчитать диагонали и прибавить к ответу 15 — число сторон. Но лучше найти общую формулу для числа сторон и диагоналей n-угольника. Очевидно, в треугольнике 3 стороны и ни одной диагонали; в четырёхугольнике 4 стороны и 2 диагонали; в пятиугольнике 5 сторон и 5 диагоналей. Чуть сложнее увидеть, что у шестиугольника 6 сторон и 9 диагоналей. Вообще, из каждой вершины n-угольника выходят n – 1 отрезков (две стороны и n – 3 диагонали). Умножив n на (n – 1) и не забыв разделить на 2 (ибо у каждого отрезка два конца), получим ответ: число сторон и диагоналей n-угольника равно n(n – 1)/2.   (*) В частности, у 15-угольника всего 15 · 14 / 2 = 105 сторон и диагоналей. Любитель индукции может доказать формулу (*) и другим способом. При n = 3 формула (*) верна. Очевидно, (n + 1)-угольник можно получить из n-угольника добавлением одной новой вершины. Из этой вершины выходят отрезки — стороны и диагонали — во все остальные n вершин. Значит, (n + 1)-угольник имеет ровно на n больше сторон и диагоналей, чем n-угольник. Поскольку n(n – 1)/2 + n = (n2 – n + 2n)/2 = (n+1)n/2, мы видим, как преобразуется формула при переходе от n к n + 1. Точнее говоря, если формула (*) давала верное значение для n-угольника, то и для (n + 1)-угольника всё будет правильно. Мы помним, что при n = 3 формула верна. Значит, по индукции, она верна при любом n.

Мы разобрали уже восемь разных комбинаторных задач. Пора перейти к более общим понятиям.

Перестановки. Факториал

Два элемента a и b могут быть выписаны в строчку всего двумя способами: ab и ba. Для трёх элементов, как мы знаем из четвёртого примера, существует 6 вариантов. Нетрудно посчитать и число перестановок множества из 4 элементов:

1234, 1243, 1324, 1342, 1423, 1432,
2134, 2143, 2314, 2341, 2413, 2431,
3124, 3142, 3214, 3241, 3412, 3421,
4123, 4132, 4213, 4231, 4312, 4321.

Всего 24 перестановки, расположенные в 4 столбца по 6 перестановок в каждом. Очевидно, перестановки на 5 элементах можно расположить в 5 столбцов, по 24 в каждом. Значит, всего существует 5 · 24 = 120 таких перестановок.

Для числа перестановок n элементов есть обозначение: n! (читаем: «эн факториал»). Факториал равен произведению всех натуральных чисел от 1 до n. Например,

4! = 1 · 2 · 3 · 4.

Функция n! возрастает очень быстро. Так, 1! = 1, 2! = 2, 3! = 6, ..., 10! = 3 628 800. Факториалы возникают в комбинаторике очень часто. Поэтому принято считать, что если ответ выражен через факториалы, то всё сделано. (Этому в немалой степени способствует открытая в 1730 году английским математиком Дж. Стирлингом формула для приближённого вычисления:

n! ~ (2pn)^1/2nⁿ/eⁿ.

Относительная ошибка при пользовании этой формулой очень невелика и стремится к нулю при увеличении числа n. Что такое e и почему верна формула Стирлинга, младшекласснику объяснить очень трудно.)

Главное свойство факториала очевидно из определения:

(n + 1)! = (n + 1) · n!.

Подставим в эту формулу n = 0. Получим: 1! = 1 · 0!, откуда 0! = 1. И действительно, во многих формулах для единообразной записи очень удобно пользоваться обозначением 0! = 1. А вот определить (–1)! никак нельзя: равенство 0! = 0 · (–1)! невозможно ни при каком значении (–1)!.

Размещения

Следующее важное понятие комбинаторики — размещение. Давайте рассмотрим такую ситуацию: в классе, в котором 25 учеников, нужно выбрать старосту, его заместителя и помощника заместителя. Сколькими способами это можно сделать?

Очевидно, сначала 25 способами можно выбрать любого ученика в старосты. Затем из 24 оставшихся — заместителя старосты, а после этого любой из 23 оставшихся может оказаться помощником заместителя. По правилу произведения, всего имеем A₂₅³=25·24·23 вариантов.

Вообще, через A_n^k (читаем: «а из эн по ка») обозначают число способов выбрать из данных n элементов сначала первый элемент, потом второй, третий,..., k-й. Вычисляют его по формуле

A_n^k = n (n – 1) ... (n – k + 1).

Заметьте: в правой части ровно k множителей, и последний из них равен n – k + 1, а вовсе не n – k, как могло показаться на первый взгляд. Формулу можно записать и через факториалы:

A_n^k = n!/(n – k)!.

Числа сочетаний

Представьте себе, что в классе из 25 человек нужно выбрать не старосту, его заместителя и помощника его заместителя, а тройку начальников, которые, обладая равными правами, будут судить, не выясняя, кто из троих главный, кто менее главный, а кто так себе. Тогда способов будет не A₂₅³, а в 6 раз меньше. (Подумайте об этом хорошенько! Здесь 6 = 3! — количество способов ранжировать трёх начальников, то есть количество всех перестановок на множестве из 3 элементов.)

Вообще, очень важные для комбинаторики и теории вероятностей числа сочетаний C_n^k (читаем: «число сочетаний из эн по ка» или «це из эн по ка») можно вычислить по формуле C_n^k=A_n^k/k!=n!/(k!(n-k)!).

К сожалению, ни для точного определения, ни для свойств чисел сочетаний здесь места не нашлось. Но для первого знакомства с комбинаторикой сказанного и так предостаточно. Вернёмся лучше к нашим обычным задачам, оставив теорию на будущее.