перестановка vs. подстановка

[sasha_vertreter]

Простите, я человек новый здесь.

Я изучал алгебру по учебнику Куроша. Там очень четко написано, что "всякое расположение чисел 1, 2... n в некотором определенном порядке называется перестановкой из n чисел (или из n символов)." А дальше (как здесь уже было написано) "всякое взаимно однозначное отображение A множество первых n натуральных чисел на себя называется подстановкой(!) n-й степени, причем, очевидно, всякая подстановка А может быть записана при помощи двух перестановок, подписанных одна под другой".

То есть подстановка - более общее понятие, чем перестановка. Последняя же является просто "структурным элементом" первой.

Может быть достаточно просто придерживаться таких четких определений...

[Xaositect]

sasha_vertreter в сообщении #221539 писал(а):

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

Я там выше приводил ссылку на "Дискретную математику и комбинаторику" Андерсона - тоже достаточно авторитетный источник.

А пользоваться все равно будут тем, чем пользовались.
Главное на английский не переводить как substitution.

[maxal]

Цитата из Стенли "Перечислительная комбинаторика":

Если $S$ - $n$-множество, то перестановка $\pi$ множества $S$ может быть задана линейным упорядочиванием $x_1, x_2, \dots, x_n$ элементов $S$. Будем представлять $\pi$ как слово $x_1 x_2 \dots x_n$ в алфавите $S$. Если $S=\{ y_1, y_2, \dots, y_n \}$, то такое слово соответствует биекции $\pi: S\rightarrow S$, задаваемой формулой $\pi(y_i)=x_i$, так что перестановку множества $S$ можно рассматривать как биекцию $S\rightarrow S$.

[arseniiv]

Конечно, можно подстановку определять двумя перестановками - нижней и верхней. Но всегда её можно привести к такому виду, чтобы верхняя была $ (1,2,3, \ldots ,n) $ Так что две перестановки излишни

[malin]

Скорее всего, надо бы написать уже в "помогите решить....", но не хочется создавать новую тему ради небольшого вопроса.

По теории вероятностей требуется найти мат. ожидание числа инверсий в случайно выбранной перестановке $(1,\ldots,n)$
При этом мной уже решена задача о распределении числа независимых циклов длины $r$ в случайной подстановке
$f = \begin{pmatrix}1& 2& 3& \dots& n\\ f(1)& f(2)& f(3)& \dots& f(n)\end{pmatrix}$

Теперь, когда мне представляется, что подстановки и перестановки - чуть ли не одно и то же, хотелось бы связать число инверсий в перестановке с числом независимых циклов в соответствующей ей подстановке. Пытался связать с числом транспозиций - не получается. Буду признателен, если подскажете как. (или подскажете, что никак).

[arseniiv]

malin в сообщении #254724 писал(а):

чуть ли не одно и то же

Да одно, одно. Просто записывается по-разному. Ну или можно это рассматривать как изоморфные объекты - но лучше не надо.

[RichardZorgi]

О, Malin, ты уже спросил задачку в Кнуте есть про число инверсий, сейчас сам буду смотреть

по поводу перестановок и подстановок смотрите в википедии "перестановка":
1)В комбинаторике перестано́вка — это упорядоченный набор чисел...
2)В теории групп под перестановкой (подстановкой) произвольного множества подразумевается биекция этого множества на себя.

Таким образом необходимо рассматривать контекст и не мешать фрукты с овощами, в комбинаторике подстановок нет, а в группах подстановки удобно записывать перестановкой.

[malin]

Как раз таки в википедии перестановка и подстановка особо не различаются и там даже специально акцентируется внимание на том, что подстановка - это способ записи перестановки... И там нет разделения на всякие теории групп и тому подобное.

Цитата:

в комбинаторике подстановок нет

Это всё равно, что сказать: в комбинаторике нет групп, потому что они в теории групп.

По-моему, посчитать количество подстановок, которые обладают каким-нибудь свойством, например, никаким - это вполне комбинаторная задача. Если в учебнике по комбинаторике будет написано подстановка, то это уже учебник по теории групп?

Но с этим уже всё понятно. Мне всё-таки интересно, как связать количество инверсий в перестановке $(i_1,\dots,i_n)$
с числом независимых циклов в разложении подстановки
$\begin{pmatrix}1& 2& 3& \dots& n\\ i_1&i_2&i_3& \dots&i_n\end{pmatrix}$

И насчёт Кнута. У него 3 тома, даже уже 4. Каждый из них очень толстый. где примерно то?

[RichardZorgi]

Д. Кнут, т.3, раздел 5.1.1.

[VBM]

Господа,
25 лет назад сей вопрос - "перестановка vs. подстановка" -был для меня весьма актуален, ибо название моей диссертации включало в себя
именно "перестановки". Два моих оппонента были из Москвы и из Минска, и никак не могли договориться, какой из терминов - "перестановка" или "подстановка" я должен был бы использовать. В целом, выяснилось следующее: если вы принадлежите математической школе, которая берёт свое начало от Льва Аркадьевича Калужнина (т.е. Киев, Минск), вам рекомендуется говорить "перестановки". Если же вы из Москвы, то лучше говорить "подстановки". Такая вот высокая политика... Лично я предпочитаю говорить "перестановка" - в конце концов, это соответствует "permutations" - ведь никто (почти) не использует "substitutions"...

[Ираклий]

luitzen в сообщении #221295 писал(а):

Вот у логиков и пр. подстановкой называется нечто отнюдь не биективное… Правда, и не в себя…

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

[Someone]

Разве это единственный случай, когда одно и то же слово в разных областях математики используется в разных смыслах?

[Ираклий]

Someone в сообщении #262731 писал(а):

Разве это единственный случай, когда одно и то же слово в разных областях математики используется в разных смыслах?

Нет, конечно. Но если есть эквивалентный синоним, то почему бы его и не использовать.. К тому же даже в школьной математике термин "подстановка" имеет вполне конкретную смысловую окраску, близкую к логическому пониманию этого термина.