2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Помогите разобраться, как определить четность перестановки.
Сообщение24.06.2012, 11:11 


24/06/12
12
Добрый день!
Помогите разобраться, как определить четность перестановки.
$$\begin{pmatrix}
1 & 2 & 3 & ... & ...& ...& ...& ...& n-1 & n\\
2 & 4 & 6 & ... & 1 & 3 & 5 & ... & ... & ...
\end{pmatrix}$$

 Профиль  
                  
 
 Re: Помогите разобраться, как определить четность перестановки.
Сообщение24.06.2012, 11:20 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Помогите разобраться, как определить четность перестановки.
Сообщение24.06.2012, 11:26 


19/05/10

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

 Профиль  
                  
 
 Re: Помогите разобраться, как определить четность перестановки.
Сообщение24.06.2012, 13:41 


24/06/12
12
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$

 Профиль  
                  
 
 Re: Помогите разобраться, как определить четность перестановки.
Сообщение24.06.2012, 13:56 


19/05/10

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

 Профиль  
                  
 
 Re: Помогите разобраться, как определить четность перестановки.
Сообщение24.06.2012, 14:40 
Заслуженный участник


11/05/08
32166
PetrP в сообщении #588484 писал(а):
Хотя ответ равен $(n+2)/2$

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

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

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

 Профиль  
                  
 
 Re: Помогите разобраться, как определить четность перестановки.
Сообщение24.06.2012, 14:58 


24/06/12
12
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 одна инверсия.

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

 Профиль  
                  
 
 Re: Помогите разобраться, как определить четность перестановки.
Сообщение24.04.2015, 12:41 


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

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

 Профиль  
                  
 
 Re: Помогите разобраться, как определить четность перестановки.
Сообщение24.04.2015, 18:09 
Заслуженный участник


11/05/08
32166
xolodec в сообщении #1007513 писал(а):
А четность можно будет определить, как $\varepsilon_\pi = (-1)^k$

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

 Профиль  
                  
 
 Re: Помогите разобраться, как определить четность перестановки.
Сообщение24.04.2015, 20:24 


29/04/14
139
ewert в сообщении #1007599 писал(а):
Но можно чуть-чуть ещё обнаглеть и сказать, что $\varepsilon_\pi = (-1)^{\frac{n^4+2n^3-n^2-2n}{8}}$

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

 Профиль  
                  
 
 Re: Помогите разобраться, как определить четность перестановки.
Сообщение24.04.2015, 20:36 
Заслуженный участник


27/04/09
28128
Такую простую последовательность как
ewert в сообщении #588506 писал(а):
$- - - - + + + + - - - - + + + + - - - - + + + + - - - - + + + + ...$
записывать в виде
ewert в сообщении #1007599 писал(а):
$\varepsilon_\pi = (-1)^{\frac{n^4+2n^3-n^2-2n}{8}}$
это, по-моему, кощунство. :?
$(-1)^{\lfloor n/4\rfloor + k}$ — и хватит с неё.

 Профиль  
                  
 
 Re: Помогите разобраться, как определить четность перестановки.
Сообщение24.04.2015, 22:45 
Заслуженный участник


11/05/08
32166
arseniiv в сообщении #1007655 писал(а):
это, по-моему, кощунство. :?

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

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

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

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

 Профиль  
                  
 
 Re: Помогите разобраться, как определить четность перестановки.
Сообщение24.04.2015, 22:50 
Заслуженный участник


27/04/09
28128

(Оффтоп)

ewert в сообщении #1007711 писал(а):
Это не кощунство, а наглость.
А кощунством тогда какое представление будет? (Хотя бы менее длинное или более?)

 Профиль  
                  
 
 Re: Помогите разобраться, как определить четность перестановки.
Сообщение24.04.2015, 22:52 
Заслуженный участник


11/05/08
32166

(Оффтоп)

arseniiv в сообщении #1007713 писал(а):
А кощунством тогда какое представление будет?

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

 Профиль  
                  
 
 Re: Помогите разобраться, как определить четность перестановки.
Сообщение25.04.2015, 11:16 


29/04/14
139
ewert в сообщении #1007711 писал(а):
выражение $\frac{(n-1)n(n+1)(n+2)}{8}$ обеспечивает ровно требуемую чётность.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group