# Алмаштырма

Алмаштырма (рус. Перестановка) комбинаторикала — $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)\neq x\}$ тип билдәләнгән аҫкүмәклеге.
$\pi$ алмаштырмаһының хәрәкәтһеҙ нөктәһе тип $\pi \colon X\to X$ сағылышының һәр хәрәкәтһеҙ нөктәһе, йәғни $\{x\in X\mid \pi (x)=x\}$ күмәклегенең элементы атала. $\pi$ алмаштырмаһының бөтә хәрәкәтһеҙ нөктәләре күмәклеге уның $X$-та вәкиленең ҡушымтаһы була.
$\pi$ алмаштырмаһында Инверсия тип һәр шундай индекстар пары $i,\ j$ атала, бында $1\leqslant i<j\leqslant n$ һәм $\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$ алмаштырмаһын бер төрлө тип атайҙар.