"Алгебра и начала математического анализа. Углубленный уровень", Виленкин Н.Я., Ивашев-Мусатов О.С., Шварцбурд С.И.
Перестановка с повторениями — это порядок всех элементов набора, в котором некоторые элементы одинаковы и неразличимы. Такие задачи встречаются при подсчёте разных слов из букв, кодов и последовательностей. Если просто переставить n элементов, получится n! вариантов, но одинаковые символы приводят к повторному счёту. Чтобы его убрать, делят n! на произведение факториалов количеств повторяющихся элементов. Главное — учесть каждый элемент и каждую группу одинаковых символов.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Перестановка — размещение всех данных элементов в определённом порядке. Например, из трёх разных букв можно составить последовательности, меняя их местами. Это понятие нужно, когда важно посчитать все возможные порядки и каждый элемент должен быть использован.
Перестановка с повторениями — перестановка элементов, среди которых есть одинаковые, неразличимые элементы. Например, две буквы А в записи ААБ не различаются между собой. Это понятие помогает считать разные последовательности, не принимая один и тот же результат за несколько вариантов.
Кратность элемента — количество одинаковых элементов данного вида; кратности обозначают n₁, n₂, …, nₖ. Например, в наборе ААББ буква А имеет кратность 2, и буква Б тоже имеет кратность 2. Обозначения позволяют отдельно учесть каждую группу повторяющихся элементов.
Число перестановок с повторениями — количество различных порядков, которые можно получить из набора с одинаковыми элементами. Различными считаются только последовательности, отличающиеся расположением символов, а не условными номерами одинаковых букв. Это число находят, устраняя повторный счёт по формуле с факториалами кратностей.
Если есть n различных элементов, для первого места можно выбрать любой из n элементов. После этого для второго остаётся n − 1 вариант, для третьего — n − 2, и так далее, пока не будет использован каждый элемент. По правилу произведения получаем n · (n − 1) · … · 1 = n!, где факториал n — произведение всех натуральных чисел от 1 до n. Этот подсчёт станет отправной точкой для случая с одинаковыми элементами.
Когда элементы одинаковы, обмен двух таких элементов не создаёт нового видимого порядка. Если мысленно пронумеровать две буквы А, то перестановки А₁А₂Б и А₂А₁Б после удаления номеров превратятся в одну и ту же последовательность ААБ. Значит, подсчёт n! различает то, чего в условии различить нельзя. Чтобы найти только разные результаты, нужно понять, сколько раз каждый результат учтён.
Внутри группы из n₁ одинаковых элементов можно мысленно выполнить n₁! перестановок, не меняя итоговой последовательности. Для второй группы таких невидимых перестановок будет n₂!, и так далее для всех групп. По правилу произведения один и тот же видимый порядок оказывается учтён n₁! · n₂! · … · nₖ! раз. Поэтому деление на это произведение убирает лишние копии.
Если всего элементов n, а группы одинаковых элементов имеют кратности n₁, n₂, …, nₖ, то число различных порядков равно n!/(n₁!n₂!…nₖ!). Здесь n = n₁ + n₂ + … + nₖ: каждый элемент относится ровно к одной группе. В числителе сначала считаются все перестановки как будто элементы различны, а знаменатель устраняет перестановки внутри групп, которые не меняют результат. Если кратность равна 1, её факториал равен 1 и на ответ такая группа не влияет.
Распознать такую задачу можно по условию: нужно переставить все элементы, порядок важен, а несколько элементов совпадают и неразличимы. Сначала выпиши общее количество элементов, затем посчитай, сколько раз встречается каждый вид. Проверь равенство n = n₁ + n₂ + … + nₖ и убедись, что каждый элемент используется ровно один раз. Если выбирают только часть элементов или порядок не важен, это уже не задача на перестановки.
| Ситуация | Обозначение общего числа элементов | Число различных перестановок |
|---|---|---|
| Все элементы различны | n | n! |
| Одна группа из n₁ одинаковых элементов | n | n!/n₁! |
| Несколько групп одинаковых элементов с кратностями n₁, n₂, …, nₖ | n = n₁ + n₂ + … + nₖ | n!/(n₁!n₂!…nₖ!) |
| Частный случай: все элементы одинаковы | n = n₁ | n!/n! = 1 |
| Проверка: сумма кратностей равна общему числу элементов | n = n₁ + n₂ + … + nₖ | Проверь состав набора до вычислений |
Найди строку, подходящую к условию, и сначала установи общее число элементов и кратность каждой группы. Если повторений нет, используй n!, а если есть — дели его на факториалы кратностей. Последняя строка помогает проверить, что ни один элемент не потерян и не посчитан дважды.
Сколько различных последовательностей можно составить из букв А, А, Б? Все три буквы должны войти в каждую последовательность. Две буквы А одинаковы, поэтому их обмен не создаёт нового варианта.
Считаем общее число букв: n = 3. Если временно считать буквы различными, переставить их можно 3! = 6 способами. Это промежуточное число включает лишние варианты.
У буквы А кратность 2, а у Б — 1. Делим 6 на 2!, потому что обмен двух букв А не меняет последовательность. Получаем 3!/2! = 6/2 = 3.
Ответ: 3 последовательности. Их можно проверить перечислением: ААБ, АБА, БАА. Других порядков нет, если использовать обе буквы А и букву Б ровно по одному разу.
Сколько различных слов можно получить перестановкой букв слова «МАМА»? Всего в слове четыре буквы. Буквы М и А повторяются по два раза, поэтому необходимо учесть обе группы.
Записываем общее число элементов: n = 4. Кратность М равна 2, кратность А также равна 2. Проверка состава даёт 2 + 2 = 4.
Подставляем кратности в формулу: 4!/(2!·2!). Вычисляем: 24/(2·2) = 6. Деление на каждый факториал необходимо, поскольку внутри каждой пары одинаковых букв обмен не меняет слово.
Ответ: 6 различных последовательностей. Например, среди них есть ММАА, МАМА и АММА. Каждая перестановка использует все четыре буквы, а повторяющиеся М и А не различаются.
Сколько различных последовательностей можно составить из 8 элементов, среди которых 3 одинаковых элемента первого вида, 2 второго, 2 третьего и 1 четвёртого вида? Все элементы должны войти в последовательность. Сначала проверим, что описание набора согласовано.
Складываем кратности: 3 + 2 + 2 + 1 = 8. Сумма совпадает с указанным общим количеством, значит, кратности описывают весь набор. Повторяются три группы, а четвёртый вид встречается один раз.
Применяем формулу: 8!/(3!·2!·2!·1!). Вычисляем: 40320/(6·2·2·1) = 40320/24 = 1680. Фактор 1! можно не записывать, так как он равен 1.
Ответ: 1680 последовательностей. Проверка кратностей до вычисления помогает не забыть группу или не включить лишний элемент. В формуле в числителе стоит общее число элементов, а не количество их видов.
Считать одинаковые элементы различными и получать n!. Так происходит, когда применяют формулу перестановок без проверки, есть ли в наборе совпадающие символы. В результате один и тот же видимый порядок учитывается несколько раз. Проверь, можно ли различить элементы одного вида; если нельзя, добавь в знаменатель факториалы их кратностей.
Делить только на одну группу повторяющихся элементов. Иногда замечают одну пару одинаковых символов, но забывают о другой группе. Тогда повторный счёт устраняется не полностью и ответ получается завышенным. Составь список всех видов элементов и поставь в знаменатель факториал каждой кратности.
Использовать в числителе количество групп вместо общего числа элементов. Число групп показывает, сколько видов элементов есть, но не сколько всего элементов переставляют. Например, три вида могут включать восемь элементов. Пересчитай все символы и проверь, что их число равно сумме кратностей.
Путать перестановки с повторениями с размещениями или сочетаниями. Это случается, если ориентироваться лишь на наличие одинаковых элементов и не проверить, что именно требуется посчитать. Перестановка использует весь набор, а порядок в ней важен; в сочетании порядок не важен, в размещении может использоваться только часть набора. Перед формулой сверь условие с этими признаками.
Для понимания темы нужны перестановки без повторений, факториал и правило произведения. Они объясняют, почему исходный подсчёт равен n! и как строится число вариантов. Новая формула уточняет этот подсчёт, если часть элементов неразличима.
Перестановки с повторениями применяют, когда считают разные слова из букв, коды или последовательности с одинаковыми символами. Важно отличать одинаковые символы от разных: это напрямую меняет кратности и знаменатель формулы. Такой подсчёт помогает заранее узнать, сколько разных результатов возможно.
Формула связана с комбинаторикой, биномиальными коэффициентами и вероятностью. В задачах на вероятность она может помочь посчитать общее число равновозможных последовательностей или число подходящих исходов. Умение учитывать повторения важно, чтобы не завысить эти количества.
Почему нельзя просто использовать формулу n!?
Формула n! считает элементы различными и учитывает, кто именно занял каждое место. Если среди элементов есть одинаковые, некоторые полученные порядки будут выглядеть одинаково. Поэтому n! даст завышенное число.
Что именно обозначают числа n₁, n₂, …, nₖ?
Это кратности групп одинаковых элементов: n₁ — количество элементов первого вида, n₂ — второго и так далее. Каждая группа содержит неразличимые между собой элементы. Сумма всех кратностей равна общему числу элементов n.
Почему в знаменателе стоят факториалы кратностей?
Внутри каждой группы одинаковые элементы можно мысленно переставлять nᵢ! способами, но вид последовательности при этом не изменится. Значит, каждый различимый порядок посчитан лишний раз столько раз, сколько таких перестановок внутри групп. Деление на произведение факториалов убирает этот повторный счёт.
Как понять, являются ли два элемента одинаковыми?
Элементы одинаковы, если по условию задачи их нельзя различить и обмен местами не меняет получившуюся последовательность. Например, две буквы А в слове неразличимы. Если же элементы имеют разные обозначения или свойства, их считают различными.
Чем перестановки с повторениями отличаются от сочетаний и размещений?
При перестановке используются все данные элементы, а порядок важен. В сочетаниях порядок не учитывается, а в размещениях выбирают только часть элементов и порядок важен. Поэтому перед применением формулы нужно проверить, что все элементы включены ровно по одному разу.
6. Перестановки с повторениями
