Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� : Июнь 16, 2010, 22:07:22 � |
|
Имеется n супружеских пар. Сколькими способами их можно рассадить за столом так, чтобы каждая пара сидела раздельно?
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
staison
Новенький
Offline
Сообщений: 8
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0
|
|
� Ответ #1 : Июнь 17, 2010, 12:48:24 � |
|
(2n)! - 2*n!
Формула вкл/искл. По-моему так.
|
|
|
Записан
|
|
|
|
MagTux
Гений-Говорун
Offline
Сообщений: 1415
СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99
Реинкарнация Будды
|
|
� Ответ #2 : Июнь 17, 2010, 14:06:01 � |
|
(2n)! - 2*n! Формула вкл/искл. По-моему так.
Для двух пар получается (2*2)!-2*2!=20 вариантов вместо двух. Тут всё сложнее. У меня без циклов не выходит.
|
|
|
Записан
|
Существует два правила на пути к успеху: 1. Не говори никому всего, что ты знаешь.
|
|
|
staison
Новенький
Offline
Сообщений: 8
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0
|
|
� Ответ #3 : Июнь 17, 2010, 15:14:35 � |
|
(2n)! - 2*n! Формула вкл/искл. По-моему так.
Для двух пар получается (2*2)!-2*2!=20 вариантов вместо двух. Тут всё сложнее. У меня без циклов не выходит. Требуется уточнить условие: 1) оказывается стол круглый 2) какие способы являются различными
|
|
|
Записан
|
|
|
|
staison
Новенький
Offline
Сообщений: 8
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0
|
|
� Ответ #4 : Июнь 17, 2010, 17:19:04 � |
|
1. Если считать важными места, а не соседей, то будет x = (2n)! - 2*2*n! 2. Иначе(т.е учесть циклич. сдвиг и симметрию) x = ((2n)! - 2*2n!)/2*(2n) 2. n = 2, x = 2 Идея проста - формула вкл/искл. Ну прям не знаю, если это неправильно
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #5 : Июнь 17, 2010, 17:31:03 � |
|
Требуется уточнить условие: 1) оказывается стол круглый 2) какие способы являются различными 1. Да, стол круглый. 2. Допустим у нас две пары 1-2, 3-4, тогда возможны такие расположения, отвечающие условию 1423, 4132.
|
|
� Последнее редактирование: Июнь 17, 2010, 17:41:47 от Илья �
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
staison
Новенький
Offline
Сообщений: 8
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0
|
|
� Ответ #6 : Июнь 17, 2010, 17:41:37 � |
|
Если я правильно понял, cпособы считаются одинаковыми, если у чел-ка одинаковые соседи в обоих случаях. И ответ в этом случае см.п2(выше)
|
|
� Последнее редактирование: Июнь 17, 2010, 20:30:34 от staison �
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #7 : Июнь 17, 2010, 17:44:23 � |
|
Исправил: 2. Допустим у нас две пары 1-2, 3-4, тогда возможны такие расположения, отвечающие условию 1423, 4132. 1324, 3142 Эти два примера будут аналогичны первым двум.
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
MagTux
Гений-Говорун
Offline
Сообщений: 1415
СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99
Реинкарнация Будды
|
|
� Ответ #8 : Июнь 18, 2010, 00:50:50 � |
|
Для 3 пар это 32 варианта Для 4 - 1488 Для 5 - 112512 могу дальше посчитать
В формуле должно быть 2n. Остальное пока гадаю. Посчитал написанной программой.
|
|
� Последнее редактирование: Июнь 18, 2010, 12:19:40 от MagTux �
|
Записан
|
Существует два правила на пути к успеху: 1. Не говори никому всего, что ты знаешь.
|
|
|
iPhonograph
Гений-Говорун
Offline
Сообщений: 2100
СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315
Дискоед
|
|
� Ответ #9 : Июнь 18, 2010, 01:09:10 � |
|
//текст доступен после регистрации//
|
|
|
Записан
|
"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
|
|
|
staison
Новенький
Offline
Сообщений: 8
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0
|
|
� Ответ #10 : Июнь 18, 2010, 11:55:35 � |
|
Воспользовался формулой неправильно. В решении получается n+1 слагаемое: Пусть N - число перестановок; N(a1),..,N(an) - число способов рассадки, когда 1..n - я пара сидит рядом N(a1,a2).... - -//- 1-я сидит рядом и 2-я сидит рядом ..... N(!a1,!a2,...,!an) = N - N(a1) - ... - N(an) + N(a1,a2) + ... + N(an-1, an) - ..... + (-1)^n *N(a1,...,an) - ответ N = (2n)! N(a1)=...=N(an)=2*2*n*(2n-2)! N(a1,a2)=...=N(an-1,an)=2*2^2*n*(n-1)*(2n -2*2)! ..... N(a1,...,ak)=N(an-k+1,....,an) = 2*2^k*n*(n-1)*...*(n-k+1)*(2n - 2*k)! = 2*2^k*(n!/(n-k)!)*(2n - 2*k)! N(a1,...,an)=2*2^n*n! Итого: N(!a1,!a2,...,!an) = N - (C из 1 по n)*N(a1) + (C из 2 по n)*N(a1,a2) - ... + (-1)^k (C из k по n)*N(a1,...,ak) + ... + (-1)^n* N(a1,...,an). Это число требуется разделить на (2n), чтобы учесть(?) циклический сдвиг. Дабы сверить ответ, решите плиз моим способом или докажите, что решение неверно. Другого способа решения не могу представить.
|
|
� Последнее редактирование: Июнь 18, 2010, 12:02:58 от staison �
|
Записан
|
|
|
|
MagTux
Гений-Говорун
Offline
Сообщений: 1415
СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99
Реинкарнация Будды
|
|
� Ответ #11 : Июнь 18, 2010, 12:19:05 � |
|
Вот накатал маткадик маленький по своему алгоритму. Судя по вышеприведённой таблице результаты верные. Суть алгоритма: функция f(n,k) считает количество расстановок из n пар элементов, когда только k пар вместе (k пар не разделены). Выражение 2k*(2n-k-1)! - количество возможных расстановок, когда k конкретных пар вместе. Далее по формуле вычитаются все комбинации, когда вместе пар больше k (исключаем повторения). Далее функция f2(n,k) вычисляет количество расстановок когда k любых пар вместе. Если в выражение 2k*(2n-k-1)! подставить k=0 (0 пар вместе), то получим (2n-1)! - общее количество всех возможных расстановок без циклических сдвигов. Далее по формуле вычитаются все комбинации с одной неразделённой парой, двумя и т.д. до n.
|
|
� Последнее редактирование: Июнь 20, 2010, 09:51:19 от MagTux �
|
Записан
|
Существует два правила на пути к успеху: 1. Не говори никому всего, что ты знаешь.
|
|
|
MagTux
Гений-Говорун
Offline
Сообщений: 1415
СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99
Реинкарнация Будды
|
|
� Ответ #12 : Июнь 18, 2010, 13:02:05 � |
|
N(!a1,!a2,...,!an) = N - (C из 1 по n)*N(a1) + (C из 2 по n)*N(a1,a2) - ... + (-1)^k (C из k по n)*N(a1,...,ak) + ... + (-1)^n* N(a1,...,an).
Мне непонятно с плюсами и минусами. Что-то прибавляется, что-то отнимается. Можешь прояснить этот момент?
|
|
|
Записан
|
Существует два правила на пути к успеху: 1. Не говори никому всего, что ты знаешь.
|
|
|
staison
Новенький
Offline
Сообщений: 8
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0
|
|
� Ответ #13 : Июнь 18, 2010, 23:28:41 � |
|
N(!a1,!a2,...,!an) = N - (C из 1 по n)*N(a1) + (C из 2 по n)*N(a1,a2) - ... + (-1)^k (C из k по n)*N(a1,...,ak) + ... + (-1)^n* N(a1,...,an).
Мне непонятно с плюсами и минусами. Что-то прибавляется, что-то отнимается. Можешь прояснить этот момент? По-моему ета формула(вкл/искл) очевидна . Нарисуй на бумаге или представь прямоугольник U - универсум. Пусть для определённости возьмём 3 множества (A,B,C) на U, обладающих какими-то свойсвами(пусть для общего случая они все пересекаются). Тогда размерность множества, не обладающее 3-мя свойствами вычисляется по фор-ле: см.выше. Если не понятно, возьми 2 множества. А в частности к задаче её надо применить, т.к достаточно сосчитать в конечном виде способы, когда пара(ы) сиди(я)т рядом, ну и общее кол-во перестановок; хотя пока-что не исключаю решения в простом виде.
|
|
� Последнее редактирование: Июнь 19, 2010, 00:01:51 от staison �
|
Записан
|
|
|
|
MagTux
Гений-Говорун
Offline
Сообщений: 1415
СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99
Реинкарнация Будды
|
|
� Ответ #14 : Июнь 19, 2010, 21:56:58 � |
|
2staison Верно. Формула правильная. Я к ней пришёл упрощая свою формулу. Но в твоем алгоритме неверно определены функции N(a1), N(a1,a2) и т.д. Вот маткадик. Считает верно.
|
|
|
Записан
|
Существует два правила на пути к успеху: 1. Не говори никому всего, что ты знаешь.
|
|
|
|