Дискретка, комбинаторика Опции

[Айра]

Привет!
Есть задача:
"Сколько существует вариантов поселения 12 человек из 4-х делегаций численностью по 3 человека в 6-ти двухместных номерах гостиницы так, чтобы а) во всяком номере жили представители разных делегаций"

Объясните, пожалуйста, как это решается?

Сообщение отредактировано: Айра - 22.11.2007 23:30

[мисс_граффити]

а если так...

чтобы не путаться, обозначим гостей как эл-ты матрицы: 11,12,13,21,22...
соседа для 11 можно найти 9 способами
для 12 - 8 способов
для 13 - 7 способов
итого 8*7*9

далее рассмотрим 3 случая:
-все соседи из одной группы (например, из 2). осталось 2 целых делегации. расселим их
31 может выбрать любого из 3 соседей
32 - из 2
33 остался без выбора. итого 6.
в результате - 9*8*7*6


-2 соседа из 1 группы, третий из другой
получим 1 полную группу и 2 неполных. количество расселений, вроде, такое же. (9*8*7*6)

-все трое из разных групп.
получаем 3 неполных группы. здесь я насчитала 8 вариантов. то есть
9*8*7*8

итого 9*8*7*(6+6+8)
и все это дело еще умножить на число перестановок для 6 элементов (комнаты-то разные...).
-------------------------------------------------------
думаю, можно все то же решить намного проще по готовым формулам.
формулу для расселения без учета пожелания о том, что все должны быть соседями с людьми из другой делегации, я знаю.
а вот как от нее прийти к нужной...
-------------------------------------------------------
могла где-то ошибиться. уж извините...

[Айра]

Извини, что долго молчала Спасибо тебе большое!!!!
Я вроде все поняла, только пара уточняющих вопросов: способы находятся сочетаниями (например для 11 С из 9 по 1?) и

получаем 3 неполных группы. здесь я насчитала 8 вариантов

8 это потому что 4*2*1 )

в этой задаче есть пункт б) "ровно в 2-х номерах жили представители одинаковых делегаций"

вот что у меня получилось:

__1-й случай: при первом распределении получаются 2 пары: тогда выходит 2*2*5*4*3*1
__2-й случай: при первом распределении получается только 1 пара: 2*7*5*5*1*1
__3-й случай: пар не образовалось, он в свою очередь разбивается еще на 3 случая:
____3.1: все соседи из одной делегации: в таком случае ровно 2 пары влоде сделать невозможно
____3.2: все соседи из разных: здесь, вроде та же ситуация
____3.3: 2-е из одной длегации, а тритий из другой: 9*8*7*2*1*1

Итого 2*2*5*4*3*2*7*5*5*9*8*7*2*6!(факториал)..

Что скажете?

думаю, можно все то же решить намного проще по готовым формулам

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

[мисс_граффити]

ну это типа метода построения дерева и получается. рассматриваем разные варианты.
сочетания... да, но не везде... вроде где 3 неполные делегации - по-моему, нет.

8 это потому что 4*2*1

почему? )))

б) "ровно в 2-х номерах жили представители одинаковых делегаций"

это как? допустим, 1 человек из 1ой и один из 3ей - и так в двух номерах?

вообще мы решаем все методом построения деревьев, вроде так называется..

ну видишь... у вас этот курс более углубленный. у нас в 1 семестр запихнули теорию вероятности, комбинаторику, математическую статистику и случайные процессы (это один предмет такой страшный! из 4 компонентов)

[Айра]

это как? допустим, 1 человек из 1ой и один из 3ей - и так в двух номерах?

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

у нас в 1 семестр запихнули теорию вероятности, комбинаторику, математическую статистику и случайные процессы (это один предмет такой страшный! из 4 компонентов)

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

[мисс_граффити]

Графы - это классная вещь.
А много "ужаса" уже не успеете - сессия ж в январе?
ладно, завершаю оффтоп.

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

2 пары из 1 делегации мы не наберем.
итак, у нас в любом случае будет 2 делегации по 1 человеку и 2 по 3. выбрать, какие из делегаций будут неполными, можно С(2,4)=6 способами (по 2 из 4 думаю, поняла такое обозначение).
Внутри каждой из делегаций пары можно выбрать 3 способами.
итого 3*3*6
расселим остальных
не нарушая общности, предположим, что вместе живут люди из 1 и 2 (просто чтобы нумеровать как-то).
ищем соседа для человека из 1 делегации.
1) если его поселить с человеком из второй, надо будет расселить 2 полные делегации. это, я думаю, досчитаешь сама... я обозначу х
2) если его поселить с человеком не из второй (6 способов), потом человеку из 2 останется выбор из 3 соседей. осталось расселить 2 делегации по 2 человека (2 варианта)

Итого, вроде бы: 3*3*6(х+6*3*2)

ну и по номерам их можно расселять как угодно, опять же... еще один множитель.

З.Ы. что-то я на форум в неприличное время захожу, уже с абсолютной кашей в голове. так что проверяй внимательно, могут быть ошибки