Permutation

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 13. november 2021; checks kræver 6 redigeringer .

En permutation i kombinatorik er et ordnet sæt uden gentagelser af tal , sædvanligvis behandlet som en bijektion på sættet , som forbinder tallet med det -te element fra sættet. Tallet kaldes længden af permutationen [1] . $1,\ 2,\ \ldots ,\ n,$ ${\displaystyle \{1,\;2,\;\ldots ,\;n\))$ $jeg$ $jeg$ $n$

I gruppeteori betyder en permutation af et vilkårligt sæt en bijektion af dette sæt på sig selv. Som et synonym for ordet "permutation" i denne betydning bruger nogle forfattere ordet substitution . (Andre forfattere kalder substitution en visuel måde at skrive en permutation på. Den mere væsentlige forskel er, at en substitution er en funktion i sig selv, mens en permutation er resultatet af at anvende denne funktion på elementerne i en sekvens.)

Udtrykket "permutation" opstod, fordi objekter først blev taget, på en eller anden måde arrangeret, og andre måder at bestille på krævede omarrangering af disse objekter. [2] .

En permutation er et sæt bestående af det samme antal elementer, der kun adskiller sig i rækkefølgen af elementerne. [3]

Egenskaber

Antallet af alle permutationer af elementer er lig med antallet af placeringer af ved , det vil sige faktorielle [4] [5] [6] [7] : $n$ $n$ $n$

P_{n}=A_{n}^{n}={\frac {n!}{(nn)!}}={\frac {n!}{0!}}=n!=1\ cdot 2\cdot \ldots \cdot n

Sammensætning definerer driften af produktet på permutationer af samme længde: Med hensyn til denne operation danner sættet af permutationer af elementer en gruppe , som kaldes symmetrisk og normalt betegnes . $(\pi \cdot \sigma )(k)=\pi (\sigma (k)).$ $n$ $S_{n}$

Enhver endelig gruppe af grundstoffer er isomorf til en eller anden undergruppe af den symmetriske gruppe ( Cayleys sætning ). I dette tilfælde er hvert element forbundet med en permutation defineret på elementerne af identiteten , hvor er en gruppeoperation i . $n$ $S_{n}$ $a\i G$ $\pi _{a}$ $G$ $\pi _{a}(g)=a\cirkel g,$ $\cirk$ $G$

Relaterede definitioner

Bæreren af en permutation er en delmængde af sættetdefineret som $\pi \kolon X\til X$ $x$ $\operatørnavn {supp} (\pi ):=\{x\in X\midt \pi (x)\neq x\}.$

Et fikspunkt i en permutationer et hvilket som helst fast punkt i kortlægningen, det vil sige et element i mængden. Sættet af alle faste punkter i en permutationer komplementet af dens bærer i. $\pi$ $\pi \kolon X\til X$ $\{x\in X\midt \pi (x)=x\}.$ $\pi$ $x$

En inversion i en permutationer et hvilket som helst par af indekser, sådan atog. Pariteten af antallet af inversioner i en permutation bestemmer pariteten af permutationen . $\pi$ $i,\j$ $1\leqslant i<j\leqslant n$ $\pi (i)>\pi (j)$

Særlige typer af permutationer

En identisk permutation er en permutation, som hvert element kortlægger til sig selv: $e,$ $x\i X$ $e(x)=x.$
En involution er en permutation, der er det omvendte af sig selv, dvs. $\tau,$ $\tau \cdot \tau =e.$
Lidelse er en permutation uden fikspunkter .
En længdecyklus eren sådan substitution, der er identisk på hele sættetmed undtagelse af delmængdenogbetegnet. $\ell$ $\pi,$ $x,$ $\{x_{1},\;x_{2},\;\ldots ,\;x_{\ell }\}\subset X$ $\pi (x_{\ell })=x_{1},\ \pi (x_{i})=x_{i+1}.$ $(x_{1},\;x_{2},\;\ldots ,\;x_{\ell }).$
En transponering er en permutation af elementerne i et sæt, der bytter to elementer. Transponeringen er en cyklus af længde 2. $x$

Substitution

En permutation af et sæt kan skrives som en substitution , for eksempel: $\pi$ $x$

{\begin{pmatrix}x_{1}&x_{2}&x_{3}&\ldots &x_{n}\\y_{1}&y_{2}&y_{3}&\ldots &y_{n}\ ende{pmatrix}},

hvor og . $\{x_{1},\;\ldots ,\;x_{n}\}=\{y_{1},\;\ldots ,\;y_{n}\}=X$ $\pi (x_{i})=y_{i}$

Cyklusprodukter og permutationstegnet

Enhver permutation kan dekomponeres til et produkt ( sammensætning ) af usammenhængende cyklusser af længde og på en unik måde op til rækkefølgen af cyklusserne i produktet. For eksempel: $\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).

Det antages også ofte, at en permutations fikspunkter er uafhængige cyklusser af længde 1, og de supplerer permutationens cyklusudvidelse med dem. For ovenstående eksempel ville en sådan forøget dekomponering være . Antallet af cyklusser af forskellig længde, nemlig mængden af tal , hvor er antallet af længdecyklusser , bestemmer den cykliske struktur af permutationen. I dette tilfælde er værdien lig med længden af permutationen, og værdien er lig med det samlede antal cyklusser. Antallet af permutationer af elementer med cyklusser er givet ved det usignerede Stirling-tal af den første slags . $(1,\;5,\;2)(3,\;6)(4)$ $(c_{1},\;c_{2},\;\ldots )$ ${\displaystyle 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))$

