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

Сообщений: 8

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


Просмотр профиля
Ответ #15 : Июнь 19, 2010, 23:43:40 �

Выражение 2k*(2n-k-1) - количество возможных расстановок, когда k конкретных пар вместе.
Объясни как так Чтение, только не говори, что это твой любимый мадкадик посчитал.
Записан
MagTux
Гений-Говорун
*
Offline Offline

Сообщений: 1415

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


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


Просмотр профиля
Ответ #16 : Июнь 20, 2010, 09:38:54 �

2staison
Нет не маткадик. Сам посчитал.

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

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

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

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

Сообщений: 8

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


Просмотр профиля
Ответ #17 : Июнь 20, 2010, 11:42:10 �

а взаимных перестановок пар с оставшимися элементами будет (2n-k)! - из общего количества элементов отнимаем по одному элементу из слитных пар.
Вот ето непонятно, никселуникгороду. Нет

Объясню мою логику:
для 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) - всего одиночных мест.
Записан
MagTux
Гений-Говорун
*
Offline Offline

Сообщений: 1415

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


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


Просмотр профиля
Ответ #18 : Июнь 20, 2010, 14:49:26 �

Вот ето непонятно, никселуникгороду. Нет

Например, из 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)!)
Так понятно?
Записан

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

Сообщений: 1415

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


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


Просмотр профиля
Ответ #19 : Июнь 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 вариантов

Поэтому ваш вариант, по моему мнению, неверен.
Последнее редактирование: Июнь 20, 2010, 15:11:28 от MagTux Записан

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

Сообщений: 1415

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


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


Просмотр профиля
Ответ #20 : Июнь 20, 2010, 15:10:07 �

2staison
И ещё (пардон, что пишу разными постами).
Для n=3 ваш алгоритм даёт 8 вариантов, а мой 32. Если хотите, я могу все 32 варианта запостить сюда.
Записан

Существует два правила на пути к успеху:
1. Не говори никому всего, что ты знаешь.
Time
Гость
Ответ #21 : Июль 01, 2010, 10:00:42 �

n раз Чтение Чтение Чтение
Записан
Страниц: 1 [2]
  Печать  
 
Перейти в: