Подсчёт перестановок с одинаковыми объектами

Эта тема является частью раздела о комбинаторике в Quant GMAT Focus.

До этого момента мы рассматривали задачи на счёт, в которых все n объектов различны. Это естественно, когда речь идёт о людях: каждый человек уникален.
Однако в задачах GMAT и GRE часто встречаются ситуации, где часть объектов одинаковы, и в таких случаях требуется специальный подход к подсчёту.

Базовая идея: почему возникает проблема

Рассмотрим пример.

Пример 1. Книги с одинаковыми словарями

У библиотекаря есть 7 книг:

• 4 разных романа,

   

• 3 одинаковых экземпляра одного и того же словаря.

   

Сколькими различными способами можно расставить эти 7 книг на полке?

Шаг 1. Временный приём: считаем одинаковые объекты разными

Для начала временно представим, что три словаря различны.
Обозначим их как D1, D2 и D3.

Тогда у нас есть 7 различных объектов, и количество возможных перестановок равно:

7!

Шаг 2. Почему это число слишком большое

Рассмотрим любую конкретную расстановку, где:

• романы стоят в фиксированных местах,

   

• словари занимают три конкретные позиции.

   

Если мы переставляем между собой только словари, а романы остаются на своих местах, то:

• существует 3! = 6 способов переставить словари,

   

• но все эти 6 вариантов выглядят одинаково, потому что словари идентичны.

   

То есть каждая реальная расстановка была посчитана 6 раз.

Шаг 3. Исправление переучёта

Следовательно, число 7! завышено в 3! раз.

Правильное количество различных расстановок:

7! / 3!

Расписываем:

7! / 3! = (7 × 6 × 5 × 4 × 3 × 2 × 1) / (3 × 2 × 1)

Сокращаем:

= 7 × 6 × 5 × 4

Считаем:

• 7 × 6 = 42

   

• 5 × 4 = 20

   

• 42 × 20 = 840

   

Ответ: 840 различных расстановок.

Общее правило для одинаковых объектов

Если:

• всего n объектов,

   

• из них b объектов одинаковы,

   

то количество различных перестановок равно:

n! / b!

Это ключевое правило, которое нужно знать для экзамена.

Несколько групп одинаковых объектов

Если в наборе из n объектов:

• b объектов одинаковы между собой,

   

• c других объектов одинаковы между собой,

   

• d других объектов одинаковы между собой,

   

то число различных перестановок равно:

n! / (b! × c! × d!)

Классический пример: слово «Mississippi»

Это правило часто называют «правилом Mississippi» из-за популярного примера.

Слово Mississippi содержит 11 букв:

• 1 буква M,

   

• 4 буквы I,

   

• 4 буквы S,

   

• 2 буквы P.

   

Количество различных перестановок букв этого слова равно:

11! / (4! × 4! × 2!)

Именно так учитывается наличие нескольких групп одинаковых объектов.

Пример 2. Практическая задача

У библиотекаря есть:

• 5 одинаковых копий книги A,

   

• 2 одинаковые копии книги B,

   

• 1 копия книги C.

   

Всего 8 книг.
Сколькими различными способами их можно расставить на полке?

Решение

Общее число перестановок без учёта одинаковости:

8!

Теперь учитываем одинаковые книги:

• делим на 5! за книги A,

   

• делим на 2! за книги B.

   

Итого:

8! / (5! × 2!)

Распишем и сократим:

• 8! / 5! = 8 × 7 × 6

   

• 6 / 2 = 3

   

Получаем:

8 × 7 × 3 = 168

Ответ: 168 различных расстановок.

Выводы

• Если среди n объектов есть одинаковые, стандартное n! приводит к переучёту.

   

• Если b объектов одинаковы, нужно делить на b!.

   

• Если есть несколько групп одинаковых объектов, делим на произведение соответствующих факториалов.

   

• Перечисление нескольких вариантов иногда помогает увидеть структуру задачи и правильно применить формулу.

   

Подсчёт перестановок с одинаковыми объектами — обязательная тема для комбинаторики GMAT и GRE Quant, и к ней мы будем неоднократно возвращаться в следующих уроках.

Следующий урок посвящен устранению повторного подсчета.