НГУ

Форумы НГУ
Текущее время: Чт фев 22, 2018 8:15 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 6 ] 
Автор Сообщение
СообщениеДобавлено: Сб мар 11, 2006 9:17 pm 
Не в сети
Редкий гость

Зарегистрирован: Сб мар 11, 2006 9:10 pm
Сообщения: 14
А может и не только комбинаторная. Но смотрите сами.

Две перестановки из n элементов \pi и \sigma назовем смежными, если они совпадают хотя бы по одному индексу: \exists i | \pi_i=\sigma_i.

Вопросы:
1. Каково наибольшее число попарно несмежных перестановок (в зависимости от n)?
2. Пусть даны k попарно несмежных перестановок. Сколько есть перестановок, не смежных ни с одной из данных?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс мар 12, 2006 10:01 pm 
Не в сети
Постоянный посетитель

Зарегистрирован: Вс июл 10, 2005 10:14 pm
Сообщения: 165
Откуда: Стас Минскер
А в чем собственно вопрос?
1. Очевидно их не более чем N, то есть ровно N ;)
2. N-k


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн мар 13, 2006 3:35 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Вс ноя 21, 2004 6:01 pm
Сообщения: 1944
Извилин писал(а):
2. N-k

Нет, конечно. Перестановки, не смежные ни с одной из данных k штук, вполне могут оказаться смежными друг с другом. Их больше.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн мар 13, 2006 9:14 am 
Не в сети
Редкий гость

Зарегистрирован: Сб мар 11, 2006 9:10 pm
Сообщения: 14
Извилин писал(а):
А в чем собственно вопрос?
1. Очевидно их не более чем N, то есть ровно N ;)
2. N-k


Да, действительно, первый вопрос тривиальный. :)
Но второй не такой простой.
При k=1 ответ не такой уж и сложный, как-то раз я его уже вывел.
Но для k=2 у меня уже ничего не получилось.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн мар 13, 2006 9:47 pm 
Не в сети
Постоянный посетитель

Зарегистрирован: Вс июл 10, 2005 10:14 pm
Сообщения: 165
Откуда: Стас Минскер
Да, я невнимательно прочитал условие. Ответ ко второму пункту неоднозначен, все зависит от конкретного вида перестановок, в частности просто построить пример когда ответ будет 0 или не 0 для одного и того же K.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн мар 13, 2006 10:22 pm 
Не в сети
Редкий гость

Зарегистрирован: Сб мар 11, 2006 9:10 pm
Сообщения: 14
Извилин писал(а):
Ответ ко второму пункту неоднозначен, все зависит от конкретного вида перестановок, в частности просто построить пример когда ответ будет 0 или не 0 для одного и того же K.


Да, у меня было подозрение, что тут нет однозначности, но на пример все же хотелось бы посмотреть.

Если это так, то вопрос трансформируется в следующий: сколько существует наборов из k попарно несмежных перестановок?


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: Google [Bot] и гости: 30


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB