Комбинаторика

[MayorBarbariska]

Такая задача:
Бригада из одиннадцати взломщиков одновременно выходит на грабеж трех разных магазинов. Сколькими способами они могут разделиться, если в каждой группе должно быть не менее двух человек? Сколькими способами их после задержания могут рассадить по четырем одинаковым камерам (не менее чем по одному в каждую)?
решал я ее таким образом:
так как магазина три, то они деляться на три группы и так как магазины разные, то разделения $\{2; 4; 5\}$ и $\{4; 2; 5\}$ - разные. поэтому нужно искать число перестановок $P_n=n!$ в каждом таком разделении. Итак:
$\{2; 2; 7\}$ - всего 3 варианта такого разделения.
$\{2; 3; 6\}$ - 3!=6 вариантов
$\{2; 4; 5\}$ - 3!=6 вариантов
$\{3; 3; 5\}$ - 3 варианта
$\{3; 4; 4\}$ - 3 варианта
все остальные варианты входят в число уже посчитанных. осталось их сложить и получиться что они могут разделиться 21 способом. ну а для размещения 11 человек по одинаковым камерам использовал формулу для числа сочетаний, получиться $(11\cdot10\cdot9\cdot8)/4!=330.$
вопрос вот в чем, как решать первую часть этой задачи при условии, что каждый взломщик уникален?

[VAL]

По первой задаче:
Вы учли, что магазины разные, но забыли учесть, что преступники тоже разные.

По второй задаче - вообще ерунда написана.
Вы выбираете 4 камеры из 11 человек?!
Ваш ответ годился бы, если бы надо было выбрать из данных 11-и преступников четверых и посадить их (допустим, в одну камеру), а остальных отпустить. Но в условии сказано другое.

[AnDe]

В группе вида $(m;n;l)$ разделить людей можно $C_{m+n+l}^m \cdot C_{n+l}^n$ способами.

VAL в сообщении #562962 писал(а):

По первой задаче:
Вы учли, что магазины разные, но забыли учесть, что преступники тоже разные.

Так ТС и спрашивает как это учесть.

[MayorBarbariska]

мда, поперепутал все.

Цитата:

В группе вида $(m;n;l)$ разделить людей можно $C_{m+n+l}^m \cdot C_{n+l}^n$ способами

можете пояснить, как получается данная формула?

Цитата:

По второй задаче - вообще ерунда написана

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

[AnDe]

Ну смотрите, чтобы сформировать группу взломщиков которые пойдут на дело в первый магазин вам надо выбрать m человек из всей бригады. Это как раз можно сделать $C_{m+n+l}^m$ способами. (Из условия видно, что идут все одиннадцать человек) Потом нужно выбрать n человек на второе дело из оставшихся, всего это можно сделать $C_{n+l}^n$ способами. Третья группа после выбора первых двух определяется однозначно (остается ровно l человек) По правилу произведений, чтобы получить все возможные комбинации надо перемножить эти числа. Причем понятно, что мы посчитали каждую группу, и не посчитали никакую два раза. Всего $C_{n+m+l}^mC_{n+l}^n=\frac{(n+m+l)!}{m!(n+l)!}\frac{(n+l)!}{n!l!} = \frac{(n+m+l)!}{n!m!l!}$ (Отсюда сразу видно, что без разницы с какой группы начинать считать, что в принципе очевидно)

[MayorBarbariska]

но ведь нужно так же учесть условие, что в группе не может быть меньше двух человек. а ко второй части эту формулу можно применять без всяких поправок, как я понял.
p.s. уже разобрался, огромное спасибо за ваши ответы))

[VAL]

MayorBarbariska в сообщении #563000 писал(а):

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

Это Вы учтете, когда будете выбирать $k, l$ и $m$.

[MayorBarbariska]

VAL, спасибо, я уже понял это)

[VAL]

MayorBarbariska в сообщении #563000 писал(а):

а ко второй части эту формулу можно применять без всяких поправок, как я понял.

Как раз таки во второй части нужны поправки, поскольку камеры по условию одинаковые.
А лучше не поправки, а совсем другой подход. Через числа Стирлинга второго рода.

Кстати, какой у Вас ответ получился?

[MayorBarbariska]

Цитата:

Через числа Стирлинга второго рода

так глубоко я в комбинаторику не залазил.

Цитата:

Кстати, какой у Вас ответ получился?

я пока разбираюсь с формулой. допустим для первой группы я выбрал $m=2$, получиться $C_{11}^2$, то как для второй выбрать $n$, что бы посчитать все возможные группы, у меня получается, что для разных выбранных мною $n$ разные ответы

[VAL]

MayorBarbariska в сообщении #563014 писал(а):

Цитата:

Через числа Стирлинга второго рода

так глубоко я в комбинаторику не залазил.

Однако условие задачи предполагает именно такой подход, как наиболее естественный.
Конечно, можно и по-другому посчитать. Например, полным перебором. Но вряд ли имелось это в виду.

Цитата:

Цитата:

Кстати, какой у Вас ответ получился?

я пока разбираюсь с формулой. допустим для первой группы я выбрал m=2, получиться $C_{11}^2$, то как для второй выбрать $n$, что бы посчитать все возможные группы, у меня получается, что для разных выбранных мною $n$ разные ответы

Разберетесь, напишите окончательный ответ. Сверимся.

[MayorBarbariska]

AnDe можете на примере объяснить формулу, а то каждый раз разные ответы выходят

[VAL]

MayorBarbariska в сообщении #563028 писал(а):

AnDe можете на примере объяснить формулу, а то каждый раз разные ответы выходят

А мне можно?
Допустим главарь решил отправить пять человек брать первый магазин, четверых - второй и двоих - третий.
Выбираем пятерых - $C_{11}^5$.
При каждом таком выборе на второй магазин можно выбрать 4-ч из 6-и оставшихся - $C_6^4$. Т.е. общее число комбинаций - $C_{11}^5\cdot C_6^4$.
Оставшихся двоих направляем в третий магазин. Число комбинаций при этом не изменится.

[MayorBarbariska]

VAL конечно, присоеденяйтесь, я только рад. возможно я что-то не так делаю, но у меня при предложенном вами разделении банды, получается не целое число способов, а именно 57.75

[VAL]

MayorBarbariska в сообщении #563040 писал(а):

возможно я что-то не так делаю, но у меня при предложенном вами разделении банды, получается не целое число способов, а именно 57.75

Как это?! Как произведение двух целых чисел может оказаться дробным?

-- 23 апр 2012, 17:28 --

Полагаю, у Вас лишний множитель 5! в знаменатель затесался.