130
правок
Изменения
→Доказательство корректности
|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> больше любого элемента из перестановки, то направление стрелеки у него тоже изменится. По нашему утверждению
}}
