Правило учета сходства и различия

Допустим, рассматриваются все варианты расположения на заданных местах объектов некоторого множества A, содержащего подмножество из p объектов {a} = {а₁, а₂,…, а_p} ({a} Í А). Обозначим условно через C(A(а₁ ¹ а₂¹ … ¹ a_p)) комбинаторное множество, образованное из A при условии различия всех объектов в подмножестве {a}, а через C(A(а₁ = а₂ = … = а_p)) – аналогичное множество, полученное из A при условии неразличимости, одинаковости объектов в {a}.

Для общих чисел вариантов комбинаторных множеств справедливо следующее соотношение:

N(С(А(а₁ ¹ а₂ ¹ … ¹ a_p))) = N(С(А(а₁ = а₂ = … = а_p))) × p!.

Аналогично рассмотрим все варианты расположения некоторого множества объектов A на заданном множестве мест М, содержащем выделенное подмножество из s мест {m} = {m₁, m₂, …, m_s} ({m} Í M). Обозначим через C(А(m₁ ¹ m₂ ¹ … ¹ m_s)) комбинаторное множество, образованное из A при условии различия всех s мест в подмножестве {m}, а через C(А(m₁ = m₂ = … = m_s)) – аналогичное множество вариантов расположения, полученное из A при условии неразличимости всех мест в {m}.

Для общих чисел различных вариантов расположения объектов в двух рассмотренных случаях справедливо аналогичное соотношение

N(С(А(m₁ ¹ m₂ ¹ … ¹m_s))) = N(С(А(m₁ = m₂ = … = m_s))) × s!

Справедливость обеих формул вытекает из того, что каждому варианту расположения p неразличимых объектов (соответственно, объектов на s неразличимых местах) по правилу умножения соответствует p! разных вариантов перестановок при различающихся объектах (соответственно, s! разных вариантов перестановок при различающихся выделенных местах). Введенное правило комбинаторики назовем правилом учета сходства-различия. Расчетная схема для учета сходства-различия объектов приведена на рис. 5.5.

1. Рис. 5.5. Расчетная схема для учета сходства-различия объектов

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

Рис. 5.6. Расчетная схема обратного перехода в правиле учета сходства-различия

Пример 3. Рассмотрим расположение двух различных букв из множества A = {a, b, c} на двух различных местах m₁ и m₂.

Если все буквы различны и места различны, то:

C(А) = {(а, b); (а, c); (b, c); (b, a); (c, a); (c, b)}; N(С(А)) = 6.

Если места для расположения букв неразличимы (при этом, например, вариант (а, b) равен варианту (b, а)), то с учетом числа одинаковых мест s = 2 получим:

C(А(m₁ = m₂)) = {(а, b); (b, с); (а, с)}; N(С(А)) = 6/2! =3.

Если две последние буквы b и c одинаковы, то, подставляя вместо c букву b (так как c = b), с учетом числа одинаковых объектов p = 2 получим:

C(А(b = c)) = {(а, b); (b, b); (b, a)}; N(С(А)) = 6/2! =3.

Если все буквы а, b и c одинаковы (a = b = c), то с учетом числа одинаковых объектов p = 3 получим:

C(А(a = b = c)) = {(a, a)}; N(С(А)) = 6/3! =1.

Пример 4.На конференции присутствует 10 делегатов. Определить, сколькими способами можно сформировать из них состав комиссии в составе трех членов в двух случаях:

1) порядок членов комиссии (1-й, 2-й, 3-й) имеет значение;

2) все члены комиссии равноправны.

Решение. Вначале допустим, что число порядок членов комиссии имеет значение (случай 1). При этом число вариантов выбора первого члена комиссии N(a₁) = 10, для второго – N(a₂) = 9 (поскольку один делегат к этому времени уже занят), для третьего – N(a₃) = 8.

Общее число вариантов в случае 1 находим по правилу умножения:

N(С(А)) = N(a₁) × N(a₂) × N(a₃) = 10×9×8=720.

В случае 2) порядок расположения объектов не имеет значения и найденное выше число вариантов необходимо дополнительно разделить на 3!=6:

N(С(А)) = 720/6=120.

Ответ: 1) 720;2)120.

Применение рассмотренных выше правил 1) сложения, 2)включений-исключений, 3) умножения и 4) учета сходства-различия позволяют находить количественные оценки чисел вариантов во всех стандартных задачах комбинаторики на подсчет числа расположений объектов на выделенных местах, в которых множества объектов и мест для их размещения имеют простую структуру – учитывается только их число, сходство или различие.

Совместное применение данных правил позволяет также решать и усложненные комбинаторные задачи.

Пример 5.В комиссии по делам семьи 4 мужчины и 7 женщин. Необходимо избрать руководство комиссии – председателя и его заместителя. Определить, сколько существует возможных вариантов избрания руководства, если по положению в руководстве обязательно должны быть и мужчина и женщина.

Решение. Из положения следует, что для руководства возможны только два сочетания: 1) председатель – мужчина, заместитель – женщина; 2) председатель – женщина, заместитель – мужчина.

Рассмотрим сначала сочетание 1). На место председателя возможно избрание одного из 4 мужчин, на место его заместителя независимо может быть избрано 7 женщин. Порядок расположения имеет значение. Следовательно, по правилу умножения общее число вариантов для сочетания 1) равно 4×7=28.

Для сочетания 2) подсчет числа вариантов аналогичен: 7×4=28.

Общее число вариантов находим по правилу сложения, поскольку сочетания 1) и 2) являются взаимоисключающими.

Ответ: 28+28=56.