Пермутации на окръжност

[Davids]

Върху окръжност по посока на часовниковата стрелка са записани последователно естествените числа от $1$ до $2n$. Нека $f$ е следното действие: избираме три последователни числа и разменяме местата на двете крайни. Една пермутация на числата $1, 2 , ..., 2n$ ще наричаме „достижима“, ако тя може да се получи от първоначалната след краен брой прилагания на $f$. Да се намери броят на всички „достижими“ пермутации на числата $1, 2 , ..., 2n$.

[ptj]

Не е ли преклено лесна за състезания?
Дадената операция може да се формулира като "субституция по четност", а отговора би трябвало да е [tex](n!)^2[/tex].

[ABK]

Ще наричаме k-та „позиция” мястото върху окръжността, което първоначално (преди първото прилагане на f) се зaема от числото k, k = 1, 2, . . . , 2n.

Когато приложим f върху числата, които се намират на позиции k, k + 1 и k + 2 (2n + 1 ≡ 1, 2n + 2 ≡ 2), числото, което се намира на позиция k + 1 запазва позицията си, а числата, които се намират на позиции k и k + 2 се разменят. Следователно, четността на позицията на всяко число е инвариант – след всяко прилагане на f числата, които са на четни позиции остават на четни, а тези, които са на нечетни остават на нечетни.

Първоначално всички нечетни числа са на нечетни позиции и всички четни – на четни и следователно във всяка „достижима” подредба това свойство трябва да бъде запазено.

Има n! на брой начини, по които нечетните числа могат да се разположат на нечетните позиции и n! на брой начини, по които четните числа могат да се разположат на четните позиции. Следователно всички числа могат да се разположат по [tex](n!)^{2}[/tex] на брой начини върху окръжността (но това все още не означава, че конкретната подредба може да се получи от първоначална, чрез краен брой прилагания на f).

За да докажем, че всяка подредба, при която нечетните числа са на нечетни позици, а четните – на четни може да бъде получена от първоначалната, е достатъчно да докажем, че за всеки k и m, числатa, които се намират на позиции k и k + 2m (1 ≤ k < k + 2m ≤ 2n) могат да бъдат разменени, при което всички останали числа запазват позицията си. Това означава, че от първоначалната позиция числото 1 може да бъде „преместено” на произволна нечетна позиция, 2 – на произволна четна, 3 – на произволна нечетна незаета от 1 и т.н.

Това може да бъде постигнато като първо приложим m пъти f, при което последователно разменяме числата на позиции k и k + 2, k + 2 и k + 4 и т.н. k + 2m – 2 и k + 2m, след което прилагаме m – 1 пъти f, като последователно разменяме числата на позиции k + 2m – 2 и k + 2m – 4, k + 2m – 4 и k + 2m – 6 и т.н. k + 2 и k.

Например,
a _ b _ c _ d _ e _ f
b _ a _ c _ d _ e _ f
b _ c _ a _ d _ e _ f
b _ c _ d _ a _ e _ f
b _ c _ d _ e _ a _ f
b _ c _ d _ e _ f _ a

b _ c _ d _ f _ e _ a
b _ c _ f _ d _ e _ a
b _ f _ c _ d _ e _ a
f _ b _ c _ d _ e _ a.

P.S. При условие, че е от значение само подредбата на числата едно спрямо друго, а не и позицията, която заемат (т.е. две подредби, при които 1 се намира на различни нечетни позиции, но числата след 1 по посока на часовниковата стрелка са подредени по един и същи начин се смятат за една „достижима” пермутация) – отговорът е [tex]\frac{(n!)^{2}}{n}[/tex].

[Davids]

Двамата очертахте точно раздвоението в разсъжденията ми, което ме накара да я кача. Принципно съм съгласен с втората теза, но за отговор от комисията на НМС са дали първия (на pal). Сега нямах време да се задълбоча, но принципно още ми е чудно

[ptj]

P.S. При условие, че е от значение само подредбата на числата едно спрямо друго, а не и позицията, която заемат (т.е. две подредби, при които 1 се намира на различни нечетни позиции, но числата след 1 по посока на часовниковата стрелка са подредени по един и същи начин се смятат за една „достижима” пермутация) – отговорът е [tex]\frac{(n!)^{2}}{n}[/tex].

Разбирам какво си написал, но принципно така "изяждаш" пермутации.
Пример :
(1,2,3,4,5), (2,3,4,5,1),(3,4,5,1,2), (4,5,1,2,3) и (5,1,2,3,4) са 5 различни пермутации, докато според твоите разсъждения те са една и съща пермутация.

[Davids]

Само че именно тук не е ли от значение факторът, че са пермутации, наредени не в права линия, а в кръг. На практика са една и съща кръгова подредба. Само от условието не става ясно позициите дали играят роля и дефинират „различни“ подредби или не, но според мен на самият кръг точно това му е ключовото в задачата, да елиминира тези пермутации като една.

[ptj]

Термина пермутация е еднозначен, а кръга от условието има роля най-вече в разделянето по четност.