Перестановки и размещения без повторений групп одинаковых объектов

Пусть на n местах располагают n объектов, которые, в отличие от обычных перестановок, образуют s групп одинаковых объектов. В каждой группе i (1 £ i £ s) число объектов обозначим k_i. При этом k_i ³ 1, k₁ + k₂ + … + k_s = n). С качественной точки зрения перемена местами одинаковых объектов не изменяет набор объектов.

Формула для подсчета общего количества N(C(А)) вариантов всех различных получаемых комбинаторных множеств C(А) может быть получена следующим образом. Вначале предполагаем, что все объекты для размещения различны. При этом получаем: . Затем применяем s раз правило учета сходства и различия к группам одинаковых объектов. После деления N¢(C(А)) на факториалы чисел k₁, k₂, …, k_s, получим итоговую расчетную формулу:

Пример 1.В финал соревнований вышли 6 участников. Определить число всех различных возможных вариантов победителей олимпиады, если организаторы планируют присудить 1 первое, 2 вторых и 3 третьих места. Порядок участников, занявших одинаковое место, не важен.

Решение. Задача сводится к определению количеств перестановок, в которых есть группы одинаковых объектов – участники, занявшие одинаковое (с точки зрения награды) место. Ее параметры:

s = 3 (по результатам финала будут выделены 3 различных группы участников): k₁ = 1 (первое место), k₂ = 2 (второе место), k₃ = 3 (третье место),

n = 6.

По общей формуле число возможных вариантов победителей и призеров:

N = 6! / (1! ×2! ×3!) =60.

Ответ: 60.

Пример 2.Определить число всех различных возможных сообщений длиной в 8 букв, в которых содержатся 3 буквы «a», 2 буквы «б», 2 буквы «и», 1 буква «р».

Решение. Задача сводится к расчету числа вариантов перестановок длины n = 8, в которых есть s = 4 группы одинаковых объектов. В них содержатся следующие числа объектов:

k₁ = 3, k₂ = 2, k₃ = 2, k₄ = 1.

По общей формуле число данных сообщений равно: N = 8! / (3! ×2! ×2! ×1!) =1680.

Ответ: 1680.

Если число размещаемых объектов k меньше числа мест n (k < n), то для расчета их общего числа используется аналогичная формула:

Вывод ее аналогичен первой формуле с учетом того, что вместо перестановок вначале определяются размещения без повторений k различных объектов на n местах .

Пример 3.В 8пронумерованных лунках размещают 2 одинаковых белых и 3 одинаковых черных шара. Найти общее число вариантов размещения.

Решение. В задаче присутствуют две группы одинаковых объектов, в которых числа k₁ = 2, k₂ = 3. Общее число размещаемых шаров k = k₁ + k₂ = 2+3=5. Поэтому задача сводится к определению числа размещений без повторений из 8 по 5 с двумя группами одинаковых объектов (k₁ = 2, k₂ = 3):

Ответ: 560.