§ 2. Основные законы комбинаторики

Определения и обозначения

Правило суммы: если два несовместных варианта действия можно выполнить соответственно m и n способами, то выбрать один из них можно m + n способами. Несовместные варианты не дают одного и того же результата. Это правило нужно, когда выбор делают из разных непересекающихся групп.

Правило произведения: если действие состоит из двух последовательных этапов, выполняемых соответственно m и n способами, то всё действие можно выполнить m · n способами. Здесь необходимо выполнить оба этапа, а каждый вариант первого сочетается с каждым допустимым вариантом второго. Правило позволяет считать целое действие по отдельным шагам.

Перестановка — упорядочение всех элементов конечного множества; число перестановок из n элементов обозначают Pₙ и вычисляют как n!. Например, перестановки различаются, если два элемента поменяли местами. Это понятие используют, когда нужно разместить все объекты в определённом порядке.

Факториал числа n — произведение всех натуральных чисел от 1 до n: n! = 1 · 2 · … · n. По определению 0! = 1. Факториал кратко записывает произведение, возникающее при подсчёте перестановок, и упрощает формулы.

Как это устроено

Правило суммы применяют, когда результат выбирают из одного из нескольких наборов возможностей. Чтобы сложение было корректным, наборы должны быть непересекающимися: тогда каждый результат попадёт ровно в один случай. Если один результат подходит сразу к двум группам, простое сложение посчитает его дважды. Поэтому сначала проверяют, могут ли случаи пересекаться.

Правило произведения связано с тем, что результат составляется из нескольких частей. Представим, что сначала выбирают один вариант первого этапа, а затем — один вариант второго. Для каждого выбора на первом этапе доступны n вариантов второго, поэтому такие группы по n вариантов повторяются m раз; всего получается m · n. Если число вариантов второго этапа зависит от первого, нужно считать для каждого выбора отдельно или разбить задачу на случаи.

Сложное действие удобнее разложить на этапы и альтернативные пути. Если для результата надо выполнить все этапы, их возможности соединяют правилом произведения. Если же достаточно выбрать один из взаимоисключающих путей, применяют правило суммы. В большой задаче оба закона могут встретиться вместе: внутри каждого пути считают этапы, а затем складывают результаты разных путей.

Перестановки считают последовательным выбором места для каждого элемента. На первое место можно поставить любой из n элементов; после этого для второго остаётся n − 1 элемент, затем n − 2 и так далее до последнего места. По правилу произведения число порядков равно n · (n − 1) · … · 1, то есть Pₙ = n!. Каждый порядок учитывает все элементы ровно один раз.

Условие задачи определяет, что именно считается одним результатом. Если два результата отличаются только порядком, нужно учитывать порядок; если порядок не важен, перестановки не подходят. Также проверяют состав выбранных элементов и пересечения между рассматриваемыми случаями. Эти вопросы помогают выбрать закон подсчёта до того, как появятся вычисления.

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

Сначала найдите в таблице описание действия: выбор между случаями, последовательные шаги или упорядочение всех элементов. Затем проверьте условие применения и только после этого подставляйте числа в формулу. Если в задаче есть несколько частей, для каждой можно определить своё правило.

Разбор задач

Задача 1. В школьном буфете можно выбрать один из 4 видов сока или один из 3 видов воды. Сколькими способами можно выбрать напиток? Здесь выбирают ровно один напиток, а группы соков и воды не пересекаются. Значит, складываем количество вариантов.

1. Определяем случаи: напиток — сок или вода.
2. Считаем, что в первом случае есть 4 варианта, во втором — 3.
3. Применяем правило суммы: 4 + 3 = 7.

Ответ: 7 способов. Проверка смысла проста: каждый из семи напитков может быть выбран отдельно, а одновременный выбор сока и воды не требуется.

Задача 2. Код состоит из одной буквы, выбранной из 5 букв, и одной цифры, выбранной из 6 цифр. Сколько кодов можно составить? Для каждого кода нужны и буква, и цифра, поэтому это два последовательных этапа. Каждая буква может сочетаться с каждой цифрой.

1. На первом этапе выбираем букву: 5 возможностей.
2. На втором этапе выбираем цифру: 6 возможностей для каждой буквы.
3. Перемножаем: 5 · 6 = 30.

Ответ: 30 кодов. Здесь складывать было бы неверно: одной буквы или одной цифры недостаточно, чтобы получить код.

Задача 3. Сколькими способами можно расставить в ряд 5 разных книг, если две определённые книги должны стоять рядом? Рассмотрим эти две книги как один блок: вместе с тремя остальными книгами получаем 4 объекта. После их расстановки нужно учесть, что книги внутри блока можно поменять местами.

1. Объединяем две соседние книги в блок и считаем его одним объектом.
2. Расставляем 4 объекта: это можно сделать 4! = 24 способами.
3. Внутри блока выбираем порядок двух книг: 2 способа. По правилу произведения получаем 24 · 2 = 48.

Ответ: 48 способов. Умножение учитывает все внутренние порядки блока для каждой расстановки объектов.

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

Складывают числа вариантов для последовательных этапов, хотя необходимо выполнить каждый из них. Так ошибаются, когда воспринимают этапы как альтернативы; проверить себя можно вопросом: получится ли результат, если пропустить один шаг? Если нет, этапы соединяют умножением.

Перемножают числа вариантов для альтернативных случаев, хотя выбирают только один случай. Причина ошибки — внимание к нескольким группам вместо вопроса, нужны ли они одновременно. Проверьте, должен ли результат содержать выбор из каждой группы: если выбирают что-то одно, для несовместных случаев используют сложение.

Применяют правило суммы к пересекающимся группам без поправки. Общие варианты тогда учитываются дважды, потому что каждый случай включает их в свой подсчёт. Перед сложением сравните группы и проверьте, может ли один результат оказаться в обеих; если может, разделите случаи или отдельно учтите пересечение.

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

Связь с другими темами

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

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

Что запомнить

• Для выбора одного из несовместных вариантов применяют правило суммы.
• Для последовательного выполнения этапов применяют правило произведения.
• Перед подсчётом нужно определить, что именно считается результатом.
• Пересекающиеся случаи нельзя просто складывать без учёта общих вариантов.
• Число перестановок n различных элементов равно n!.
• По определению 0! = 1.