Пермутации задача

[Гост]

Нека n ∈ N \ {0, 1}. Нека Sn е множеството от пермутациите на числата
1, 2, . . . , n. Ако π1, π2 ∈ Sn са пермутации, казваме, че π1 се получава от π2 чрез
транспозиция, ако π1 се получава от π2 чрез размяна на точно две числа. Примерно,
ако n = 5 и
π1 = 2 1 3 4 5
π2 = 4 1 3 2 5
π3 = 1 4 3 2 5
то π1 се получава от π2 чрез транспозиция (също така е вярно, че π2 се получава от
π1 чрез транспозиция) и π2 се получава от π3 чрез транспозиция, но не е вярно, че
π1 се получава от π3 чрез транспозиция.
Докажете или опровергайте, че за всяко n ≥ 2, за всеки две различни пермутации
π', π" ∈ Sn е вярно, че π'
се получава от π" чрез серия от транспозиции.

[peyo]

Нека n ∈ N \ {0, 1}

Това какво означава, специално 0,1 частта?

Докажете или опровергайте, че за всяко n ≥ 2, за всеки две различни пермутации
π', π" ∈ Sn е вярно, че π'
се получава от π" чрез серия от транспозиции.

Да вземем транспозицията където заменяме местата на две съседни числа. Тази операция е идинствената използвана в метода за сортиране на мехурчето.

Метода на мехурчето въпреки смешното си име си е истински метод за сортиране и работи абсолютно надежно в 100% от случаите. Сортираната редица е просто еднa от възможните $n!$ пермутации и ние стигаме до тази сортирана пермутация след краен брой операции (около $n^2$) независимо от каква начална пермутация тръгваме. Значи с операцията мехурче (което е транспоцизия) можем да стигнем от всяка начална пермутация до всяка крайна пермутация, с което задачата е решена.