Кострикин. Курс алгебры, задачник

[arseniiv]

Ещё можете доказать более общую теорему: доказать равномощность $[n) ^ X$, где $[n)$ — множество из $n$ элементов ($n$ — натуральное), а более конкретно $\{0, \ldots, n - 1\}$, и множества всех наборов $(X_0, \ldots, X_n)$ таких, что $X = X_0 \supset \ldots \supset X_n = \varnothing$; смысл этих наборов в том, что они задают «мультиподмножества» $X$ с менее чем $n$ элементами: $X_m$ говорит, какие элементы $X$ в такое мультимножество входят ${} \geqslant m$ раз.

[Sinoid]

В ответе к 3.1, в) точно опечатка: там в ответ на перемножение двух подстановок пятой степени приведена подстановка шестой степени. И я даже могу сказать, откуда взята эта подстановка. Это - результат перемножения подстановок буквы г), взятых в обратном порядке.

-- 20.03.2021, 21:54 --

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

$[n) ^ X$

А почему скобки разные с обеих сторон?

[arseniiv]

Это аллюзия к $[0; n)$ — если мы определим такие обозначения $[\ldots], [\ldots), (\ldots], (\ldots)$ промежутков для любого (частично) упорядоченного множества, то для $\mathbb Z$ мы получим, что $[0; n) = \{0, \ldots, n - 1\}$. Чтобы не путать с вещественными промежутками, можно такие обозначать как-то так: $[0; n)_{\mathbb Z}$. Но когда часто находишь себя в использовании левой границы, равной всегда одному и тому же нулю, тянет сократить обозначение до $[n)$ — и спутать с чем-то трудно, и наглядно, и коротко.

[Sinoid]

Ясно. Спасибо за разъяснение.

[Sinoid]

Проверьте, пожалуйста, решение задачи 3.5, г):
Определить число инверсий в последовательности 7, 5, 6, 4, 1, 3, 2.
Имеем: 7 образует 6 инверсий, 5 - 4, 6 тоже 4 инверсии, 4 - 3 инверсии, 3 - 1. Итого - 18 инверсии, а в ответе - всего 14.

[arseniiv]

Тоже насчитал 18.

[Sinoid]

Спасибо.

[Sinoid]

Проверьте, плиз, решение 3.6, д):
Определить четность перестановки $\setcounter{MaxMatrixCols}{11} \begin{pmatrix} \vspace{-1em}&&&&&&&&&&\\ 1 & 2 & 3 & \hdotsfor{6}& n-1 & n\\ 2 & 4 & 6 & \ldots & 1 & 3 & 5 & \hdotsfor{4} \end{pmatrix}$
Имхо, в этой задаче нужно рассматривать отдельно случаи четного и нечетного $n$.
1) $\fbox{n=2m}$. Тогда перестановка (хотя меня так и тянет назвать ее подстановкой после изучения высшей алгебры по Курошу) примет следующий вид: $\setcounter{MaxMatrixCols}{11}\begin{pmatrix}1 & 2 & 3 & \ldots & m-1 & m & m+1 & m+2 & \ldots & 2m-1 & 2m\\ 2 & 4 & 6 & \ldots & 2(m-1) & 2m & 1 & 3 & \ldots & 2m-3 & 2m-1 \end{pmatrix}$. Инверсии создают в этой перестановке только элементы, стоящие в первой половине нижней строки этой перестановки с элементами второй половины этой строки. Каждый элемент этой первой половины дает некоторое количество инверсий с элементами второй половины. Подсчитаем количество этих инверсий для каждого элемента первой половины нижней строки. Имеем: $\begin{matrix}2 & 1\\ 4 & 2\\ 6 & 3\\ \hdotsfor{2}\\ 2(m-1) & m-1\\ 2m & m \end{matrix}$. Общее количество инверсий в этом случае есть $1+2+\ldots+m=\dfrac{m(m+1)}{2}$.
2) $\fbox{n=2m+1}$. Перестановка: $\setcounter{MaxMatrixCols}{11}\begin{pmatrix}1 & 2 & 3 & \ldots & m-1 & m & m+1 & m+2 & \ldots & 2m & 2m+1\\ 2 & 4 & 6 & \ldots & 2(m-1) & 2m & 1 & 3 & \ldots & 2m-1 & 2m+1 \end{pmatrix}$. Тут практически все так же, только инверсии дают не элементы первой половины нижней строки со второй ее половиной, а первые $m$ элементов этой строки с последующими $m$ элементами этой строки. По-хорошему, надо бы переписать случай $n=2m$ под этот случай. Ну, да, ладно. И, так же, как и выше, каждый из первых $m$ элементов этой строки дает определенное количество инверсий с последующими $m$ элементами этой строки. Таблица количества инверсий будет следующей: $\begin{matrix}2 & 1\\ 4 & 2\\ 6 & 3\\ \hdotsfor{2}\\ 2(m-1) & m-1\\ 2m & m \end{matrix}$. Значит, общее количество инверсий будет таким же - $\dfrac{m(m+1)}{2}$. И вот тут-то самое оно и возникает. В ответе написано, что $(-1)^{\left[(n+2)/2\right]}$. Как в случае 1), так и в случае 2) $\left[\dfrac{n+2}{2}\right]=m+1$. Однако сравнение $\dfrac{m(m+1)}{2}\equiv m+1(\mod2)$ (для случая 1) ) выполняется как не для всех положительных (для случая 1) ), так и не для всех неотрицательных целых (для случая 2); 0 - натуральное или нет - под вопросом, поэтому здесь написал неотрицательных целых) $m$. Как думаете, это у меня ошибка?

[vpb]

Sinoid в сообщении #1510598 писал(а):

Как думаете, это у меня ошибка?

Нет, в задачнике. Это бывает. Это можно было сразу увидеть (если сомневались) на маленьких примерах, скажем $n=2,8$.

[Sinoid]

Вот тут:

vpb в сообщении #1510606 писал(а):

...Как в случае 1), так и в случае 2) $\left[\dfrac{n+2}{2}\right]=m+1$. Однако...

Имелось ввиду $\left\lfloor \dfrac{n+1}{2}\right\rfloor=m$.

-- 23.03.2021, 20:48 --

А вот так, на будущее. Довольно часто попадаются, например, суммы, в которых пределы - целые части чисел. Вот, допустим, мне попалась сумма с верхним пределом $\left\lfloor \dfrac{n}{3}\right\rfloor$, которую нужно вычислить. Это что, нужно рассматривать отдельно случаи $n=3n_{1}$, $n=3n_{1}+1$ и $n=3n_{1}+2$? Я понимаю, что формулировка вопроса довольно размыта, но все же.

[vpb]

В более позднем (4-м) издании задачника ошибку исправили.

Sinoid в сообщении #1510674 писал(а):

Это что, нужно рассматривать отдельно случаи $n=3n_{1}$, $n=3n_{1}+1$ и $n=3n_{1}+2$? Я понимаю, что формулировка вопроса довольно размыта, но все же.

Бывает надо отдельно рассматривать, бывает можно всё вместе, по разному.

[Sinoid]

vpb в сообщении #1510683 писал(а):

Бывает надо отдельно рассматривать,

Значит, все-таки возможно, что отдельно, а по-другому никак. А я думал, это дело в скудости моей фантазии. Спасибо.

[arseniiv]

Sinoid
И ещё если вас значительно занесёт в преобразования выражений с разными суммированиями, целыми частями, остатками от деления, биномиальными коэффициентами, то довольно много материала по поводу таких преобразований (и упражнения тоже) есть в замечательной «Конкретной математике» Кнута, Грэма, Паташника. Про пределы суммирования с полом я не помню, но пол в самих слагаемых сумм рассматривается там весьма много.

[Sinoid]

arseniiv, о, спасибо большое за рекомендацию. Обязательно посмотрю.

[Sinoid]

