Комбинаторика — раздел математики, который изучает, сколькими способами можно выбрать и расположить элементы конечного множества: переставить их, выбрать некоторые из них, составить из них комбинации с заданными свойствами. Такие задачи называют задачами подсчёта числа вариантов.
Пример 1. Сколькими способами четверо друзей — Аня, Боря, Вера и Гена — могут встать в очередь в кассу?
Сначала поставим первой Аню и построим дерево возможностей. Вторым может стоять Б, В или Г — три ветки. Если вторым стоит Б, то третьим — В или Г, а последним — тот, кто остался; так же, если вторым стоит В или Г. Получается 3 · 2 = 6 очередей с Аней впереди: АБВГ, АБГВ, АВБГ, АВГБ, АГБВ, АГВБ. Первым может стоять любой из четверых, и для каждого из них тоже получится 6 очередей. Всего 6 · 4 = 24 способа.
Метод систематического перебора (комбинации из различных элементов):
- закрепить на первом месте один из элементов;
- для этого случая подсчитать число вариантов с помощью дерева возможностей, таблицы или списка;
- если на первом месте может стоять любой элемент, умножить полученное число на количество элементов;
- если на элементы наложены ограничения, подсчитать варианты отдельно для элементов с разными свойствами и сложить результаты.
Правило произведения. Если первый элемент комбинации можно выбрать m способами и при каждом таком выборе второй элемент — n способами, то пару можно составить m · n способами; для трёх элементов — m · n · k способами и т. д. Например, n различных предметов можно расставить в ряд n · (n - 1) · … · 2 · 1 способами: пять книг — 5 · 4 · 3 · 2 · 1 = 120 способами.
Пример 2 (перебор с ограничениями). В столовой на первое можно взять суп или салат, на второе — котлету, рыбу или плов, на третье — чай или компот. Компот к рыбе не подают, а суп не берут вместе с пловом. Сколько различных обедов из трёх блюд можно составить?
Дерево возможностей: суп — котлета (чай или компот), рыба (только чай): 3 обеда; салат — котлета (чай или компот), рыба (только чай), плов (чай или компот): 5 обедов. Всего 3 + 5 = 8 обедов.
Пример 3 (магический квадрат). Квадрат 3 × 3 называют магическим, если суммы чисел во всех его строках, столбцах и обеих диагоналях одинаковы. Сколькими способами можно расставить в нём числа 5, 6, …, 13?
Сумма всех чисел 81, значит, сумма в каждой строке 81 : 3 = 27. Троек различных чисел с суммой 27 ровно восемь — столько же, сколько строк, столбцов и диагоналей (3 + 3 + 2), поэтому каждая тройка занимает свою линию. Число в центре входит в четыре линии, в углу — в три, остальные — в две. В четыре тройки входит только 9 — оно стоит в центре; в три — 6, 8, 10, 12 — они стоят в углах. В левый верхний угол можно поставить любое из этих четырёх чисел, тогда противоположный угол определён (диагональ через 9), а в правый верхний угол — одно из двух оставшихся. Остальные клетки заполняются однозначно, и получается 4 · 2 = 8 магических квадратов.