Перестановки и число инверсий

[Профессор Снэйп]

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

Нет, а Вы всё-таки аккуратно выпишите, почему это очевидно. Мы ж вроде математикой занимаемся, а не чем попало!

Ох...

Пусть $A_1 = \{ \langle i,j \rangle : 1 \leqslant i < j \leqslant n \}$, $A_2 = \{ \langle j,i \rangle : \langle i,j \rangle \in A_1 \}$. Произвольная $\delta \in S_n$ действует на $A_1 \cup A_2$, сопоставляя паре $\langle x,y \rangle$ пару $\langle \delta(x), \delta(y) \rangle$. Число инверсий $\delta$ равно $| A_2 \cap \delta(A_1) |$. Так как $\tau(A_2) = \sigma(A_1)$, то $A_2 \cap \sigma(A_1) = A_2 \setminus \tau(A_1)$.

[e7e5]

Профессор Снэйп в сообщении #353677 писал(а):

А в задаче спрашивается, как выражается число инверсий перестановки $\tau(i) = \sigma(n - i + 1)$ через число инверсий перестановки $\sigma$. Очевидно, что сумма этих чисел равна $n(n-1)/2$.

$\tau(i) = \sigma(n - i + 1)$ - в ваших обозначениях мне это понятно. А вот далее, что Вам очевидно, мне нет. Пожалуйста поясните.

-- Сб сен 18, 2010 13:23:37 --

Профессор Снэйп в сообщении #353693 писал(а):

Пусть $A_1 = \{ \langle i,j \rangle : 1 \leqslant i < j \leqslant n \}$, $A_2 = \{ \langle j,i \rangle : \langle i,j \rangle \in A_1 \}$. Произвольная $\delta \in S_n$ действует на $A_1 \cup A_2$, сопоставляя паре $\langle x,y \rangle$ пару $\langle \delta(x), \delta(y) \rangle$. Число инверсий $\delta$ равно $| A_2 \cap \delta(A_1) |$. Так как $\tau(A_2) = \sigma(A_1)$, то $A_2 \cap \sigma(A_1) = A_2 \setminus \tau(A_1)$.

Пожалуйста и это разъясните. Как ответ получается итоговый по вашим рассуждениям?

В задачанике ответ $\frac {n(n-1)} {2} -k$

[ewert]

(Оффтоп)

Профессор Снэйп в сообщении #353693 писал(а):

Пусть $A_1 = \{ \langle i,j \rangle : 1 \leqslant i < j \leqslant n \}$, $A_2 = \{ \langle j,i \rangle : \langle i,j \rangle \in A_1 \}$. Произвольная $\delta \in S_n$ действует на $A_1 \cup A_2$, сопоставляя паре $\langle x,y \rangle$ пару $\langle \delta(x), \delta(y) \rangle$. Число инверсий $\delta$ равно $| A_2 \cap \delta(A_1) |$. Так как $\tau(A_2) = \sigma(A_1)$, то $A_2 \cap \sigma(A_1) = A_2 \setminus \tau(A_1)$.

А-бал-деть!

Однако же "$\tau(A_2) = \sigma(A_1)$" -- всё-таки не доказано. Неаккуратно.

[Профессор Снэйп]

$\tau = \sigma \circ \varepsilon$, где $\varepsilon(i) = n-i+1$ при любом $i \in \{ 1, \ldots, n \}$. Значит, $\tau(A_2) = \sigma(\varepsilon(A_2)) = \sigma(A_1)$, ибо $\varepsilon(A_2) = A_1$.

[ewert]

(Оффтоп)

Профессор Снэйп в сообщении #353716 писал(а):

$\varepsilon(A_2) = A_1$.

Не доказано. Всё ещё неаккуратно.

[Профессор Снэйп]

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

Не доказано. Всё ещё неаккуратно.

А что тут неаккуратного? $\langle x,y \rangle \in A_2 \Leftrightarrow \langle \varepsilon(x), \varepsilon(y) \rangle \in A_1$. Это тоже доказывать?

[ewert]

(Оффтоп)

Профессор Снэйп в сообщении #353723 писал(а):

Это тоже доказывать?

Обязательно.

Потом нужно будет собрать всё вместе и отослать в журнал.

Кстати: а Вы можете так же аккуратно, строго и вдумчиво доказать, что $2\times2=4$?...

[Профессор Снэйп]

e7e5 в сообщении #353698 писал(а):

Как ответ получается итоговый по вашим рассуждениям?

Число инверсий перестановки $\sigma$ плюс число инверсий перестановки $\tau$ равно количеству элементов множества $A_2$ равно $n(n-1)/2$.

-- Сб сен 18, 2010 16:59:32 --

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

Кстати: а Вы можете так же аккуратно, строго и вдумчиво доказать, что $2\times2=4$?...

Так же строго не могу. Могу ещё строже

[e7e5]

Но в задачнике другой ответ ( его привел)!

[Профессор Снэйп]

e7e5 в сообщении #353731 писал(а):

Но в задачнике другой ответ ( его привел)!

Чем же он другой?

$k + x = n(n-1)/2$, чему равен $x$?

[e7e5]

да, равен ответу в задачнике, опыта со множествами нет, кажется непонятным...

-- Сб сен 18, 2010 14:11:15 --

А почему?

Профессор Снэйп в сообщении #353728 писал(а):

элементов множества $A_2$ равно $n(n-1)/2$.

[Профессор Снэйп]

e7e5 в сообщении #353734 писал(а):

А почему?

Профессор Снэйп в сообщении #353728 писал(а):

элементов множества $A_2$ равно $n(n-1)/2$.

Что за множество $A_2$, из каких пар оно состоит?

[e7e5]

$A_2 = \{ \langle j,i \rangle : \langle i,j \rangle \in A_1 \}$, т.е задается перестановка $1, 2, ..., n$, для которой наибольшее число инверсий
$C_{n}^2$?

$n, n-1, ..., 3, 2, 1$

[Профессор Снэйп]

e7e5 в сообщении #353742 писал(а):

$A_2 = \{ \langle j,i \rangle : \langle i,j \rangle \in A_1 \}$, т.е...

Не надо "т. е.", достаточно того, что написано.

Какие пары входят в $A_2$. Например, пара $\langle 1,2 \rangle$ входит? А пара $\langle 2,1 \rangle$? А пары $\langle 1,1 \rangle$, $\langle 2,2 \rangle$?

[e7e5]

пара $\langle 2,1 \rangle$? - входит.