Enhver cyklus kan dekomponeres til et produkt af (ikke nødvendigvis usammenhængende) transpositioner . I dette tilfælde kan en cyklus af længde 1 (som i det væsentlige er en identisk permutation ) repræsenteres som et tomt produkt af transpositioner eller for eksempel som en kvadrat af enhver transposition: En længdecyklus kan dekomponeres til en produkt af gennemførelsen som følger: $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}).

Det skal bemærkes, at nedbrydningen af cyklusser til et produkt af transpositioner ikke er unik:

(1,\;2,\;3)=(1,\;3)(1,\;2)=(2,\;3)(1,\;3)=(1,\; 3)(2,\;4)(2,\;4)(1,\;2).

Enhver permutation kan således dekomponeres til et produkt af transpositioner. Selvom dette kan gøres på mange måder, er pariteten af antallet af transpositioner den samme i alle sådanne dekomponeringer. Dette gør det muligt for tegnet på en permutation ( permutationsparitet eller permutationssignatur ) at blive defineret som: $\pi$

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

hvor er antallet af transponeringer i en vis udvidelse af . I dette tilfælde kalder de en lige permutation hvis , og en ulige permutation hvis . $t$ $\pi$ $\pi$ $\varepsilon _{\pi }=1$ $\varepsilon _{\pi }=-1$

Tilsvarende er tegnet for en permutation bestemt af dens cyklusstruktur: tegnet for en permutation af elementer, bestående af cyklusser, er lig med $\pi$ $n$ $k$

{\displaystyle \varepsilon _{\pi }=(-1)^{nk))

Tegnet på permutationen kan også bestemmes ud fra antallet af inversioner i : $\pi$ $N(\pi)$ $\pi$

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

Permutationer med gentagelse

Overvej elementer af forskellige typer, og i hver type er alle elementer ens. Derefter kaldes permutationerne af alle disse elementer, op til rækkefølgen af den samme type elementer, permutationer med gentagelse . Hvis er antallet af elementer af den th type, så er antallet af mulige permutationer med gentagelser lig med den multinomiale koefficient $n$ $m$ $k_i$ $jeg$ $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}!}}.$

En permutation med gentagelser kan også opfattes som en kardinalitet multiset permutation . $\{1^{k_{1}},\;2^{k_{2}},\;\ldots ,\;m^{k_{m}}\}$ $k_{1}+k_{2}+\ldots +k_{m}=n$

Tilfældig permutation

En tilfældig permutation er en tilfældig vektor, hvis alle elementer tager naturlige værdier fra 1 til, og sandsynligheden for, at to elementer matcher, er 0. $\xi =(\xi _{1},\;\ldots ,\;\xi _{n}),$ $n,$

En uafhængig tilfældig permutation er en sådan tilfældig permutation , for hvilken: $\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)}}}}

for nogle sådan at: $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.

Hvis på samme tid ikke er afhængig af , så kaldes permutationen ligeligt fordelt . Hvis der ikke er afhængighed af , det vil sige, at det kaldes homogen . $p_{{ij}}$ $jeg$ $\xi$ $j$ $\forall i,\;j\ (1\leqslant i,\;j\leqslant n)\colon p_{ij}=1/n,$ $\xi$

Se også

Noter

↑ Evgeny Vechtomov, Dmitry Shirokov. Matematik: Logik, mængder, kombinatorik . Lærebog for akademisk studentereksamen. - 2. udg. - Liter, 2018-03-02. - S. 145-146. — 244 s. Arkiveret 7. april 2022 på Wayback Machine
↑ Matematik lærebog for SPO / M. I. Bashmakov, klasse 10-11. - s. 67
↑ Sandsynlighedsteori og elementer i matematisk statistik Arkiveret 1. februar 2022 på Wayback Machine
↑ Vilenkin N.Ya. Kapitel III. Kombinatorik af tupler og sæt. Tildelinger med gentagelser // Populær kombinatorik . - M. : Nauka, 1975. - S. 80. - 208 s.
↑ Konfigurationsteori og enumerationsteori . Dato for adgang: 30. december 2009. Arkiveret fra originalen 23. januar 2010. (ubestemt)
↑ Kapitel 3. Elements of Combinatorics Arkiveret 4. januar 2010 på Wayback Machine . // Forelæsninger om sandsynlighedsteori.
↑ Donald E. Knuth - Kunsten at programmere. Bind 1. Grundlæggende algoritmer. 1.2.5. Permutationer og factorials

Litteratur

Donald Knuth . The Art of Computer Programming, bind 3. Sortering og søgning = The Art of Computer Programming, vol.3. Sortering og søgning. - 2. udg. - M . : "Williams" , 2007. - S. 824. - ISBN 0-201-89685-0 .
Kostrikin A.I. Introduktion til algebra. Grundlæggende om algebra . - M .: Fizmatlit , 1994. - S. 59 -71. - 320 sek. — ISBN 5-02-014644-7 .
Sergei Melnikov. Permutationer, kombinationer, placeringer: udledning af alle permutationer // Delphi og Turbo Pascal med underholdende eksempler. - BHV-Petersburg, 2012. - 448 s. - ISBN 978-5-94157-886-3 .