"Алгебра", Никольский С.М., Потапов М.К., Решетников Н.Н. и др.
Комбинаторика помогает быстро находить число возможных вариантов, не перебирая их по одному. Она используется при выборе команд, составлении чисел, расписаний, паролей и маршрутов. Главные инструменты темы — правило сложения для взаимоисключающих вариантов и правило умножения для последовательных действий. Также нужно различать перестановки, размещения и сочетания: решающим признаком служит то, учитывается ли порядок выбранных объектов.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Комбинаторика — раздел математики о подсчёте числа возможных вариантов выбора и расположения объектов. Объектами могут быть цифры, ученики, книги или места. Комбинаторные правила позволяют находить ответ быстро, не перечисляя все варианты.
Правило сложения означает: если способы взаимоисключающие, их количества складывают. Взаимоисключающие варианты нельзя выполнить одновременно в одном выборе. Например, выбор первого или второго блюда считают сложением числа первых и вторых блюд.
Правило умножения применяют, когда действие состоит из нескольких последовательных этапов. Если первый этап можно выполнить несколькими способами, а каждому его результату соответствует определённое число способов второго этапа, количества перемножают. Так считают, например, варианты составления числа по отдельным разрядам.
Факториал числа n — произведение всех натуральных чисел от 1 до n: n! = 1 · 2 · … · n, причём 0! = 1. Знак «!» показывает, что нужно взять факториал числа. Факториалы сокращают запись формул перестановок, размещений и сочетаний.
Правило сложения подходит, когда выбирают ровно один вариант из разных, не пересекающихся групп. Например, блюдо не может одновременно быть выбранным первым и вторым, поэтому каждый вариант попадает ровно в одну группу. При последовательном выполнении действий один результат образуется соединением выбора на первом и втором этапах, поэтому для каждого варианта первого этапа нужно посчитать все варианты второго и выполнить умножение.
Перестановка возникает, когда последовательно размещают все n имеющихся элементов. На первое место можно поставить n элементов, на второе — n − 1 оставшийся элемент, затем n − 2 и так далее до последнего места. По правилу умножения получаем n · (n − 1) · … · 1 = n!, поэтому число перестановок равно n!.
Размещение без повторений — это выбор k элементов из n с учётом порядка. На первое место можно выбрать n элементов, на второе — n − 1, а на каждом следующем месте число доступных элементов уменьшается на единицу. Последний множитель равен n − k + 1, поэтому Aₙᵏ = n · (n − 1) · … · (n − k + 1) = n!/(n − k)!.
В сочетании порядок выбранных элементов не учитывается. Если сначала посчитать размещения, то один и тот же набор из k элементов окажется посчитан k! раз — по одному разу для каждой перестановки внутри набора. Поэтому размещения делят на k!, и получают Cₙᵏ = Aₙᵏ/k! = n!/(k!(n − k)!).
Чтобы выбрать нужную формулу, спросите себя, создаёт ли перестановка выбранных объектов новый результат. Если меняются должности, места, цифры в числе или порядок выступления, порядок учитывается. Если меняется только состав команды, группы или набора, порядок не учитывается; отдельно проверьте, разрешены ли повторения.
| Вид выборки | Что выбирается | Учитывается ли порядок | Формула | Пример |
|---|---|---|---|---|
| Сочетание без повторений | k элементов из n | Нет | Cₙᵏ = n!/(k!(n − k)!) | Выбор команды из нескольких участников |
Сначала определите, выбирается ли часть элементов или используются все, а затем выясните роль порядка. Для выбора команды подходит сочетание: перестановка участников не меняет состав команды. Если же участников расставляют по местам или назначают на разные должности, порядок уже нужно учитывать.
В столовой можно выбрать одно из 4 первых блюд или одно из 5 вторых блюд. Требуется выбрать только одно блюдо, поэтому одновременно выбрать первое и второе по условию нельзя. Следовательно, случаи являются взаимоисключающими.
Ответ: 9 вариантов выбора одного блюда. Умножение здесь не подходит, потому что не выбирают пару из двух блюд, а выбирают один вариант из двух групп.
Нужно составить трёхзначное число из цифр 1, 2, 3, 4, 5 без повторений. Порядок цифр важен: числа 123 и 321 различны. Выбор выполняется последовательно по разрядам.
Ответ: 60 различных трёхзначных чисел. Условие «без повторений» уменьшает число доступных цифр на каждом следующем шаге.
Из 10 учеников выбирают команду из 4 человек и назначают капитана. Сначала важен только состав команды, поэтому выбираем сочетание. Затем внутри уже выбранной команды выделяем одного капитана.
Ответ: 840 способов. Нельзя сразу считать всех четырёх учеников размещением, потому что ряд участников без должностей не задаёт новый состав команды.
Правило сложения используют вместо умножения при последовательном выборе нескольких объектов. Так происходит, когда этапы выбора ошибочно воспринимают как альтернативы. Проверьте себя вопросом: получается один объект из нескольких этапов или выбирается один вариант из разных групп?
Выбор команды иногда считают размещением и получают разные варианты при перестановке участников. Ошибка возникает из-за смешения состава команды и порядка её записи. Если должностей и мест нет, поменяйте участников местами и проверьте, изменился ли результат.
При условии «без повторений» иногда снова выбирают уже использованный элемент. Причина — применение постоянного числа вариантов на каждом этапе. После каждого выбора пересчитывайте, сколько элементов осталось доступно.
Факториалы могут неправильно сокращать или подставлять в формулу без проверки смысла задачи. Чаще всего сначала не выясняют, важен ли порядок. Запишите, что считается новым вариантом при перестановке объектов, и только потом выбирайте размещение или сочетание.
Для комбинаторики нужны действия с натуральными числами, произведениями, дробями и степенями. Также важно понимать смысл умножения как объединения последовательных выборов и деления как обратного действия.
Комбинаторные формулы применяются при изучении вероятности и статистики. Число возможных исходов помогает находить вероятность события, а подсчёт данных — анализировать результаты наблюдений.
Тема встречается в задачах о паролях, расписаниях, маршрутах, командах и распределении мест. Она помогает моделировать реальные ситуации и находить число вариантов без полного перебора.
Как понять, складывать количества вариантов или перемножать?
Складывают, если нужно выбрать один вариант из взаимоисключающих групп: например, первое или второе блюдо. Перемножают, если выбор состоит из нескольких последовательных этапов: например, сначала цифру сотен, затем десятков и единиц.
Чем размещение отличается от сочетания?
В размещении выбирают часть элементов и учитывают порядок их расположения. В сочетании выбирают часть элементов, но перестановка выбранных объектов не создаёт нового варианта.
Почему в формуле сочетаний появляется множитель k!?
Каждый набор из k элементов при подсчёте размещений учитывается k! раз — по одному разу для каждой его перестановки. Поэтому число размещений делят на k!, чтобы оставить один вариант для каждого набора.
Что означает запись 0! и почему 0! = 1?
Запись 0! означает факториал нуля. Значение 0! принимают равным 1, чтобы формулы факториалов и сочетаний сохраняли правильный вид, например Cₙ⁰ = 1.
Как определить, можно ли использовать один и тот же элемент несколько раз?
Нужно внимательно искать в условии слова «без повторений», «различные» или прямой запрет повторного выбора. Если запрета нет, повторение может быть разрешено, но это зависит от смысла задачи и выбранной модели подсчёта.
§ 13. Комбинаторика
