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