Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

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



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

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

N(С(А(а1 ¹ а2 ¹ … ¹ ap))) = N(С(А(а1 = а2 = … = аp))) × p!.

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

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

N(С(А(m1 ¹ m2 ¹ … ¹ms))) = N(С(А(m1 = m2 = … = ms))) × s!

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

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

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

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

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

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

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

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

C(А(m1 = m2)) = {(а, 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(a1) = 10, для второго – N(a2) = 9 (поскольку один делегат к этому времени уже занят), для третьего – N(a3) = 8.

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

N(С(А)) = N(a1) × N(a2) × N(a3) = 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.




Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.