Докажите, что любую подстановку можно представить в виде произведения транспозиций вида (i, i+1) (переставляющих соседние элементы ) задан 19 Окт '17 14:24 Мэт |
Возможно такое "наглядное" доказательство. Если на полке стоят 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 Окт '17 16:18 falcao |