Алмаштырма

Өс шарҙан 6 алмаштырма

Алмаштырма (рус. Перестановка) комбинаторикала — ${\displaystyle 1,\ 2,\ \ldots ,\ n,}$ һандарының ҡабатланмайынса тәртипкә килтерелгән йыйылмаһы, ғәҙәттә ${\displaystyle \{1,\;2,\;\ldots ,\;n\}}$ күмәклегендә, ${\displaystyle i}$ һанына йыйылманан ${\displaystyle i}$-сы элементты ярашлы ҡуйған биекция булараҡ трактовкалана. Шул уҡ ваҡытта ${\displaystyle n}$ һаны алмаштырманың оҙонлоғо тип атала^[1].

Төркөмдәр теорияһында ирекле күмәклектең алмаштырмаһы тип был күмәклектең үҙ-үҙенә биекцияһы атала. Был мәғәнәлә «алмаштырма» һүҙенә синоним булараҡ ҡайһы бер авторҙар подстановка һүҙен ҡулланалар. (Башҡа авторҙар алмаштырманы яҙыуҙың күрһәтмә ысулын подстановка тип атай. Унан да мөһимерәк айырма шунда, подстановка - ул туранан-тура функция, ә алмаштырма - был функцияны эҙмә-эҙлелек элементтарына ҡулланыу һөҙөмтәһе ул.)

«Алмаштырма» термины тәүҙә нисектер урынлаштырылған объекттар алынғанға, ә тәртипкә килтереүҙең башҡа алымдары был объекттарҙы алмаштырып ҡуйыуҙы талап иткәнгә килеп тыуа^[2].

Алмаштырма тип бер үк элементтарҙан торған, элементтарҙың урынлашыу тәртибе менән генә айырылған йыйылмалар атала^[3].

Үҙсәнлектәре

${\displaystyle n}$ элементтан бөтә алмаштырмалар һаны ${\displaystyle n}$ элементтан ${\displaystyle n}$-шар урынлаштырмалар һанына, йәғни ${\displaystyle n}$ факториалға тигеҙ^[4][5][6][7]:

${\displaystyle P_{n}=A_{n}^{n}={\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!=1\cdot 2\cdot \ldots \cdot n}$.

Функциялар композицияһы бер оҙонлоҡтағы алмаштырмаларҙа ҡабатлау ғәмәлен билдәләй: ${\displaystyle (\pi \cdot \sigma )(k)=\pi (\sigma (k)).}$ Был ғәмәлгә ҡарата ${\displaystyle n}$ элементтан алмаштырмалар күмәклеге төркөм төҙөй, уны симметрик тип атайҙар һәм ғәҙәттә ${\displaystyle S_{n}}$ тип тамғалайҙар.

${\displaystyle n}$ элементтан теләһә ниндәй сикле төркөм ${\displaystyle S_{n}}$ симметрик төркөмөнөң ниндәйҙер аҫтөркөмөнә изоморфлы (Кэли теоремаһы). Был ваҡытта һәр ${\displaystyle a\in G}$ элементы ${\displaystyle G}$ элементтарында ${\displaystyle \pi _{a}(g)=a\circ g,}$ тождествоһы менән бирелгән ${\displaystyle \pi _{a}}$ алмаштырмаһы менән тиңләштерелә, бында ${\displaystyle \circ }$ — ${\displaystyle G}$-ла төркөм операцияһы.

Бәйле билдәләмәләр

Алмаштырма вәкиле ${\displaystyle \pi \colon X\to X}$ — ул ${\displaystyle X}$ күмәклегенең ${\displaystyle \operatorname {supp} (\pi ):=\{x\in X\mid \pi (x)\neq x\}}$ тип билдәләнгән аҫкүмәклеге.

${\displaystyle \pi }$ алмаштырмаһының хәрәкәтһеҙ нөктәһе тип ${\displaystyle \pi \colon X\to X}$ сағылышының һәр хәрәкәтһеҙ нөктәһе, йәғни ${\displaystyle \{x\in X\mid \pi (x)=x\}}$ күмәклегенең элементы атала. ${\displaystyle \pi }$ алмаштырмаһының бөтә хәрәкәтһеҙ нөктәләре күмәклеге уның ${\displaystyle X}$-та вәкиленең ҡушымтаһы була.

${\displaystyle \pi }$ алмаштырмаһында Инверсия тип һәр шундай индекстар пары ${\displaystyle i,\ j}$ атала, бында ${\displaystyle 1\leqslant i<j\leqslant n}$ һәм ${\displaystyle \pi (i)>\pi (j)}$. Алмаштырмала инверсиялар һанының йоплоғо алмаштырманың йоплоғон билдәләй.

Алмаштырмаларҙың махсус төрҙәре

• Тождестволы алмаштырма — һәр ${\displaystyle x\in X}$ элементын үҙенә сағылдырыусы ${\displaystyle e,}$ алмаштырмаһы: ${\displaystyle e(x)=x.}$
• Инволюция — үҙенә үҙе кире булған алмаштырма ${\displaystyle \tau ,}$, йәғни ${\displaystyle \tau \cdot \tau =e.}$
• Буталыш — хәрәкәтһеҙ нөктәһе булмаған алмаштырма.
• ${\displaystyle \ell }$ оҙонлоғондағы Цикл тип ${\displaystyle \{x_{1},\;x_{2},\;\ldots ,\;x_{\ell }\}\subset X}$ аҫкүмәклегенән башҡа бөтә ${\displaystyle X,}$ күмәклегендә тождестволы булған һәм ${\displaystyle \pi (x_{\ell })=x_{1},\ \pi (x_{i})=x_{i+1}}$ үтәлгән ${\displaystyle \pi ,}$ подстановкаһы атала. Тамғаланышы: ${\displaystyle (x_{1},\;x_{2},\;\ldots ,\;x_{\ell }).}$.
• Транспозиция — ике элементты урындары менән алмаштырыусы ${\displaystyle X}$ күмәклеге элементтары алмаштырмаһы. Транспозиция оҙонлоғоғо 2 булған цикл була.

Подстановка

${\displaystyle X}$ күмәклегенең ${\displaystyle \pi }$ алмаштырмаһы подстановка күренешендә яҙыла ала, мәҫәлән:

${\displaystyle {\begin{pmatrix}x_{1}&x_{2}&x_{3}&\ldots &x_{n}\\y_{1}&y_{2}&y_{3}&\ldots &y_{n}\end{pmatrix}},}$

бында ${\displaystyle \{x_{1},\;\ldots ,\;x_{n}\}=\{y_{1},\;\ldots ,\;y_{n}\}=X}$ һәм ${\displaystyle \pi (x_{i})=y_{i}}$.

Циклдар ҡабатландығы һәм алмаштырма тамғаһы

Теләһә ниндәй ${\displaystyle \pi }$ алмаштырмаһы ${\displaystyle \ell \geqslant 2}$ оҙонлоғондағы киҫешмәүсе циклдар ҡабатландығына (циклдар композицияһына) тарҡатыла ала, шуның менән бергә ҡабатландыҡта циклдарҙың урынлашыу тәртибенә тиклем аныҡлыҡ менән берҙән-бер ысул менән. Мәҫәлән:

${\displaystyle {\begin{pmatrix}1&2&3&4&5&6\\5&1&6&4&2&3\end{pmatrix}}=(1,\;5,\;2)(3,\;6).}$

Шулай уҡ йыш ҡына алмаштырманың хәрәкәтһеҙ нөктәләрен 1 оҙонлоҡтағы үҙ аллы циклдарҙан ғибәрәт тип иҫәпләйҙәр һәм алмаштырманың цикллы тарҡалыуын улар менән тулыландыралар. Өҫтә килтерелгән миҫал өсөн бындай тулыландырылған тарҡатыу ошолай була: ${\displaystyle (1,\;5,\;2)(3,\;6)(4)}$. Төрлө оҙонлоҡтағы циклдар һаны, атап әйткәндә ${\displaystyle (c_{1},\;c_{2},\;\ldots )}$ һандар йыйылмаһы, бында ${\displaystyle c_{\ell }}$ — ${\displaystyle \ell }$ оҙонлоғондағы циклдар һаны, алмаштырманың цикл структураһын билдәләй. Шуның менән бергә ${\displaystyle 1\cdot c_{1}+2\cdot c_{2}+\ldots }$ дәүмәле алмаштырманың оҙонлоғона тигеҙ, ә ${\displaystyle c_{1}+c_{2}+\ldots }$ дәүмәле циклдарҙың дөйөм һанына тигеҙ. ${\displaystyle n}$ элементтан ${\displaystyle k}$ циклы менән алмаштырмалар һаны беренсе төрҙәге тамғаһыҙ Стирлинг һаны ${\displaystyle {\begin{bmatrix}n\\k\end{bmatrix}}}$ менән бирелә.

Теләһе ҡайһы цикл (киҫешмәүсе булыуы мотлаҡ түгел) транспозициялар ҡабатландығына тарҡатылырға мөмкин. Шул уҡ ваҡытта 1 оҙонлоҡтағы циклды (ысынында иһә тождестволы алмаштырма ${\displaystyle e}$ булып торған) транспозицияларҙың буш ҡабатландығы йәки, мәҫәлән, теләһә ниндәй транспозицияның квадраты рәүешендә күрһәтергә мөмкин: ${\displaystyle (1,\;2)(1,\;2)=(2,\;3)(2,\;3)=e.}$ ${\displaystyle \ell \geqslant 2}$ оҙонлоғондағы циклды ${\displaystyle \ell -1}$ транспозициялар ҡабатландығына ошолай тарҡатырға мөмкин:

${\displaystyle (x_{1},\;\ldots ,\;x_{l})=(x_{1},\;x_{\ell })(x_{1},\;x_{\ell -1})\dots (x_{1},\;x_{2}).}$

Циклдарҙың транспозициялар ҡабатландығына тарҡалмаһы берҙән-бер түгеллеген билдәләп китергә кәрәк:

${\displaystyle (1,\;2,\;3)=(1,\;3)(1,\;2)=(2,\;3)(1,\;3)=(1,\;3)(2,\;4)(2,\;4)(1,\;2).}$

Шулай итеп, теләһә ниндәй алмаштырма транспозициялар ҡабатландығына тарҡатылырға мөмкин. Быны күп ысулдар менән эшләргә мөмкин булһа ла, шундай бөтә тарҡатыуҙарҙа транспозициялар һанының йоплоғо бер төрлө. Был ${\displaystyle \pi }$ алмаштырмаһының тамғаһын (алмаштырманың йоплоғо йәки алмаштырма сигнатураһы) ошолай билдәләргә мөмкинлек бирә:

${\displaystyle \varepsilon _{\pi }=(-1)^{t},}$

бында ${\displaystyle t}$ — ҡайһылыр ${\displaystyle \pi }$ тарҡалмаһында транспозициялар һаны. Шуның менән бергә, әгәр ${\displaystyle \varepsilon _{\pi }=1}$ булһа ${\displaystyle \pi }$-ны йоп алмаштырма тип атайҙар, һәм, әгәр ${\displaystyle \varepsilon _{\pi }=-1}$ булһа, таҡ алмаштырма тип атайҙар.

Эквивалентлы, алмаштырманың тамғаһы уның цикл структураһы менән билдәләнә: ${\displaystyle n}$ элементтан, ${\displaystyle k}$ циклдан торған ${\displaystyle \pi }$ алмаштырмаһының тамғаһы

${\displaystyle \varepsilon _{\pi }=(-1)^{n-k}}$-гә тигеҙ.

${\displaystyle \pi }$ алмаштырманың тамғаһы шулай уҡ ${\displaystyle N(\pi )}$-ның ${\displaystyle \pi }$ -ла инверсиялар һаны аша ла билдәләнергә мөмкин:

${\displaystyle \varepsilon _{\pi }=(-1)^{N(\pi )}}$.

Ҡабатланыусы алмаштырма

Төрлө ${\displaystyle m}$ типтағы ${\displaystyle n}$ элементты ҡарайыҡ, шуның менән бергә һәр типта бөтә элементтар бер төрлө. Ул саҡта бөтә был элементтарҙан алмаштырмалар бер типтағы элементтарҙың урынлашыу тәртибенә тиклем аныҡлыҡ менән ҡабатланыусы алмаштырма тип аталалар. Әгәр ${\displaystyle k_{i}}$ — ${\displaystyle i}$-сы типтағы элементтар һаны булһа, ул саҡта ${\displaystyle k_{1}+k_{2}+\ldots +k_{m}=n}$ һәм бөтә мөмкин булған ҡабатланыусы алмаштырмалар һаны ${\displaystyle \textstyle {\binom {n}{k_{1},\;k_{2},\;\ldots ,\;k_{m}}}={\frac {n!}{k_{1}!k_{2}!\ldots k_{m}!}}}$ мультиномиаль коэффициентҡа тигеҙ.

Ҡабатланыусы алмаштырманы шулай уҡ ҡеүәте ${\displaystyle k_{1}+k_{2}+\ldots +k_{m}=n}$ булған ${\displaystyle \{1^{k_{1}},\;2^{k_{2}},\;\ldots ,\;m^{k_{m}}\}}$ мультикүмәклек алмаштырмаһы итеп ҡарарға мөмкин.

Осраҡлы алмаштырма

Төп мәҡәлә: Случайные перестановки

Осраҡлы алмаштырма тип ${\displaystyle \xi =(\xi _{1},\;\ldots ,\;\xi _{n})}$ осраҡлы векторы атала, уны бөтә элементтары 1-ҙән алып ${\displaystyle n}$-ға тиклемге натураль ҡиммәттәр ҡабул итәләр һәм шуның менән бергә теләһә ниндәй ике элементтың тап килеү ихтималлығы 0-гә тигеҙ.

Бәйһеҙ осраҡлы алмаштырма тип шундай ${\displaystyle \xi }$ осраҡлы алмаштырма атала, уның өсөн:

${\displaystyle P\{\xi =\sigma \}={\frac {p_{1\sigma (1)}\ldots p_{n\sigma (n)}}{\sum \limits _{\pi \in S_{n}}p_{1\pi (1)}\ldots p_{n\pi (n)}}}}$

ҡайһы бер шундай ${\displaystyle p_{ij}}$ өсөн:

${\displaystyle \forall i\ (1\leqslant i\leqslant n)\colon p_{i1}+\ldots +p_{in}=1}$

${\displaystyle \sum \limits _{\pi \in S_{n}}p_{1\pi (1)}\ldots p_{n\pi (n)}>0.}$

Шуның менән бергә әгәр ${\displaystyle p_{ij}}$ ${\displaystyle i}$-гә бәйле булмаһа, ${\displaystyle \xi }$ алмаштырмаһын бер төрлө төркөмләнгән тип атайҙар. Әгәр ${\displaystyle j}$-ҡа бәйлелек булмаһа, йәғни ${\displaystyle \forall i,\;j\ (1\leqslant i,\;j\leqslant n)\colon p_{ij}=1/n,}$ ул саҡта ${\displaystyle \xi }$ алмаштырмаһын бер төрлө тип атайҙар.

Шулай уҡ ҡарағыҙ

• Нарайана алгоритмы
• Анаграмма
• Гигантская компонента
• Урынлаштырма
• Симметрик төркөм
• Сочетание

Иҫкәрмәләр

1. Евгений Вечтомов, Дмитрий Широков. Математика: логика, множества, комбинаторика. Учебное пособие для академического бакалавриата. — 2-е изд.. — Litres, 2018-03-02. — С. 145—146. — 244 с. Архивная копия от 7 апрель 2022 на Wayback Machine
2. Учебник по математике для СПО / Башмаков М. И., 10-11 класс. — С. 67
3. Теория вероятностей и элементы математической статистики 2022 йыл 1 февраль архивланған.
4. Виленкин Н.Я. Глава III. Комбинаторика кортежей и множеств. Размещения с повторениями // Популярная комбинаторика. — М.: Наука, 1975. — С. 80. — 208 с.
5. Теория конфигураций и теория перечислений  (билдәһеҙ). Дата обращения: 30 декабрь 2009. Архивировано 23 ғинуар 2010 года.
6. Глава 3. Элементы комбинаторики 2010 йыл 4 ғинуар архивланған.. // Лекции по теории вероятностей.
7. Дональд Э. Кнут — Искусство программирования. Том 1. Основные алгоритмы. 1.2.5. Перестановки и факториалы

Әҙәбиәт

• Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0.
• Кострикин А. И. Введение в алгебру. Основы алгебры. — М.: Физматлит, 1994. — С. 59-71. — 320 с. — ISBN 5-02-014644-7.
• Сергей Мельников. Перестановки, сочетания, размещения: вывод всех перестановок // Delphi и Turbo Pascal на занимательных примерах. — БХВ-Петербург, 2012. — 448 с. — ISBN 978-5-94157-886-3.

Һылтанмалар

• Аранжеман // Брокгауз һәм Ефрондың энциклопедик һүҙлеге: 86 томда (82 т. һәм 4 өҫтәмә том). — СПб., 1890—1907. (рус.)