Даны натуральные числа $%n, k$%. Требуется найти порядок и чётность перестановки в $%S_n$%, в которой элемент $%i$% переходит в элемент $%i+k$% по модулю $%n$% (переставляемые элементы$%~-~$%остатки по модулю $%n$%).

задан 27 Май '15 0:02

10|600 символов нужно символов осталось
1

Если порядок равен $%m$%, то после применения подстановки $%m$% раз, к каждому элементу прибавляется $%km$%, и подстановка становится тождественной. Это значит, что $%km$% кратно $%n$%, где $%m$% -- наименьшее натуральное с таким свойством.

Положим $%d={\mathrm НОД}(k,n)$%. При этом $%k=dk_1$%, $%n=dn_1$%, и числа $%k_1$%, $%n_1$% взаимно просты. Условие делимости $%km=dk_1m$% на $%n=dn_1$% равносильно делимости $%k_1m$% на $%n_1$%, а потому и делимости $%m$% на $%n_1$%, с учётом взаимной простоты. Наименьшее натуральное число с таким свойством -- это $%n_1$%. Поэтому $%m=n_1=\frac{n}d =\frac{n}{\mathrm НОД(k,n)}$%.

С чётностью дело обстоит так. Легко заметить, что рассматриваемая подстановка является $%k$%-й степенью цикла $%(12\ldots n)$%. Если $%k$% чётно, то получится чётная подстановка для любого $%n$%. Если $%k$% нечётно, что степень будет иметь ту же чётность, что и цикл. Легко видеть, что цикл нечётен при чётном $%n$% и наоборот. Поэтому подстановка из условия нечётна тогда и только тогда, когда $%k$% нечётно, а $%n$% чётно.

ссылка

отвечен 27 Май '15 0:13

@falcao, можете, пожалуйста, объяснить подробнее, почему при чётном $%k$% подстановка получается чётной для любого $%n$%?

(27 Май '15 0:41) Poncho

@Poncho: здесь действуют простые правила ЧЧ=Ч, ЧН=НЧ=Н, НН=Ч. Поэтому квадрат любой постановки чётен.

(27 Май '15 1:00) falcao

Ясно, число транспозиций будет чётным, спасибо.

(27 Май '15 9:41) Poncho
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×730
×308

задан
27 Май '15 0:02

показан
232 раза

обновлен
27 Май '15 9:48

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru