Комбинаторика
Отец даёт двухлетней дочери
ложку и спрашивает:
— Сколько у тебя ложек?
— Одна.
Даёт другую:
— Теперь сколько?
— Две.
Даёт третью.
— Теперь сколько?
— Много.
— Нет, ты скажи.
Девочка с преувеличенным выражением
брезгливости отодвигает от
себя третью ложку:
— Возьми, она грязная!
К. Чуковский, «От двух до пяти»
Комбинаторика — это раздел математики, в котором изучают,
сколько комбинаций, подчинённых тем или
иным условиям, можно составить из данных объектов.
Прежде чем переходить к общим принципам,
рассмотрим несколько примеров. Попробуйте сначала сами ответить на поставленные вопросы,
а потом обязательно прочитайте решения.
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/2nn/en.
Относительная ошибка при пользовании этой формулой очень невелика и стремится к нулю при увеличении числа 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 оставшихся может оказаться помощником заместителя. По правилу произведения, всего имеем
A253=25·24·23 вариантов.
Вообще, через Ank (читаем: «а из эн по ка») обозначают число способов выбрать из
данных n элементов сначала первый элемент, потом второй,
третий,..., k-й. Вычисляют его по формуле
Ank = n (n – 1) ... (n – k + 1).
Заметьте: в правой части ровно k множителей, и последний из них равен n – k + 1, а вовсе не n – k, как могло показаться на
первый взгляд. Формулу можно записать и через факториалы:
Ank = n!/(n-k)!.
Числа сочетаний
Представьте себе, что в классе из 25 человек нужно выбрать не старосту, его заместителя и помощника его заместителя, а тройку начальников, которые, обладая равными правами, будут управлять и
судить класс, не выясняя, кто из троих главный, кто менее главный, а кто так себе. Тогда способов будет не A253, а в 6 раз меньше. (Подумайте об этом хорошенько! Здесь 6 = 3! — количество способов ранжировать трёх начальников, то есть количество всех перестановок на множестве из 3 элементов.)
Вообще, очень важные для комбинаторики и теории вероятностей числа сочетаний Cnk (читаем: «число сочетаний из эн по ка» или «це из эн по ка») можно вычислить
по формуле Cnk=Ank/k!=n!/(k!(n-k)!).
К сожалению, ни для точного определения, ни для свойств чисел сочетаний здесь места не нашлось. Но для первого знакомства с комбинаторикой сказанного и так предостаточно. Вернёмся лучше к нашим обычным задачам, оставив теорию на будущее.