Форум умных людей

Задачи и головоломки => Помогите решить! => Тема начата: Илья от Июнь 16, 2010, 22:07:22



Название: Пары
Отправлено: Илья от Июнь 16, 2010, 22:07:22
Имеется n супружеских пар. Сколькими способами их можно рассадить за столом так, чтобы каждая пара сидела раздельно?


Название: Re: Пары
Отправлено: staison от Июнь 17, 2010, 12:48:24
(2n)! - 2*n!

Формула вкл/искл. По-моему так.


Название: Re: Пары
Отправлено: MagTux от Июнь 17, 2010, 14:06:01
(2n)! - 2*n!
Формула вкл/искл. По-моему так.

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

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


Название: Re: Пары
Отправлено: staison от Июнь 17, 2010, 15:14:35
(2n)! - 2*n!
Формула вкл/искл. По-моему так.

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

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

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


Название: Re: Пары
Отправлено: staison от Июнь 17, 2010, 17:19:04
1. Если считать важными места, а не соседей, то будет x = (2n)! - 2*2*n!
2. Иначе(т.е учесть циклич. сдвиг и симметрию) x = ((2n)! - 2*2n!)/2*(2n)
2. n = 2, x = 2

Идея проста - формула вкл/искл.
Ну прям не знаю, если это неправильно :roll:


Название: Re: Пары
Отправлено: Илья от Июнь 17, 2010, 17:31:03
Цитировать
Требуется уточнить условие:
1) оказывается стол круглый
2) какие способы являются различными
 

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


Название: Re: Пары
Отправлено: staison от Июнь 17, 2010, 17:41:37
Если я правильно понял, cпособы считаются одинаковыми, если у чел-ка одинаковые соседи в обоих случаях. И ответ в этом случае см.п2(выше)


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

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

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


Название: Re: Пары
Отправлено: MagTux от Июнь 18, 2010, 00:50:50
Для 3 пар это 32 варианта
Для 4 - 1488
Для 5 - 112512
могу дальше посчитать

В формуле должно быть 2n. Остальное пока гадаю.
Посчитал написанной программой.


Название: Re: Пары
Отправлено: iPhonograph от Июнь 18, 2010, 01:09:10
http://www.research.att.com/~njas/sequences/b129348.txt


Название: Re: Пары
Отправлено: staison от Июнь 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), чтобы учесть(?) циклический сдвиг.
Дабы сверить ответ, решите плиз моим способом или докажите, что решение неверно.
Другого способа решения не могу представить.


Название: Re: Пары
Отправлено: MagTux от Июнь 18, 2010, 12:19:05
Вот накатал маткадик маленький по своему алгоритму.
(http://img46.imageshack.us/img46/4522/80743822.jpg)
Судя по вышеприведённой таблице результаты верные.

Суть алгоритма:
функция 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.


Название: Re: Пары
Отправлено: MagTux от Июнь 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).

Мне непонятно с плюсами и минусами. Что-то прибавляется, что-то отнимается. Можешь прояснить этот момент?


Название: Re: Пары
Отправлено: staison от Июнь 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 множества.
А в частности к задаче её надо применить, т.к достаточно сосчитать в конечном виде способы, когда пара(ы) сиди(я)т рядом, ну и общее кол-во перестановок; хотя пока-что не исключаю решения в простом виде.


