элементов данного множества (математическая), замена каждого из его элементов а каким-либо другим элементом φ(а) из того же множества; при этом должны получаться все элементы исходного множества и каждый только один раз. Таким образом, понятие П. по существу совпадает с понятием взаимно однозначного отображения множества на себя (см. Взаимно однозначное соответствие), однако оно применяется большей частью к конечным множествам. Только этот случай и рассматривается ниже. Для П. принята запись
здесь под каждым из элементов данного множества написан соответствующий ему элемент. Так как свойства П. не зависят от природы элементов а, b,..., с, то большей частью (во всяком случае — в учебных целях) используют целые числа 1, 2,..., n, при этом в верхней строке они преимущественно записываются в своём естественном порядке; П. принимает вид
или проще
где φ1, φ2,..., φn — те же числа 1, 2,..., n, но записанные, возможно, в каком-либо ином порядке. Т. о., вторая строка П. образует перестановку (См. Перестановка)φ1, φ2,..., φn из чисел 1, 2,..., n. Различных П. из nэлементов существует столько же, сколько и перестановок, т.е. n!= 1․2․3․...․n. Подстановка
оставляющая на месте все элементы, называется единичной, или тождественной. Для каждой подстановки А существует обратная, т. е. такая, которая переводит φi в i; она обозначается через А-1. Например,
Результат последовательного применения двух подстановок А и В снова будет некоторой подстановкой С: если А переводит i в φi, а В переводит φi в ψi, то С переводит i в ψi. Подстановка С называется произведением подстановок А и В, что записывается так: С = АВ. Например, если
При умножении П. не выполняется закон коммутативности, т. е., вообще говоря, АВ≠ ВА; так, в том же примере
Легко видеть, что IA = AI = А, АА-1= А-1А = I, А(ВС)=(АВ)С (ассоциативный закон). Т. о., все П. из nэлементов образуют группу (См. Группа), называемую симметрической группой (См. Симметрическая группа) степени n.
П., переставляющая местами только 2 элемента i и j, называют транспозицией и обозначается так: (i, j), например
Любую П. можно разложить в произведение транспозиций. Число множителей при разложении разными способами данной П. в произведение транспозиций всегда будет либо чётным, либо нечётным. В соответствии с этим и П. называют либо чётной, либо нечётной; например, А = (1, 3)(5, 4)(5, 1) — нечётная П. Чётность П. можно определить также по числу инверсий, т. е. по числу нарушений порядка в нижней строке П., если числа верхней строки расположены в их естественном порядке: чётность П. совпадает с чётностью числа инверсий; например, в нижней строке подстановки Аимеется 5 инверсий, т. е. случаев, когда большее число стоит раньше меньшего: (3, 2), (3, 1),(2, 1), (5, 1) и (5, 4). Существует n!/2 чётных и n!/2 нечётных П. из nэлементов.
П., циклически переставляющая данную группу элементов, а остальные элементы оставляющая на месте, называется циклом. Число переставляемых элементов называют длиной цикла. Например, подстановка А есть цикл длины 4: она переводит 1 в 3, 3 в 5, 5 в 4, 4 в1; коротко это записывается так: А = (1, 3, 5, 4). Транспозиция есть цикл длины 2. Любую П. можно разложить в произведение независимых (т. е. не имеющих общих элементов) циклов. Например,
Термин «П.» в интегральном исчислении (См. Интегральное исчисление) означает замену переменной в подынтегральной функции.
Лит.: Курош А. Г., Курс высшей алгебры, 10 изд., М. — Л., 1971.
ПОДСТАНО́ВКА см. подставить.
-и, ж.
Действие по глаг. подставить—подставлять (в 3 знач.).
Подстановка числовых показателей в буквенное алгебраическое выражение.
ПОДСТАНО́ВКА, подстановки, жен. (книжн.). Действие по гл. подставить в 4 знач. - подставлять; замена одного другим. Решить задачу без подстановки буквенных показателей. Подстановка целого числа.
ж.
действие по гл. подстановить
ПОДСТАНОВКА - закон, сопоставляющий каждому натуральному числу 1, 2, ..., n другое число из той же последовательности, причем различным элементам а и b соответствуют различные элементы а1 и b1; для подстановки принята запись: где ?1, ?2, ..., ?n - числа 1, 2, ..., n, записанные в ином порядке.
жен. substitutionж. substitution.
replacement,(добавочных битов или символов для согласования скорости передачи информации) stuffing, substitution
f.substitution, permutation; группа подстановок, permutation group
ж. мат.
substitution f
ж. мат.
substitución f
ж. мат.
sostituzione
ПОДСТАНО́ВКА см. Подста́вить.
* * *
подстано́вказакон, сопоставляющий каждому натуральному числу 1, 2, ..., n другое число из той же последовательности, причём различным элементам а и b соответствуют различные элементы a1 и b1; для подстановки принята запись:,где φ1, φ2,..., φn — числа 1, 2, ..., n, записанные в ином порядке.
* * *
ПОДСТАНОВКАПОДСТАНО́ВКА, закон, сопоставляющий каждому натуральному числу 1, 2,..., n другое число из той же последовательности, причем различным элементам а и b соответствуют различные элементы а1 и b1; для подстановки принята запись:
где j1, j2,..., jn — числа 1, 2,..., n, записанные в ином порядке.
множества - взаимно однозначное отображение множества на себя. Термин "П." главным образом применяется для конечного множества X. В этом случае удобно считать, что Х={1,..., п}, изаписывать П. в виде
(*)
где i1, i2,..., in - нек-рая перестановка чисел 1, 2,..., n (впрочем, иногда термин "перестановка" употребляется как синоним термина "П.", см., напр., [2] с. 146). Запись (*) означает, что gпереводит число kв ik, то есть y(k)=ik (пишут также kg=ik).для i=1, 2,..., n. Число всех различных П. множества Xпри|Х| = n равно числу всех перестановок этого множества, т. е. n!. Произведение подстановок a и b множества определяется как последовательное выполнение отображений a и b и задается формулой ab(x)=a(b(x)) для всех . Совокупность всех П. множества Xобразует группу относительно введенного умножения, к-рая наз. симметрической группой. Любая подгруппа симметрич. группы наз. подстановок группой.
Симметрич. группа П. множества Xобозначается S(X), она содержит в качестве подгруппы SF(X) - группу, состоящую из таких подстановок g, к-рые перемещают лишь конечное подмножество элементов (то есть лишь для конечного множества элементов ). Если Xконечно и состоит из пэлементов, то симметрич. группа обозначается Sn.
Транспозицией наз. такая П. множества X, к-рая меняет местами только два элемента iи j; она обозначается (i, j). В S п имеется ровно ( п-1)/2 транспозиций. Любая подстановка g. из SF(X).представима в виде произведения транспозиций. В частности, каждая П. из Sn есть произведение транспозиций. П. может разлагаться в произведение транспозиций многими способами. Однако для данной g. характер четности числа множителей в разложении на транспозиции не зависит от способа разложения. П., представимая в виде произведения четного числа транспозиций, наз. четной, а разлагающаяся в произведение нечетного числа транспозиций - нечетной. В Sn имеется n!/2 четных П. и столько же нечетных. Если П. записана в виде (*), то ее четность совпадает с четностью числа инверсий перестановки i1,..., in к-рое равно числу таких пар {ik, ij}, что k<j, ik>ij. Транспозиция, очевидно, есть нечетная II. Применение одной транспозиции к любой перестановке меняет четность числа ее инверсий на противоположную. Произведение двух четных, а также двух нечетных П. ость четная П., а четной и нечетной П. (в любом порядке) - нечетная. Все четные П. составляют нормальную подгруппу (X).в группе SF(X), к-рая наз. знакопеременной. При|Х|= п подгруппа (X).обозначается А п.
Циклом длины lназ. такая подстановка а конечного множества Y={y1,..., у l], что
Конечный цикл обозначается (y1, y2,..., yl). Бесконечным циклом наз. такая П. счетного множества
что для любого целого i s(yi)=yi+1 Обозначение бесконечного цикла таково:
Цикл длины 2 есть транспозиция. Группа Sn содержит ( п-1)! циклов длины п. Для любой подстановки g из S(X).существует такое разбиение множества X на непересекающиеся подмножества, что на каждом из них g действует как цикл. Конечные подмножества этого разбиения имеют вид
где gl(x}=x, а бесконечные -
где при . Циклы, индуцируемые подстановкой Y на подмножествах разбиения, наз. независимыми циклами подстановки g. Например, (1, 3, 4) и (2, 5)- независимые циклы П.
g записывается в виде
и является произведением своих независимых циклов. Вообще, если g нетождественная П., имеющая лишь конечное число циклов неединичной длины, то g - произведение таких циклов. В частности, каждая нетождественная П. из SF(X).является произведением своих независимых циклов неединичной длины. Порядок подстановки g из SF(X), т. е. порядок циклич. группы <g>, равен наименьшему общему кратному длин ее независимых циклов.
Из независимых циклов данной П. можно получить независимые циклы П., сопряженной с ней. Напр., если
произведение независимых циклов подстановки g из Sn, а и d( а i)=bi, i=l,..., п, то
- разложение подстановки в произведение независимых циклов. Две П. группы Sn тогда и только тогда сопряжены в Sn, когда они имеют одно и то же число независимых циклов каждой длины.
Пусть , k - число независимых циклов подстановки s, включая и циклы длины 1. Тогда разность п-kназ. декрементом подстановки s. Наименьшее число множителей при разложении подстановки s в произведение транспозиций совпадает с ее декрементом. Четность П. совпадает с четностью ее декремента.
П. возникли впервые в комбинаторике 18 в. В кон. 18 в. Ж. Лагранж (J. Lagrange) применил их при исследовании разрешимости алгебраич. уравнении в радикалах. О. Коши (A. Cauchy) посвятил многочисленные исследования этому понятию. Ему, в частности, принадлежит идея разложения П. в произведение циклов. Исследования групповых свойств П. восходит к Н. Абелю (N. Abel) и особенно к Э. Галуа (Е. Galois). См. Галуа теория, Подстановок группа.
Лит.:[1] Jordan С., Traite des substitutions et des equations altfebriques, P., 1057; [2] Кострикин А. И., Введение в алгебру, М., 1977; [3] Курош А. Г., Курс высшей алгебры, 11 изд., М., 1975; [4] Холл М., Теория групп, пер. с англ., М., 1962. Д. А. Супруненко.
replacement,(добавочных битов или символов для согласования скорости передачи информации) stuffing, substitution
* * *
подстано́вка ж. мат.substitution (in, into )
подстано́вка вме́сто … — substitution for …
де́лать подстано́вку — make a substitution
ж. матем.
sostituzione f
- подстановка адреса
- интегральная подстановка- круговая подстановка
- непосредственная подстановка
- нечётная подстановка
- обратная подстановка
- тождественная подстановка
- формальная подстановка
- циклическая подстановка
- чётная подстановка
матем.
підстано́ва, підста́вина;(действие) підста́влення, (неоконч. - ещё) підставля́ння
- арифметическая подстановка
- геометрическая подстановка- гиперболическая подстановка
- гомографическая подстановка
- двойная подстановка
- двукратная подстановка
- двухсторонняя подстановка
- двусторонняя подстановка
- диагональная подстановка
- допустимая подстановка
- единичная подстановка
- инволютивная подстановка
- круговая подстановка
- линейная подстановка
- локсодромическая подстановка
- неориентированная подстановка
- несобственная подстановка
- нечётная подстановка
- обобщённая подстановка
- образующая подстановка
- обратная подстановка
- односторонняя подстановка
- ориентированная подстановка
- ортогональная подстановка
- основная подстановка
- параболическая подстановка
- переместительная подстановка
- правильная подстановка
- простая подстановка
- свободная подстановка
- сложная подстановка
- составная подстановка
- тождественная подстановка
- транспонирующая подстановка
- тригонометрическая подстановка
- циклическая подстановка
- чётная подстановка
- эллиптическая подстановка
матем.
підстано́ва, підста́вина;(действие) підста́влення, (неоконч. - ещё) підставля́ння
- арифметическая подстановка
- геометрическая подстановка- гиперболическая подстановка
- гомографическая подстановка
- двойная подстановка
- двукратная подстановка
- двухсторонняя подстановка
- двусторонняя подстановка
- диагональная подстановка
- допустимая подстановка
- единичная подстановка
- инволютивная подстановка
- круговая подстановка
- линейная подстановка
- локсодромическая подстановка
- неориентированная подстановка
- несобственная подстановка
- нечётная подстановка
- обобщённая подстановка
- образующая подстановка
- обратная подстановка
- односторонняя подстановка
- ориентированная подстановка
- ортогональная подстановка
- основная подстановка
- параболическая подстановка
- переместительная подстановка
- правильная подстановка
- простая подстановка
- свободная подстановка
- сложная подстановка
- составная подстановка
- тождественная подстановка
- транспонирующая подстановка
- тригонометрическая подстановка
- циклическая подстановка
- чётная подстановка
- эллиптическая подстановка
закон, сопоставляющий каждому натуральному числу 1, 2,..., п др. число из той же последовательности, причём разл. элементам а и b соответствуют разл. элементы а1 и b1; для П. принята запись:
где ф1, ф2,..., фn - числа 1, 2,..., п, записанные в ином порядке.