Вероятность и статистика · объяснение и практика
Почему одинаковые элементы уменьшают число перестановок
Считаем разные строки из набора с одинаковыми символами, объясняем повторный счёт через временные метки и проверяем, какие перестановки действительно видимы.

В теме Комбинаторика и пространство исходов · Учебная карта
Главная мысль
Если среди n элементов одинаковые группы имеют размеры n₁, n₂ и далее, число разных линейных записей равно n!/(n₁!n₂!…). Деление убирает перестановки внутри неразличимых групп.
Как одинаковые буквы создают повторный счёт
Возьмём символы А, А, Б. Если временно пометить одинаковые буквы какА₁ иА₂, получим 3! = 6 порядков. После снятия индексов пары порядков совпадают. Видимы только ААБ, АБА, БАА — три строки. Поэтому число 6 делится на 2!, количество перестановок двух одинаковых букв.
Такое деление не означает случайное сокращение числа вариантов. Каждая видимая строка имеет ровно два помеченных прообраза. Если две группы содержат повторы, одинаковый повторный счёт возникает независимо внутри каждой. Установление этой одинаковой кратности и оправдывает произведение факториалов в знаменателе.
Как считать несколько повторяющихся групп
У набора А, А, Б, Б, В всего 5 символов, две пары одинаковых. Число различных строк равно 5!/(2!·2!) = 120/4 = 30. Если ошибочно разделить только на 2, одна группа повторов останется посчитанной дважды. Если разделить на 4! вместо произведения 2!·2!, будут исключены перестановки между разными буквами, которые на самом деле меняют строку.
У четырёх символов А, А, А, Б число строк 4!/3! = 4. Это легко проверить независимо: единственную Б можно поставить на любое из четырёх мест. Такая проверка особенно полезна, когда почти все элементы одинаковы. Факториальная запись и выбор позиции редкого символа описывают одно множество результатов разными способами.
Пример
Сколько строк получается изА, А, Б, Б без дополнительных ограничений?
4!/(2!·2!) = 6. Можно также выбрать два места дляА: C(4,2) = 6, оставшиеся два автоматически займут Б.
Когда одинаковый вид не означает неразличимость
Две книги с одинаковыми обложками могут оставаться разными объектами, если имеют разные номера или содержание. Тогда их обмен считается новым расположением и делить на 2! нельзя. И наоборот, если задача наблюдает только цвет жетонов, перестановка двух синих жетонов с разными невидимыми номерами может не менять видимую цветовую строку. Объект счёта задаётся условием.
Дополнительные запреты, например отсутствие соседних А, требуют отдельного отбора. Формула с факториалами считает все строки данного состава без таких ограничений. Вероятность конкретной видимой строки тоже зависит от механизма: равномерная перестановка различимых помеченных предметов даёт одинаковые веса строк фиксированного состава, но другой способ генерации может их изменить. Сначала определяют различимость и порядок, затем ограничения, и лишь после этого выбирают формулу.
От чтения к действию
А теперь — вы
Частые вопросы
Почему делят на факториалы групп отдельно?
Перестановки внутри каждой неразличимой группы не меняют строку. Их независимые кратности перемножаются.
Можно ли той же формулой учесть запрет соседства?
Не напрямую. Она считает все строки данного состава; дополнительный запрет требует отдельного расчёта.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Когда порядок выбранных предметов не создаёт новый вариант
Считаем группы без должностей и порядка, объясняем деление на перестановки внутри выбранной группы и отличаем сочетания от упорядоченного выбора.
Открыть темуКак посчитать все порядки разных предметов
Считаем линейные порядки всех разных предметов, объясняем убывание числа вариантов на каждом месте и учитываем простое ограничение соседства как блок.
Открыть тему