Отец даёт двухлетней дочери
ложку и спрашивает:
— Сколько у тебя ложек?
— Одна.
Даёт другую:
— Теперь сколько?
— Две.
Даёт третью.
— Теперь сколько?
— Много.
— Нет, ты скажи.
Девочка с преувеличенным выражением
брезгливости отодвигает от
себя третью ложку:
— Возьми, она грязная!
К. Чуковский, «От двух до пяти»
Комбинаторика — это раздел математики, в котором изучают, сколько комбинаций, подчинённых тем или иным условиям, можно составить из данных объектов. Прежде чем переходить к общим принципам, рассмотрим несколько примеров. Попробуйте сначала сами ответить на поставленные вопросы, а потом обязательно прочитайте решения.
1) Сколько существует трёхзначных чисел?
Решение |
Решение |
3) Сколькими способами можно расположить на шахматной доске белую и чёрную ладьи, чтобы они не били одна другую?
Решение |
4) Сколькими способами можно выложить в ряд красный, жёлтый и зелёный шарики?
Решение |
5) Сколькими способами можно пройти из левой нижней клетки изображённого на рисунке квадрата 9×9 в правую верхнюю, ни разу не побывав ни на одной закрашенной клетке и двигаясь только вверх или вправо?
Решение |
6) Сколько слов (не обязательно осмысленных) можно получить, переставляя буквы слова МАМА?
Решение |
7) Сколько среди первых 1000 натуральных чисел таких, которые не кратны ни 2, ни 5?
Решение |
8) Сколько сторон и диагоналей в выпуклом пятнадцатиугольнике?
Решение |
Мы разобрали уже восемь разных комбинаторных задач. Пора перейти к более общим понятиям.
Два элемента 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)!).
К сожалению, ни для точного определения, ни для свойств чисел сочетаний здесь места не нашлось. Но для первого знакомства с комбинаторикой сказанного и так предостаточно. Вернёмся лучше к нашим обычным задачам, оставив теорию на будущее.