Название: Re: Пары
Отправлено: MagTux от Июнь 19, 2010, 21:56:58
2staison
Верно. Формула правильная. Я к ней пришёл упрощая свою формулу. Но в твоем алгоритме неверно определены функции N(a1), N(a1,a2) и т.д.
Вот маткадик. Считает верно.
(http://img707.imageshack.us/img707/7382/81172920.jpg)


Название: Re: Пары
Отправлено: staison от Июнь 19, 2010, 23:43:40
Выражение 2k*(2n-k-1) - количество возможных расстановок, когда k конкретных пар вместе.
Объясни как так :read:, только не говори, что это твой любимый мадкадик посчитал.


Название: Re: Пары
Отправлено: MagTux от Июнь 20, 2010, 09:38:54
2staison
Нет не маткадик. Сам посчитал.

Поскольку пары слитные, то их в перестановках надо считать одним элементом.
Когда k пар вместе, тогда внутри пар будет 2k перестановок, а взаимных перестановок пар с оставшимися элементами будет (2n-k)! - из общего количества элементов отнимаем по одному элементу из слитных пар. Без учёта циклов это будет (2n-k)!/2n-k=(2n-k-1)!
Итого будет 2k(2n-k-1)!

В моём объяснении были пропущены факториалы. Поправил.

И ещё: "мой любимый маткадик" формул никаких не выводит. Он лишь считает. С его помощью я проверял результаты. А в моих алгоритмах всё выведено на тетрадном листке в клеточку.


Название: Re: Пары
Отправлено: staison от Июнь 20, 2010, 11:42:10
а взаимных перестановок пар с оставшимися элементами будет (2n-k)! - из общего количества элементов отнимаем по одному элементу из слитных пар.
Вот ето непонятно, никселуникгороду. :no2:

Объясню мою логику:
для k пар, каждая пара сидящит вместе. На низком уровне: пусть зафиксируем 2 рядом стоящие места. Тогда 1-ую пару можно посадить на n мест, с учётом перестановки в паре : 2*n. Далее берём 2-ую пару. Её можно рассадить на n-1 место, аналогично, с учётом перестановки в паре получим (2*n*)*(2*(n-1)) - работает правило произведения(очевидно). И т. д. берём k-ую пару, получим 2*n*2*(n-1)*2*(n-2)*...*2*(n-k+1) и ещё требуется учесть перестановку оставшихся людей за столом(умножить на (2n - 2k)! - 2n - всего, 2k - в парах). Также ето нужно умножить на 2, т.к зафиксировать начальные места для 1-ой пары можно 2-мя способами(т.е. её можно просто сместить циклически на 1 позицию). В итоге, всего получим 2*2k*n*(n-1)*...*(n-k+1)*(2n-2k)!, где n*(n-1)*...*(n-k+1) = n!/(n-k)!. С учётом циклического сдвига разделим на (2n) - всего одиночных мест.


Название: Re: Пары
Отправлено: MagTux от Июнь 20, 2010, 14:49:26
Вот ето непонятно, никселуникгороду. :no2:

Например, из 5 пар 2 сидит вместе (1-я и 2-я). Тогда

(11`) (22`) 3  3` 4  4` 5  5` - всего 8 (2n-k) элементов. Рассадить их можно 8! (2n-k)! способами. Без цикличности 7! (2n-k-1)! способами. Перестановки внутри двух пар - 22 (2k). Итого всего вариантов 22*7! (2k(2n-k-1)!)
Так понятно?


Название: Re: Пары
Отправлено: MagTux от Июнь 20, 2010, 15:05:36
>>1-ую пару можно посадить на n мест
>>Далее берём 2-ую пару. Её можно рассадить на n-1 место

Первую пару можно посадить 2n способами (без перестановки внутри).
Пример (n=3):
(11`) x x x x
x (11`) x x x
x x (11`) x x
x x x (11`) x
x x x x (11`)
1`) x x x x x (1
Вторую - 2n-3 способами (без перестановок внутри).
(11`) (22`) x x
(11`) x (22`) x
(11`) x x (22`)
А третюю пару посчитать нельзя, поскольку количество вариантов зависит от того, как расположена 1 и 2 пары.
Пример,
(11`) (22`) x x - для 3-й пары 1 вариант
(11`) x (22`) x - для 3-й пары 0 вариантов

Поэтому ваш вариант, по моему мнению, неверен.


Название: Re: Пары
Отправлено: MagTux от Июнь 20, 2010, 15:10:07
2staison
И ещё (пардон, что пишу разными постами).
Для n=3 ваш алгоритм даёт 8 вариантов, а мой 32. Если хотите, я могу все 32 варианта запостить сюда.


Название: Re: Пары
Отправлено: Time от Июль 01, 2010, 10:00:42
n раз :read: :read: :read: