Алмаштырма

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

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

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

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

## Үҙсәнлектәре
n элементтан бөтә алмаштырмалар һаны n элементтан n-шар  урынлаштырмалар һанына, йәғни n факториалға тигеҙ:
: P_n=A_n^n=\frac {n!}{(n-n)!}=\frac {n!}{0!}=n!=1\cdot 2\cdot\ldots\cdot n.

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

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

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

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

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

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

### Подстановка
X күмәклегенең \pi алмаштырмаһы *подстановка* күренешендә яҙыла ала, мәҫәлән:
: \begin{pmatrix} 
x_1 & x_2 & x_3 & \ldots & x_n \\ 
y_1 & y_2 & y_3 & \ldots & y_n\end{pmatrix},
бында \{x_1,\;\ldots,\;x_n\}=\{y_1,\;\ldots,\;y_n\}=X һәм \pi(x_i)=y_i.

### Циклдар ҡабатландығы һәм алмаштырма тамғаһы
Теләһә ниндәй \pi алмаштырмаһы \ell \geqslant 2 оҙонлоғондағы  *киҫешмәүсе циклдар* ҡабатландығына  (циклдар композицияһына) тарҡатыла ала, шуның менән бергә ҡабатландыҡта циклдарҙың урынлашыу тәртибенә тиклем аныҡлыҡ менән берҙән-бер ысул менән. Мәҫәлән:
: \begin{pmatrix} 
1 & 2 & 3 & 4 & 5 & 6 \\ 
5 & 1 & 6 & 4 & 2 & 3\end{pmatrix} = (1,\;5,\;2)(3,\;6).

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

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

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

Эквивалентлы, алмаштырманың тамғаһы уның цикл структураһы менән билдәләнә: n элементтан, k циклдан торған \pi алмаштырмаһының тамғаһы
: \varepsilon_{\pi} = (-1)^{n-k}-гә тигеҙ.

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

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

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

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

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

*Бәйһеҙ осраҡлы алмаштырма*  тип шундай \xi осраҡлы алмаштырма атала, уның өсөн:
: 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)}}

ҡайһы бер шундай p_{ij} өсөн:
: \forall i\ (1\leqslant i \leqslant n)\colon p_{i1}+\ldots + p_{in}=1
: \sum\limits_{\pi \in S_n}p_{1\pi(1)}\ldots p_{n\pi(n)}>0.

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

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

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

## Иҫкәрмәләр

## Әҙәбиәт
* 
* 
* 

## Һылтанмалар
*