Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Математика _ Дискретка, комбинаторика

Автор: Айра 23.11.2007 3:29

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

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

Автор: мисс_граффити 23.11.2007 6:35

а если так...

чтобы не путаться, обозначим гостей как эл-ты матрицы: 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 элементов (комнаты-то разные...).
-------------------------------------------------------
думаю, можно все то же решить намного проще по готовым формулам.
формулу для расселения без учета пожелания о том, что все должны быть соседями с людьми из другой делегации, я знаю.
а вот как от нее прийти к нужной... sad.gif
-------------------------------------------------------
могла где-то ошибиться. уж извините...

Автор: Айра 26.11.2007 2:34

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

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

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

в этой задаче есть пункт б) "ровно в 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!(факториал)..

Что скажете? wink.gif

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

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

Автор: мисс_граффити 26.11.2007 3:32

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

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

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

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

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

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

Автор: Айра 27.11.2007 2:48

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

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

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

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

Автор: мисс_граффити 27.11.2007 4:41

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

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

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

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

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

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