Помогите пожалуйста решить. Бригада из одиннадцати взломщиков одновременно выходит на грабеж трех разных магазинов. Сколькими способами они могут разделиться, если в каждой группе должно быть не менее двух человек? Сколькими способами их после задержания могут рассадить по четырем одинаковым камерам (не менее чем по одному в каждую)?

задан 8 Июн '17 3:22

10|600 символов нужно символов осталось
0

1) Общее число способов разделиться на три пронумерованные группы равно $%3^{11}$%. Из них надо вычесть число вариантов, когда хотя бы в одной из групп менее двух человек. Обозначим через $%A$%, $%B$%, $%C$% множества вариантов, для которых в первой, второй и третьей группе соответственно, имеется не более одного взломщика. Вычитать надо число $%|A\cup B\cup C|$%, которое мы найдём по формуле включений и исключений.

Находим число $%|A|$%. Если в первой группе никого нет, то остальных можно распределить по двум группам $%2^{11}$% способами. Если в первой группе ровно один взломщик, то его выбираем $%11$% способами, а остальных распределяем $%2^{10}$% способами. Итого $%|A|=2^{11}+11\cdot2^{10}=13\cdot2^{10}$%. Из соображений симметрии, $%|A|=|B|=|C|$%.

Теперь находим число элементов в пересечении $%AB$%. В первых двух группах может быть численность 0,0, или 0,1, или 1,0, или 1,1. Первый вариант всего один. Вариантов второго типа будет $%11$%, и столько же для третьего случая. Для последнего случая имеем $%11\cdot10$%. Итого $%|AB|=1+11+11+11\cdot10=133$%. Ясно также, что $%|AB|=|AC|=|BC|$%.

Тройное пересечение $%ABC$% пусто. По формуле включений и исключений получается $%|A\cup B\cup C|=|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|=3\cdot13\cdot2^{10}-3\cdot133=39537$%. Значит, в ответе будет $%3^{11}-39537=137610$%.

В принципе, есть и другие способы решения, связанные с перебором вариантов, в соответствии с численностью распределения по группам.

2) Здесь число вариантов равно $%S(11,4)$% -- числу Стирлинга второго рода. Эти числа можно найти по таблицам при помощи рекуррентных формул. Напомним, что $%S(n,k)$% есть число разбиений $%n$%-элементного множества на $%k$% непустых равноправных групп. Ясно, что $%S(n,1)=1$%. При $%k > 1$%, если мы изымаем один элемент, то получаем разбиение $%(n-1)$%-элементного множества либо на $%k-1$% часть, либо на $%k$% частей. В первом случае вернуть изъятый элемент на место можно одним способом: он образует одноэлементную часть. Во втором случае его можно вернуть $%k$% способами, добавляя к одной из имеющихся $%k$% частей. Отсюда $%S(n,k)=S(n-1,k-1)+kS(n-1,k)$%. Теперь, рисуя таблицу, постепенно её заполняем по указанным формулам и находим $%S(11,4)=145750$%. Принцип заполнения таблиц можно увидеть здесь.

Можно решить задачу и по-другому, без заполнения таблиц. Если, как и выше, решить задачу при помощи формулы включений и исключений для пронумерованных камер, то получится $%4^{11}-4\cdot3^{11}+6\cdot2^{11}-4$%, и далее это значение делим на число перестановок, равное $%4!$%, получая тот же ответ.

ссылка

отвечен 8 Июн '17 13:14

Спасибо большое!

(8 Июн '17 21:13) olga5
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,297

задан
8 Июн '17 3:22

показан
712 раз

обновлен
8 Июн '17 21:13

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru