Изменения

|proof=Доказывать будем по индукции. Для <tex>n = 1\; - </tex> очевидно. Предположим, что для <tex>n - 1</tex> алгоритм строит перестановки корректно. Докажем, что алгоритм будет корректно строить перестановки и для <tex>n</tex> элементов. Разобём Разобьём все <tex>n!</tex> перестановок на блоки по <tex>n</tex>(Подрядподряд). В силу вышедоказанной леммы в каждом блоке <tex>P[i]\backslash\{n\} = P[i + 1]\backslash\{n\} = ... = P[i + n]\backslash\{n\}</tex>, если <tex>i\; - </tex> - начало группы. Значит , в каждой группе какая-то перестановка из <tex>n - 1</tex> элементов элемента дополняется до перестановки из <tex>n</tex> всеми возможными способами. Теперь докажем, что на переход между блоками , элемент <tex>n</tex> никак не влияет. Заметим, что при переходе между блоками <tex>n</tex> является неподвижным элементом. В силу нашего утверждения <tex>n</tex> стоит либо на первой, либо на последней позиции. Так как <tex>n</tex> больше любого элемента, то никакой подвижный элемент не может указывать на <tex>n</tex>. В силу этих фактов <tex>n</tex> никак не повлияет на переход между блоками.