Помогите разобраться, как определить четность перестановки.

[PetrP]

Добрый день!
Помогите разобраться, как определить четность перестановки.

$$\begin{pmatrix} 1 & 2 & 3 & ... & ...& ...& ...& ...& n-1 & n\\ 2 & 4 & 6 & ... & 1 & 3 & 5 & ... & ... & ... \end{pmatrix}$$

[AV_77]

По определению - посчитать число инверсий в нижней строке. Это не так сложно. Например, 2 образует 1 инверсию, 4 - две и т.д.

[mihailm]

или скажите сколько нужно транспозиций чтобы поставить 1 перед двойкой, потом 3 перед 4 и т.д.

[PetrP]

AV_77 в сообщении #588433 писал(а):

По определению - посчитать число инверсий в нижней строке. Это не так сложно. Например, 2 образует 1 инверсию, 4 - две и т.д.

Рассуждаю следующим образом:
В нижней строке сначала перечисляются все четные элементы, затем все нечетные, тогда при $n$ равном $12$:
$\setcounter{MaxMatrixCols}{20}\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ 2 & 4 & 6 & 8 & 10 & 12 & 1 & 3 & 5 & 7 & 9 & 11 \end{pmatrix}$

Теперь подсчитываем число инверсий:
Для $1$: $2 > 1$, $1$ инверсия
Для $2$: $4 > 1$ и $3$, $2$ инверсии
...
Для $n/2$ соответственно $n/2$ инверсий.
Сумма всех инверсий это арифметическая прогрессия от $1 \ 2 \ ... \ n/2$
Сумма элементов арифметической прогрессии: $(1+n/2)n/4 = (2\cdot n + n^2)/8

Соответственно знак перестановки равен $(-1)$ в степени $(2\cdot n+n^2)/8$

Хотя ответ равен $(n+2)/2$

[mihailm]

для начала повторите что такое инверсия что ли

[ewert]

PetrP в сообщении #588484 писал(а):

Хотя ответ равен $(n+2)/2$

Этот "ответ" не может быть верен ни в каком смысле.

Ясно, что переход от чётного $n=2k$ к нечётному $n=2k+1$ никогда не меняет чётности перестановки. А переход от нечётного $n=2k-1$ к чётному $n=2k$ меняет чётность перестановки на противоположную тогда и только тогда, когда $k$ нечётно. Т.е. чётности перестановок (начиная с $n=2$) идут четвёрками:

$- - - - + + + + - - - - + + + + - - - - + + + + - - - - + + + + ...$

[PetrP]

mihailm в сообщении #588492 писал(а):

для начала повторите что такое инверсия что ли

Инверсией в перестановке $\pi$ порядка n называется всякая пара $i, j$ такая, что $1 \leqslant i \leqslant j \leqslant n$ и $\pi(i)>\pi(j)$

Так для $i = 1$ подходят все $j$, которые больше 1, $\pi(1) = 2$, соответственно 2 больше $\pi(8) = 1$, значит для 1 одна инверсия.

Я рассуждал так, подскажите, где я ошибаюсь.

[xolodec]

Пусть, $n = 2p$ или $n = 2p + 1$ .
Тогда, если я не ошибся, то количество инверсий можно определить, как $k = \frac{(p+1)p}{2}$, что похоже на ваш результат, но учитывает четность и нечетность $n$.
А четность можно будет определить, как $\varepsilon_\pi = (-1)^k$
А почему

PetrP в сообщении #588484 писал(а):

Хотя ответ равен $(n+2)/2$

я теряюсь в догадках.

[ewert]

xolodec в сообщении #1007513 писал(а):

А четность можно будет определить, как $\varepsilon_\pi = (-1)^k$

Конечно. Но можно чуть-чуть ещё обнаглеть и сказать, что $\varepsilon_\pi = (-1)^{\frac{n^4+2n^3-n^2-2n}{8}}$

[xolodec]

ewert в сообщении #1007599 писал(а):

Но можно чуть-чуть ещё обнаглеть и сказать, что $\varepsilon_\pi = (-1)^{\frac{n^4+2n^3-n^2-2n}{8}}$

А можно поинтересоваться, а как эта кракозяба в степени $(-1)$ получилась? Откуда взялась 4 степень $n$?
Я тоже хотел бы научиться так "наглеть"

[arseniiv]

Такую простую последовательность как

ewert в сообщении #588506 писал(а):

$- - - - + + + + - - - - + + + + - - - - + + + + - - - - + + + + ...$

записывать в виде

ewert в сообщении #1007599 писал(а):

$\varepsilon_\pi = (-1)^{\frac{n^4+2n^3-n^2-2n}{8}}$

это, по-моему, кощунство.
$(-1)^{\lfloor n/4\rfloor + k}$ — и хватит с неё.

[ewert]

arseniiv в сообщении #1007655 писал(а):

это, по-моему, кощунство.

Не передёргивайте. Это не кощунство, а наглость.

xolodec в сообщении #1007651 писал(а):

А можно поинтересоваться, а как эта кракозяба в степени $(-1)$ получилась? Откуда взялась 4 степень $n$?

Очень просто. Среди натуральных чисел делящиеся на 8 встречаются лишь в каждом восьмом случае. А делящиеся на 2 и на (4 или 8) -- по одному в каждой четвёрке соседних. Соответственно, выражение $\frac{(n-1)n(n+1)(n+2)}{8}$ обеспечивает ровно требуемую чётность.

Естественно, это было не более чем баловство.

[arseniiv]

(Оффтоп)

ewert в сообщении #1007711 писал(а):

Это не кощунство, а наглость.

А кощунством тогда какое представление будет? (Хотя бы менее длинное или более?)

[ewert]

(Оффтоп)

arseniiv в сообщении #1007713 писал(а):

А кощунством тогда какое представление будет?

Это к СК, я в этом не разбираюсь

[xolodec]

ewert в сообщении #1007711 писал(а):

выражение $\frac{(n-1)n(n+1)(n+2)}{8}$ обеспечивает ровно требуемую чётность.

Спасибо большое! Я, правда, так и не понял, как вы его сконструировали, но все равно спасибо за ответ!