"Алгебра и начала математического анализа", Колягин Ю.М., Ткачёва М.В. и др.
Правило произведения помогает считать число способов, если действие состоит из нескольких последовательных выборов. Размещение с повторениями — это упорядоченный набор из k элементов, выбранных из n доступных элементов, причём один элемент может встречаться несколько раз. Для такого выбора на каждом месте доступны все n вариантов, поэтому общее число наборов равно n^k. Главное — определить число мест, число доступных элементов, учесть порядок и проверить, разрешены ли повторы.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Правило произведения: если действие состоит из нескольких последовательных этапов, а на каждом этапе есть заданное число вариантов, общее число способов равно произведению этих чисел. Например, при n₁ вариантах первого шага и n₂ вариантах второго получаем n₁ · n₂ способов. Правило нужно, чтобы не перебирать все комбинации вручную.
Размещение с повторениями — это упорядоченный набор из k элементов, выбранных из n различных элементов, причём один элемент можно использовать несколько раз. Слово «упорядоченный» означает, что последовательность выбора имеет значение. Такое понятие применяют при составлении кодов, слов и других последовательностей.
Число размещений с повторениями — количество всех таких упорядоченных наборов. Если имеется n элементов и k мест, это число обозначают как nk. Формула показывает, сколько вариантов получится, когда на каждое место можно поставить любой из доступных элементов.
Рассмотрим два последовательных выбора: сначала выбирается один предмет из n₁ вариантов, затем другой из n₂ вариантов. Для каждого варианта первого шага доступны все n₂ продолжений, поэтому образуется n₂ способов. Так как первых вариантов n₁, одинаковые группы продолжений повторяются n₁ раз, и получается n₁ · n₂ способов.
При большем числе этапов рассуждение не меняется. Сначала нужно отдельно определить, сколько вариантов есть на первом этапе, затем на втором и так далее. Если этапы выполняются все вместе, их варианты перемножаются; складывать их можно было бы только при выборе одного из взаимоисключающих действий.
Размещение с повторениями удобно представлять как заполнение последовательных мест. Первое место образует первый этап выбора, второе — второй, а всего таких этапов k. На каждом месте доступны все n элементов, потому что уже выбранный элемент не запрещается использовать снова.
Поэтому число способов равно произведению n · n · … · n, где множитель n встречается k раз, то есть nk. Порядок важен: последовательности 1, 2, 1 и 2, 1, 1 занимают места по-разному и считаются разными. Повторение разрешено именно потому, что после выбора элемента он остаётся доступным для следующих мест.
Чтобы выбрать подходящую модель, сначала найдите число мест k: это могут быть разряды кода, буквы слова или позиции предметов. Затем определите число доступных элементов n на каждом месте. Наконец, проверьте условие о повторах и ограничения на отдельные позиции: без этого применение nk может дать неверный результат.
| Ситуация | Число вариантов этапа | Число этапов | Общее число способов |
|---|---|---|---|
| Последовательные независимые выборы | n₁, n₂, …, nₖ | k | n₁ · n₂ · … · nₖ |
| Выбор с повторениями из n элементов на k упорядоченных мест | n на каждом месте | k | nk |
Сначала определите, к какой строке относится условие задачи. Если число вариантов меняется от этапа к этапу, используйте произведение n₁ · n₂ · … · nₖ.
Если на каждом из k мест можно независимо выбрать любой из n элементов и повторы разрешены, подходит формула nk. Таблица помогает быстро увидеть, какие данные нужно найти до вычислений.
Ученик выбирает одну из 4 футболок и одну из 3 пар брюк. Комплект составляется из двух последовательно выбранных предметов. Каждый вариант футболки можно сочетать с любой парой брюк.
Ответ: 12 комплектов одежды. Здесь не требуется учитывать порядок предметов, потому что выбираются разные части одного комплекта. Важно лишь, что оба выбора выполняются вместе.
Код состоит из трёх мест, а для каждого места доступны цифры 0, 1, 2, 3. Поскольку это код, первый символ может быть нулём. Повторы разрешены, поэтому после каждого выбора набор доступных цифр остаётся тем же.
Ответ: 64 кода. Например, 001 и 100 считаются разными кодами, поскольку цифры стоят в разном порядке. Ноль исключать не нужно, так как условие говорит о коде, а не о трёхзначном числе.
Нужно составить последовательность из шести букв русского алфавита, используя 33 буквы. Повторения разрешены, значит одна и та же буква может занимать несколько мест. Каждое место выбирается независимо от остальных.
Ответ: 336 последовательностей. В данном подсчёте «слово» понимается как любая шестибуквенная последовательность. Поэтому порядок букв учитывается, а одинаковые буквы могут повторяться.
Сложение вместо умножения. Так ошибаются, когда видят несколько чисел вариантов и не различают совместные этапы и альтернативы. Если нужно выполнить все этапы, варианты перемножаются, а сложение используют для взаимоисключающих случаев. Проверьте, выбираются ли предметы одновременно для одного результата.
Применение nk при запрете повторов. Формула предполагает, что выбранный элемент остаётся доступным. При запрете повторений на следующих местах вариантов становится меньше. Сверьте вычисление с условием и спросите себя, можно ли снова выбрать уже использованный элемент.
Игнорирование порядка. Иногда последовательности считают одинаковыми только потому, что в них встречаются одни и те же элементы. Для размещений это неверно: перестановка по местам создаёт другой набор. Проверьте, изменится ли результат, если поменять элементы местами.
Исключение нуля из первого места кода. Так происходит из-за привычки к записи многозначных чисел. Для кода начальный ноль допустим, если специального запрета нет. Определите, является объект кодом или именно числом, прежде чем убирать ноль.
До изучения правила произведения нужно уметь внимательно читать условие, выделять этапы выбора и различать совместные и взаимоисключающие варианты. Эти навыки помогают переводить текст задачи в последовательность действий и математическую формулу.
Правило произведения служит основой комбинаторных подсчётов: на нём строятся формулы для различных видов выборок. Оно также используется при вычислении вероятностей, когда сначала нужно определить число всех возможных исходов или число благоприятных исходов.
Почему при последовательном выборе нужно умножать числа вариантов?
Каждому варианту первого этапа можно поставить в соответствие все варианты второго, третьего и следующих этапов. Поэтому для каждого первого выбора образуется одинаковое число продолжений, и общее количество способов получается умножением.
Чем размещение с повторениями отличается от размещения без повторений?
В размещении с повторениями один и тот же элемент разрешено выбирать несколько раз, поэтому на каждом месте доступны все n элементов. Без повторений выбранные элементы исключаются, и число вариантов на следующих местах уменьшается.
Почему в формуле размещений с повторениями порядок имеет значение?
Размещение является упорядоченным набором: последовательности 1, 2, 1 и 2, 1, 1 считаются разными. Перестановка элементов меняет набор, даже если в нём используются те же элементы.
Как понять, можно ли в задаче использовать формулу n^k?
Нужно найти k последовательных мест и убедиться, что для каждого места доступны одни и те же n элементов. Кроме того, повторы должны быть разрешены, а порядок выбранных элементов должен учитываться.
Нужно ли исключать ноль из первого разряда кода?
Нет, если речь идёт именно о коде: код может начинаться с нуля. Ноль исключают из первого разряда только при составлении записи числа, поскольку запись числа с нулём в начале обычно не считается нужным числом разрядов.
§ 2. Правило произведения. Размещения с повторениями
