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

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

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

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

Совершенно верно. А как Вы это определили? Входит, потому что $2$ больше, чем $1$, или по какой-то другой причине?

[e7e5]

Потому что вами записано общее правило на множество $A_2$, что входит.

-- Сб сен 18, 2010 14:56:26 --

Вопрос сводится к задаче от числе сочетаний ( парами выбираем числа). А здесь Вы больше про множества толкуете. Как же тогда переход к $C_{n}^2$ происходит?

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

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

Потому что вами записано общее правило на множество $A_2$, что входит.

-- Сб сен 18, 2010 14:56:26 --

Вопрос сводится к задаче от числе сочетаний ( парами выбираем числа). А здесь Вы больше про множества толкуете. Как же тогда переход к $C_{n}^2$ происходит?

Читал, размышлял, ничего не понял...

[VAL]

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

То есть для $\sigma \in S_n$ инверсией называется такая пара $\langle i,j \rangle \in \{ 1, \ldots, n \}^2$, что $i < j$ и $\sigma(i) > \sigma(j)$. Так?

Профессор, удивлен, что вы с этим не сталкивались? Или вы так прикалываетесь?
А как же Вы на первом курсе понятие определителя вводите?
Конечно, что топикстартер назвал числом инверсией, обычно называют числом инверсных пар. Но ведь понятно же, о чем речь.

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

VAL в сообщении #353756 писал(а):

Профессор, удивлен, что вы с этим не сталкивались?

Действительно не сталкивался.

VAL в сообщении #353756 писал(а):

А как же Вы на первом курсе понятие определителя вводите?

Если через сумму с перестановками, то там знак перестановки. Вроде инверсии где-то при деле, но знак с успехом определяется и без всяких инверсий.

[e7e5]

То что было названо в первых постах - все взято из книжки по линейной алгебре, недавно купленной, а задача из задачника по линейной алгебре.

Так предельно ясно, как написал Профессор, в книжке не пишется.
На множество $A_2$ было дано описание, естественно по нему и пары выбираются. Потом пошли не очень понятные мне описания. Никакого прикола здесь не вижу.

Если все очевидно, пожалуйста напишите. Впрочем, может быть, множествами надо отдельно заняться.

Про определитель: в книжке написано: Определителем n-го порядка, соответстующим квадратной матрице назвается алгебраическая сумма $n!$ членов вида $a_{1, \alpha_1}, a_{2, \alpha_2}... a_{n, \alpha_n}$

[VAL]

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

VAL в сообщении #353756 писал(а):

А как же Вы на первом курсе понятие определителя вводите?

Если через сумму с перестановками, то там знак перестановки. Вроде инверсии где-то при деле, но знак с успехом определяется и без всяких инверсий.

А как? Через разложение в произведение независимых циклов? У нас это позже проходят, чем определители.

-- 18 сен 2010, 16:32 --

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

Про определитель: в книжке написано: Определителем n-го порядка, соответстующим квадратной матрице назвается алгебраическая сумма $n!$ членов вида $a_{1, \alpha_1}, a_{2, \alpha_2}... a_{n, \alpha_n}$

И все? Вряд ли. Полагаю там еще про знак (четность) перестановки написано.

[e7e5]

В тексте стоит точка, а дальше ниже начинают писать. про знаки... Определитель сейчас не в теме, опустим...

[ewert]

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

Вроде инверсии где-то при деле, но знак с успехом определяется и без всяких инверсий.

Там всё не так дёшево, к сожалению. Там надо ещё доказывать независимость чётности перестановки от способа её получения, и тут нужен якорь. Возможно, количество инверсий -- таковым и служит.

[e7e5]

Задача 1.
Определить число инверсий в перестановках натуральных чисел:
$1, 3, 5, 7, ... , 2n-1, 2, 4, 6, 8, ... , 2n$

Задача 2.
$2, 4, 6, ..., 2n, 1, 3, 5, 7, ..., 2n-1$

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

То есть для $\sigma \in S_n$ инверсией называется такая пара $\langle i,j \rangle \in \{ 1, \ldots, n \}^2$, что $i < j$ и $\sigma(i) > \sigma(j)$.

для коротких перестановок в виде чисел считать умею, какой подход в таком случае?

Строгое предупреждение за многократное дублирование тем.

[ewert]

Желательно -- молчаливый. Для единички в той перестановке (из 1-й задачки) инверсий нет, для тройки -- одна, для пятёрки -- две и т.д. (а для чётного участка их и вовсе нет, поскольку сравнению подлежат только дальнейшие члены), вот и суммируйте пресловутую арифметическую прогрессию.

[vvvv]

Пример.
$1,2,5,6,4,3,7,8 $ число инверсий $5$
$8,7,5,6,4,3,2,1 $ число инверсий $27$
Формула в ответе неверна.
Но, если рассмотреть $8,7,3,4,6,5,2,1$ - тогда число инверсий будет $23$ и формула ответа работает.

[e7e5]

Спасибо, понял:
Задача 1
$0+0+0+0+...+(n-1)+(n-2)+(n-3)+(n-4)+...+1+0=\frac {n(n-1)} {2}$

Задача 2

$0+...+0+n+(n-1)+...+1=\frac {n(n+1)} {2}$

[Null]

Вы перевернули неправильно должно быть 8,7,3,4,6,5,2,1

[e7e5]

vvvv в сообщении #353827 писал(а):

Пример.
$1,2,5,6,4,3,7,8 $ число инверсий $5$
$8,7,5,6,4,3,2,1 $ число инверсий $27$
Формула в ответе неверна.
Но, если рассмотреть $8,7,3,4,6,5,2,1$ - тогда число инверсий будет $23$ и формула ответа работает.

$1,2,5,6,4,3,7,8 $ : $0+0+3+2+0+0+0+0=5$
$8,7,5,6,4,3,2,1 $: $7+6+5+4+2+2+1=27$
О каком ответе речь, что неверно?