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