Страниц: [1] 2
  Печать  
Автор Тема: Пары  (Прочитано 13862 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
: Июнь 16, 2010, 22:07:22 �

Имеется n супружеских пар. Сколькими способами их можно рассадить за столом так, чтобы каждая пара сидела раздельно?
Записан

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
staison
Новенький
*
Offline Offline

Сообщений: 8

СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0


Просмотр профиля
Ответ #1 : Июнь 17, 2010, 12:48:24 �

(2n)! - 2*n!

Формула вкл/искл. По-моему так.
Записан
MagTux
Гений-Говорун
*
Offline Offline

Сообщений: 1415

СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99


Реинкарнация Будды


Просмотр профиля
Ответ #2 : Июнь 17, 2010, 14:06:01 �

(2n)! - 2*n!
Формула вкл/искл. По-моему так.

Для двух пар получается (2*2)!-2*2!=20 вариантов вместо двух.

Тут всё сложнее. У меня без циклов не выходит.
Записан

Существует два правила на пути к успеху:
1. Не говори никому всего, что ты знаешь.
staison
Новенький
*
Offline Offline

Сообщений: 8

СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0


Просмотр профиля
Ответ #3 : Июнь 17, 2010, 15:14:35 �

(2n)! - 2*n!
Формула вкл/искл. По-моему так.

Для двух пар получается (2*2)!-2*2!=20 вариантов вместо двух.

Тут всё сложнее. У меня без циклов не выходит.

Требуется уточнить условие:
1) оказывается стол круглый
2) какие способы являются различными
Записан
staison
Новенький
*
Offline 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

Идея проста - формула вкл/искл.
Ну прям не знаю, если это неправильно Roll Eyes
Записан
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
Ответ #5 : Июнь 17, 2010, 17:31:03 �

Цитировать
Требуется уточнить условие:
1) оказывается стол круглый
2) какие способы являются различными
 

1. Да, стол круглый. Smiley
2. Допустим у нас две пары 1-2, 3-4, тогда возможны такие расположения, отвечающие условию 1423, 4132.
Последнее редактирование: Июнь 17, 2010, 17:41:47 от Илья Записан

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
staison
Новенький
*
Offline Offline

Сообщений: 8

СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0


Просмотр профиля
Ответ #6 : Июнь 17, 2010, 17:41:37 �

Если я правильно понял, cпособы считаются одинаковыми, если у чел-ка одинаковые соседи в обоих случаях. И ответ в этом случае см.п2(выше)
Последнее редактирование: Июнь 17, 2010, 20:30:34 от staison Записан
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
Ответ #7 : Июнь 17, 2010, 17:44:23 �

Исправил:
Цитировать
2. Допустим у нас две пары 1-2, 3-4, тогда возможны такие расположения, отвечающие условию 1423, 4132.

Цитировать
1324, 3142

Эти два примера будут аналогичны первым двум.
Записан

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
MagTux
Гений-Говорун
*
Offline 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 Offline

Сообщений: 2100

СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315

Дискоед


Просмотр профиля
Ответ #9 : Июнь 18, 2010, 01:09:10 �

//текст доступен после регистрации//
Записан

"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
staison
Новенький
*
Offline 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 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 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 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).

Мне непонятно с плюсами и минусами. Что-то прибавляется, что-то отнимается. Можешь прояснить этот момент?
По-моему ета формула(вкл/искл) очевидна Wink. Нарисуй на бумаге или представь прямоугольник U - универсум. Пусть для определённости возьмём 3 множества (A,B,C) на U,  обладающих какими-то свойсвами(пусть для общего случая они все пересекаются). Тогда размерность множества, не обладающее 3-мя свойствами вычисляется по фор-ле: см.выше. Если не понятно, возьми 2 множества.
А в частности к задаче её надо применить, т.к достаточно сосчитать в конечном виде способы, когда пара(ы) сиди(я)т рядом, ну и общее кол-во перестановок; хотя пока-что не исключаю решения в простом виде.
Последнее редактирование: Июнь 19, 2010, 00:01:51 от staison Записан
MagTux
Гений-Говорун
*
Offline Offline

Сообщений: 1415

СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99


Реинкарнация Будды


Просмотр профиля
Ответ #14 : Июнь 19, 2010, 21:56:58 �

2staison
Верно. Формула правильная. Я к ней пришёл упрощая свою формулу. Но в твоем алгоритме неверно определены функции N(a1), N(a1,a2) и т.д.
Вот маткадик. Считает верно.
Записан

Существует два правила на пути к успеху:
1. Не говори никому всего, что ты знаешь.
Страниц: [1] 2
  Печать  
 
Перейти в: