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

[malin]

Я прошу прощения, но я даже зарегистрировался специально, чтобы сделать это тривиальное замечание: не перестановки, а ПОДСТАНОВКИ!

Тема отделена от topic23328.html

[Xaositect]

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

Я прошу прощения, но я даже зарегистрировался специально, чтобы сделать это тривиальное замечание: не перестановки, а ПОДСТАНОВКИ!

Нет, именно перестановка (permutation)
http://ru.wikipedia.org/wiki/Перестановка

[malin]

Ребята, ну это же совсем неправильно! Посудите сами: Перестано́вка — это упорядоченный набор чисел 1, 2,..., n.
А подстановка - это биекция, отображающая множество само в себя. Прошу обратить внимание на то, что любая подстановка коечного множества может быть задана таблицей, в то время как перестановка никоим образом не может быть так записана!(подробно можно прочитать в книге Глухов, Елизаров, Нечаев - Алгебра, том 1)

[Xaositect]

Смотрите дальше.

Цитата:

Более общо, перестановкой произвольного (обычно конечного) множества X называется биекция $\pi: X\to X$.

Может быть, раньше эти термины различались, в последнее время я везде вижу и слышу только "перестановка".
Андерсон Дж. — Дискретная математика и комбинаторика

Цитата:

Перестановка была определена как функция, которая на множестве устанавливает взаимно-однозначное соответствие. Если $f$ ---перестановка на множестве $\{1,2,3,\dots,n\}$, она может быть представлена в виде $\begin{pmatrix}1& 2& 3& \dots& n\\ f(1)& f(2)& f(3)& \dots& f(n)\end{pmatrix}$

Могу привести еще несколько ссылок на книги, где этот термин так используется.

[maxal]

Термин подстановка теперь почти не используется.

-- Wed Jun 10, 2009 13:22:04 --

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

Перестано́вка — это упорядоченный набор чисел 1, 2,..., n.

Не совсем. Перестановка - это биекция на множестве $\{1,2,\dots,n\}$. Она может быть записана в виде упорядоченного набора чисел $1,2,\dots,n$, но это лишь одна из возможных записей.

[malin]

Хорошо, если вы определяете перестановку таким образом:

Цитата:

Перестановка была определена как функция, которая на множестве устанавливает взаимно-однозначное соответствие. Если $f$ ---перестановка на множестве $\{1,2,3,\dots,n\}$, она может быть представлена в виде $\begin{pmatrix}1& 2& 3& \dots& n\\ f(1)& f(2)& f(3)& \dots& f(n)\end{pmatrix}$

тогда как бы вы назвали упорядоченный набор целых чисел от 1 до n? Если тоже перестановкой, тогда опишите связь между этими двумя понятиями.
Насколько я вас понял, такая связь может быть задана следующим образом: перестановка чисел от 1 до 5, например такая: $(1,3,2,5,4)$ является полноцикловой подстановкой следующего вида:$\begin{pmatrix}1& 2& 3& 4& 5\\3& 5& 2& 1& 4\end{pmatrix}$
Однако перестановка $(4,1,3,2,5)$ будет являться той же самой подстановкой, хотя как перестановки они отличаются!
Уловили разницу?

[Xaositect]

Можно взаимно однозначно сопоставить перестановку $f = \begin{pmatrix}1& 2& 3& \dots& n\\ f(1)& f(2)& f(3)& \dots& f(n)\end{pmatrix}$ и набор $(f(1),f(2),\dots,f(n))$(нижнюю строку таблицы).

Здесь немного неудачная ситуация с обозначениями, потому что $(a_1 a_2 \dots a_k)$ означает циклическую перестановку --- такую, что $f(a_1) = a_2, f(a_2) = a_3,\dots,f(a_k)= a_1$ а на элементах, отличных от $a_i$ $f(x)=x$. Например, перестановка $(35)$ меняет местами $3$ и $5$

[malin]

Это я знаю. Действительно, подстановка $(35)$ меняет местами 3 и 5, но в то же время и подстановка $(53)$ меняет местами 3 и 5. Ведь так?
НО если бы $(35)$ $(53)$ были не подстановками(биекциями), а упорядоченными наборами(множествами), то они бы отличались.
Согласитесь, вектор $(35)$ не равен вектору $(53)$. В тоже время биекции $(35)$ и $(53)$ совпадают.
Вот почему нельзя путать эти два понятия: разным перестановкам соответствуют одинаковые подстановки!

-- Ср июн 10, 2009 22:55:53 --

Всё! я понял! Вы просто отошли от общепринятых обозначений и решили, что лучше забить на обозначение циклов, а вместо этого в круглых скобках писать нижнюю строку подстановки. Тогда да. Но это не лучший путь=)

[maxal]

Как именно записываются перестановки в научной литературе всегда оговаривается отдельно. Чтобы спутать запись перестановки в виде произведения циклов и в виде кортежа ее значений на числах $1,2,\dots,n$, надо быть очень рассеянным.

-- Wed Jun 10, 2009 13:59:45 --

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

[RIP]

maxal в сообщении #221254 писал(а):

Термин подстановка теперь почти не используется.

Странно. У нас на лекциях по алгебре использовался как раз термин "подстановка". А про перестановку было нечто в духе: иногда подстановку называют перестановкой, но это неправильно, поскольку перестановка --- это упорядоченный набор... (см. выше), поэтому мы так делать не будем.

[maxal]

RIP
А у нас на лекциях (лет 15 назад) подстановкой назывался конкретный способ записи перестановки:

$$\pi = \begin{pmatrix} x_1 & x_2 & \dots & x_n \\ y_1 & y_2 & \dots & y_n \end{pmatrix}$$

Эта подстановка описывает перестановку, заданную равенствами $\pi(x_i)=y_i$.

В статьях же я давненько термина подстановка не встречал.

[luitzen]

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

[VAL]

RIP в сообщении #221264 писал(а):

maxal в сообщении #221254 писал(а):

Термин подстановка теперь почти не используется.

Странно. У нас на лекциях по алгебре использовался как раз термин "подстановка". А про перестановку было нечто в духе: иногда подстановку называют перестановкой, но это неправильно, поскольку перестановка --- это упорядоченный набор... (см. выше), поэтому мы так делать не будем.

Похожая картина была и у нас, когда я учился (а было это много лет тому давно). Мол, подстановка - это то, что проходят в алгебре (т.е. биекция множества на себя), а перестановка - бывает только в комбинаторике (расставили различимые объекты в определенном порядке и при этом не важно, стояли ли они до того в каком-то другом порядке).
В начале своей преподавательской деятельности, я четко придерживался такого же подхода. Но потом заметил, что в литературе все чаще используют термин "перестановка", в том числе и для обозначения биекции. В результате я стал употреблять слова "подстановка" и "перестановка" как Бог на душу положит.
Например, оформляя и вычитывая решение задачи ММ100, в котором подстановки (или перестановки?) упоминаются десятки раз, я заметил, что использую обсуждаемые термины, как если бы я воспользовался хорошим ГСЧ Я попробовал причесать решение, искореняя один из терминов, но не уверен, что смог довести эту работу до конца.

[lofar]

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

Все это дело вкуса. Мне, например, больше нравится слово "перестановка".

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

lofar в сообщении #221439 писал(а):

Все это дело вкуса.

Согласен. Всегда думал, что "подстановка" и "перестановка" --- просто синонимы.