Что-то не пойму с задачей 3.17:
Пусть $f_{ij}-$один из двучленов $x_i-x_j$ или $x_j-x_i$, где $i$ и $j-$ произвольные числа от 1 до $n$, $i<j$, и пусть $f(x_{1},\, x_{2},\ldots, x_{n})-$произведение всех этих двучленов. Доказать, что для любой перестановки $\sigma\in S_{n}$

$$f(x_{\sigma(1)},\ldots,x_{\sigma(n)})=(\operatorname{sgn}\sigma)\cdot f(x_{1},\ldots,x_{n})$$

В случае определителя Вандермонда все прекрасно доказывается. Но в этом доказательстве есть один момент, делающий его непригодным для случая произвольного $f(x_{1},\, x_{2},\ldots x_{n})$. Вот посмотрите, пожалуйста. Берем произведение ${\displaystyle \prod_{1\leqslant j<i\leqslant n}(x_{i}-x_{j})}$ (для удобства будем называть его определителем Вандермонда). Перестановка $\begin{equation} \sigma=\begin{pmatrix}1 & 2 & \ldots & j & \ldots & i & \ldots & n\\ \sigma(1) & \sigma(2) & \ldots & \sigma(j) & \ldots & \sigma(i) & \ldots & \sigma(n) \end{pmatrix} \end{equation} $
преобразует наш определитель в следующее выражение: ${\displaystyle \prod_{1\leqslant j<i\leqslant n}(x_{\sigma(i)}-x_{\sigma(j)})}$. Вот здесь-то и начинается кино. Ввиду сюръективности $\sigma$ и в исходном определителе присутствует множитель $x_{\sigma(i)}-x_{\sigma(j)}$, если пара $(j,\,i)$ (здесь и далее, для определенности $j<i$) не образует инверсии относительно перестановки $\sigma$: при этом будет $\sigma(j)<\sigma(i)$, а во всех скобках исходного определителя Вандермонда индекс уменьшаемого больше индекса вычитаемого. Наоборот, если пара $(j,\,i)$ образует инверсию относительно перестановки $\sigma$, то будет $\sigma(j)>\sigma(i)$ и в исходном определителе ввиду сформулированного выше соотношения между индексами переменных, являющимися уменьшаемым и вычитаемым, присутствует скобка $x_{\sigma(j)}-x_{\sigma(i)}$. В выражении же, полученном из исходного определителя Вандермонда перестановкой $\sigma$, будет скобка $x_{\sigma(i)}-x_{\sigma(j)}=-(x_{\sigma(j)}-x_{\sigma(i)})$. И это верно для любой пары $j,\,i$. Итак, мы получили, что каждая инверсия любой пары $j,\,i$ относительно перестановки $\sigma$ создает в произведении, получающемся из исходного определителя Вандермонда с помощью перестановки $\sigma$ скобку, отличающуюся только знаком от какой-то скобки в исходном определителе Ванедермонда (все, мной сделан первый шаг к Галуа ). После чего утверждение задачи по отношению к определителям Вандермонда становится очевидным. А вот в случае произвольного $f(x_{1},\, x_{2},\ldots x_{n})$... Произведение ${\displaystyle f(x_{1},\, x_{2},\ldots x_{n})=\prod_{\begin{matrix}1\leqslant j,\, i\leqslant n\\ j\neq i \end{matrix}}(x_{i}-x_{j})}$ преобразованием $\sigma=\begin{pmatrix}\ldots & j & \ldots & i & \ldots\\ \ldots & \sigma(j) & \ldots & \sigma(i) & \ldots \end{pmatrix}$ переводится в произведение $\displaystyle \prod_{\begin{matrix}1\leqslant j,\, i\leqslant n\\ j\neq i \end{matrix}}(x_{\sigma(i)}-x_{\sigma(j)})$. И, если в данном случае какая-нибудь пара $(j,\,i)$ образует инверсию относительно перестановки $\sigma$, то в этом случае уже ничто не запретит множителю $x_{\sigma(i)}-x_{\sigma(j)}$ входить как в произведение после преобразование, так и в исходное произведение: в этом случае какие-либо соотношения между индексами уменьшаемого и вычитаемого в каждой скобке исходного произведения просто-напросто отсутствуют.