Докажите, что любую подстановку можно представить в виде произведения транспозиций вида (i, i+1) (переставляющих соседние элементы )

задан 19 Окт 14:24

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

Возможно такое "наглядное" доказательство. Если на полке стоят n томов энциклопедии в каком-то порядке, то их можно расставить по порядку, меняя местами несколько раз два рядом стоящих тома.

А вот более формальное рассуждение. Всякая подстановка есть произведение независимых циклов, поэтому доказываемое утверждение сводится к случаю цикла. Для подстановки (abc...z) непосредственно проверяется, что она равна произведению транспозиций (ab)(ac)...(az). Тем самым, всё свелось к случаю транспозиции. Рассматривая случай (ij), где i < j, проверяем, что данная транспозиция равна произведению (i,i+1)(i+1,i+2)...(j-1,j)(j-1,j-2)...(i+1,i).

Последнее равенство имеет такую наглядную интерпретацию: если надо переставить местами i-й и j-й тома, то сначала придвигаем i-й том к j-му, меняя его местами со следующими. Затем меняем местами i-й и j-й, после чего j-й том придвигаем к первому месту, меняя его последовательно со всеми предыдущими.

ссылка

отвечен 19 Окт 16:18

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,411
×849
×277

задан
19 Окт 14:24

показан
51 раз

обновлен
19 Окт 16:18

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

по почте:

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

по RSS:

Ответы

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

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