Умблик
Справочник вероятности
Подсчёт вариантов
Вероятность и статистика · Подсчёт вариантов

Перестановки с повторяющимися элементами

Убираем из факториального подсчёта перестановки одинаковых объектов.

6 минут на чтениеЗаданий для самопроверки: 3

Чему научимся

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

Главная идея. Если среди n позиций есть группы одинаковых элементов численностей n₁,…,nᵣ, число визуально различных рядов равно n!/(n₁!…nᵣ!), потому что перестановки внутри каждой одинаковой группы незаметны.

План рассуждения и проверка понимания
  1. Посчитайте общее число позиций n и для каждого типа одинаковых элементов его повторяемость nᵢ, проверив сумму n₁ + … + nᵣ = n.
  2. Мысленно различите все экземпляры и получите n!, затем разделите на nᵢ! для каждой группы взаимозаменяемых экземпляров.
  3. Проверьте модель различимости и при малом наборе выпишите варианты, чтобы убедиться, что одинаковые ряды не посчитаны повторно.

Частая ошибка. Разделить только на факториал одного повторяющегося символа или считать одинаковыми физически похожие предметы, хотя условие различает их номерами.

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

Схема к теме

Наглядная модель: Перестановки с повторяющимися элементами

Убираем из факториального подсчёта перестановки одинаковых объектов.

Наглядная модель: Перестановки с повторяющимися элементамиУбираем из факториального подсчёта перестановки одинаковых объектов.1Условиячто известно и чтотребуется2Модельпорядок, повторения идопустимые исходы3Подсчёткаждый вариантучитывается один раз4Проверкамалый случай можновыписать вручную
  • 1. Условия — что известно и что требуется
  • 2. Модель — порядок, повторения и допустимые исходы
  • 3. Подсчёт — каждый вариант учитывается один раз
  • 4. Проверка — малый случай можно выписать вручную
Последовательность отделяет выбор модели от вычисления и не даёт потерять или повторно учесть варианты. Вывод: Сначала ответьте на вопросы о порядке и повторениях, только потом выбирайте формулу.
Проверка пониманияОбъясните тему своими словами

Объясните формулу для слова «МАМА»: почему временная нумерация двух М и двух А даёт 4!, какие четыре перестановки меток не меняют слово и почему ответ равен шести.

В хорошем объяснении есть:

  • Названы две группы повторов размеров 2 и 2 и знаменатель 2!·2!.
  • Пояснено, что перестановка одинаковых букв не образует новый видимый ряд.

Одинаковые буквы не создают новый вариант

Если в ряду есть одинаковые элементы, перестановка двух таких элементов внешне ничего не меняет. Поэтому формула n!n!, считающая все объекты различными, завышает число разных рядов.

Пусть элементов первого типа n1n_1, второго n2n_2 и так далее, всего nn. Мысленно снабдим одинаковые элементы разными номерами. Теперь порядков n!n!, но каждому видимому ряду соответствует n1!⋯nr!n_1!\cdots n_r! перестановок скрытых номеров. Деление на этот одинаковый множитель даёт формулу.

Условия различимости

Нужно точно решить, какие предметы считаются одинаковыми. Две одинаковые на вид книги с разными инвентарными номерами могут быть разными исходами в одной задаче и неразличимыми в другой. Решает условие подсчёта, а не физическое сходство само по себе.

Количество элементов каждого типа фиксировано. Если тип на каждой позиции можно выбирать свободно, это уже размещения с повторениями, а не перестановки фиксированного набора.

Граничный случай одного типа даёт n!/n!=1n!/n!=1: все позиции одинаковы. При всех количествах по единице знаменатель равен единице, и возвращается обычное n!n!.

Три примера

  1. Из букв слова «МАМА» получаются 4!/(2!2!)=64!/(2!2!)=6 различных рядов: две М и две А повторяются.
  2. Пять мест заполняют три белых и два чёрных одинаковых жетона. Число рядов 5!/(3!2!)=105!/(3!2!)=10.
  3. Для букв А, А, Б, В, В, В число рядов 6!/(2!1!3!)=606!/(2!1!3!)=60.

Не делите на количество повторяющихся букв вместо их факториалов. Три одинаковых буквы переставляют скрытые номера 3!=63!=6 способами, а не тремя. Эта тема является комбинаторным расширением; отдельная обязательная школьная привязка здесь не утверждается.

Формула, смысл и ограничения

Главные формулы с расшифровкой

N=n!n1!⋯nr!,n1+⋯+nr=nN=\frac{n!}{n_1!\cdots n_r!},\qquad n_1+\cdots+n_r=n

Формула словами: Есть n позиций и r типов неразличимых внутри типа элементов с заданными количествами.

От формулы к наблюдению

Попробуйте самостоятельно

Измените параметры и сопоставьте расчёт с результатами случайного эксперимента.

Комбинаторика

От простого к сложному

Проверьте себя

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

Открываем задание…

Открываем задание…

Открываем задание…

Источники и соглашения

Объяснения и задачи — авторские. Источники помогают проверить определения, условия и школьную привязку. Обозначения и параметризация указаны в статье.