Изменения

Перейти к: навигация, поиск

Участник:ZeRoGerc

10 байт добавлено, 20:36, 29 ноября 2014
Доказательство корректности
{{Лемма
|id=lemma1
|statement=Если в перестановке <tex>P[i]</tex> есть подвижный элемент <tex>a \neq n</tex> , то также определены перестановки <tex>P[i + 1] ... P[i + n]</tex> причём . Кроме того, <tex>P[i + 1]\backslash\{n\} = P[i + 2]\backslash\{n\} = ... = P[i + n]\backslash\{n\}</tex>.
|proof=Заметим, что если в перестановке есть подвижный элемент <tex>a \neq n</tex>, то после транспозиции его с соседним элемнтом(по направлению стрелки), нам нужно будет заменить направление стрелок у всех элементов больше <tex>a</tex>. Так как <tex>n</tex> больше любого элемента из перестановки, то направление стрелеки у него тоже изменится. По нашему утверждению либо в новой перестановке окажется компонента <tex>(n,</tex> →<tex>)</tex> на первой позиции, либо компонента <tex>(n,</tex> ←<tex>)</tex> на последней позиции. В обоих случаях <tex>n</tex> окажется подвижным элементом в следующих <tex>n</tex> перестановках. Так как в следующих <tex>n</tex> перестановках подвижным элементом будет только <tex>n</tex>, то <tex>P[i + 1]\backslash\{n\} = P[i + 2]\backslash\{n\} = ... = P[i + n]\backslash\{n\}</tex>.
}}
130
правок

Навигация