Permutation

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 13 november 2021; kontroller kräver 6 redigeringar .

En permutation i kombinatorik är en ordnad mängd utan upprepningar av siffror , vanligtvis behandlad som en bijektion på mängden , som associerar numret med det -th elementet från mängden. Numret kallas permutationens längd [1] . $1,\ 2,\ \ldots ,\ n,$ ${\displaystyle \{1,\;2,\;\ldots ,\;n\))$ $i$ $i$ $n$

I gruppteorin betyder en permutation av en godtycklig mängd en bijektion av denna uppsättning på sig själv. Som en synonym för ordet "permutation" i denna mening använder vissa författare ordet substitution . (Andra författare kallar substitution för ett visuellt sätt att skriva en permutation. Den större skillnaden är att en substitution är en funktion i sig, medan en permutation är resultatet av att den funktionen appliceras på elementen i en sekvens.)

Termen "permutation" uppstod eftersom föremål först togs, på något sätt arrangerades, och andra sätt att ordna krävde omarrangering av dessa föremål. [2] .

En permutation är en uppsättning som består av samma antal element, som bara skiljer sig i ordningen på elementen. [3]

Egenskaper

Antalet alla permutationer av element är lika med antalet placeringar av by , det vill säga den faktoriella [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

Sammansättning definierar produktens funktion på permutationer av samma längd: Med avseende på denna operation bildar uppsättningen av permutationer av element en grupp , som kallas symmetrisk och vanligtvis betecknas . $(\pi \cdot \sigma )(k)=\pi (\sigma (k)).$ $n$ $S_{n}$

Varje ändlig grupp av element är isomorf till någon undergrupp av den symmetriska gruppen ( Cayleys teorem ). I det här fallet är varje element associerat med en permutation som definieras på elementen av identiteten där är en gruppoperation i . $n$ $S_{n}$ $a\i G$ $\pi _{a}$ $G$ $\pi _{a}(g)=a\cirkel g,$ $\cirkel$ $G$

Relaterade definitioner

Bäraren för en permutation är en delmängd av den uppsättningsom definieras som $\pi \kolon X\till X$ $X$ $\operatörsnamn {supp} (\pi ):=\{x\in X\mid \pi (x)\neq x\}.$

En fast punkt i en permutationär vilken fast punkt som helst i mappningen, det vill säga ett element i mängdenUppsättningen av alla fasta punkter i en permutationär komplementet till dess bärare i. $\pi$ $\pi \kolon X\till X$ $\{x\in X\mid \pi (x)=x\}.$ $\pi$ $X$

En inversion i en permutationär vilket par av indexså attoch. Pariteten för antalet inversioner i en permutation bestämmer permutationens paritet . $\pi$ $i,\ j$ $1\leqslant i<j\leqslant n$ $\pi (i)>\pi (j)$

Särskilda typer av permutationer

En identisk permutation är en permutationsom varje element mappar till sig själv: $e,$ $x\i X$ $e(x)=x.$
En involution är en permutationsom är inversen till sig själv, d.v.s. $\tau ,$ $\tau \cdot \tau =e.$
Disorder är en permutation utan fixpunkter .
En längdcykel är en sådan substitutionpåhela uppsättningenutom för delmängdenochbetecknas. $\aln$ $\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 är en permutation av elementen i en uppsättningsom byter två element. Transponeringen är en cykel av längd 2. $X$

Substitution

En permutation av en uppsättning kan skrivas som en substitution , till exempel: $\pi$ $X$

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

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

Cykelprodukter och permutationstecknet

Varje permutation kan sönderdelas till en produkt ( sammansättning ) av osammanhängande cykler av längd , och på ett unikt sätt upp till ordningen av cyklerna i produkten. Till exempel: $\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 antas också ofta att de fasta punkterna för en permutation är oberoende cykler av längd 1, och de kompletterar permutationens cykelexpansion med dem. För exemplet ovan skulle en sådan utökad sönderdelning vara . Antalet cykler av olika längd, nämligen uppsättningen av siffror , där är antalet cykler av längd , bestämmer permutationens cykliska struktur . I det här fallet är värdet lika med längden på permutationen och värdet är lika med det totala antalet cykler. Antalet permutationer av element med cykler ges av det osignerade stirlingtalet av det första slaget . $(1,\;5,\;2)(3,\;6)(4)$ $(c_{1},\;c_{2},\;\ldots )$ $c_{\ell }$ $\aln$ $1\cdot c_{1}+2\cdot c_{2}+\ldots$ $c_{1}+c_{2}+\ldots$ $n$ $k$ ${\begin{bmatrix}n\\k\end{bmatrix))$

Vilken cykel som helst kan brytas ned till en produkt av (inte nödvändigtvis osammanhängande) transpositioner . I det här fallet kan en cykel av längd 1 (som i huvudsak är en identisk permutation ) representeras som en tom produkt av transpositioner eller, till exempel, som en kvadrat av vilken transponering som helst: En längdcykel kan dekomponeras till en produkt av införlivningar enligt följande: $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 bör noteras att nedbrytningen av cykler till en produkt av transponeringar inte är unik:

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

Således kan vilken permutation som helst brytas upp till en produkt av transponeringar. Även om detta kan göras på många sätt, är pariteten för antalet transpositioner densamma i alla sådana nedbrytningar. Detta gör att tecknet för en permutation ( permutationsparitet eller permutationssignatur ) kan definieras som: $\pi$

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

var är antalet införlivningar i någon expansion av . I det här fallet kallar de en jämn permutation om , och en udda permutation om . $t$ $\pi$ $\pi$ $\varepsilon _{\pi }=1$ $\varepsilon _{\pi }=-1$

På motsvarande sätt bestäms tecknet för en permutation av dess cykelstruktur: tecknet för en permutation av element, bestående av cykler, är lika med $\pi$ $n$ $k$

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

Tecknet på permutationen kan också bestämmas i termer av antalet inversioner i : $\pi$ $N(\pi )$ $\pi$

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

Permutationer med upprepning

Betrakta element av olika typer, och i varje typ är alla element desamma. Sedan kallas permutationerna av alla dessa element, upp till ordningen av samma typ av element, permutationer med upprepning . Om är antalet element av den e typen, då är antalet möjliga permutationer med upprepningar lika med den multinomiala koefficienten $n$ $m$ $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}!}}.$

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

Slumpmässig permutation

En slumpmässig permutation är en slumpmässig vektor, vars alla element tar naturliga värden från 1 till och sannolikheten för att två element matchar är 0. $\xi =(\xi _{1},\;\ldots ,\;\xi _{n}),$ $n,$

En oberoende slumpmässig permutation är en sådan slumpmässig permutation , för vilken: $\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)}}}}

för vissa sådana att: $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.

Om samtidigt inte är beroende av , då kallas permutationen jämnt fördelad . Om det inte finns något beroende av , det vill säga det kallas homogen . $p_{{ij}}$ $i$ $\xi$ $j$ $\forall i,\;j\ (1\leqslant i,\;j\leqslant n)\colon p_{ij}=1/n,$ $\xi$

Se även

Anteckningar

↑ Evgeny Vechtomov, Dmitry Shirokov. Matematik: logik, mängder, kombinatorik . Lärobok för akademisk studentexamen. - 2:a uppl. - Liter, 2018-03-02. - S. 145-146. — 244 sid. Arkiverad 7 april 2022 på Wayback Machine
↑ Matematiklärobok för SPO / M. I. Bashmakov, årskurs 10-11. - s. 67
↑ Sannolikhetsteori och element i matematisk statistik Arkiverad 1 februari 2022 på Wayback Machine
↑ Vilenkin N.Ya. Kapitel III. Kombinatorik av tupler och set. Tilldelningar med upprepningar // Populär kombinatorik . - M. : Nauka, 1975. - S. 80. - 208 sid.
↑ Konfigurationsteori och uppräkningsteori . Datum för åtkomst: 30 december 2009. Arkiverad från originalet den 23 januari 2010. (obestämd)
↑ Kapitel 3. Elements of Combinatorics Arkiverad 4 januari 2010 på Wayback Machine . // Föreläsningar om sannolikhetsteori.
^ Donald E. Knuth - Konsten att programmera. Volym 1. Grundläggande algoritmer. 1.2.5. Permutationer och faktorialer

Litteratur

Donald Knuth . The Art of Computer Programming, volym 3. Sortering och sökning = The Art of Computer Programming, vol.3. Sortering och sökning. - 2:a uppl. - M . : "Williams" , 2007. - S. 824. - ISBN 0-201-89685-0 .
Kostrikin A.I. Introduktion till algebra. Grunderna i algebra . - M .: Fizmatlit , 1994. - S. 59 -71. — 320 s. — ISBN 5-02-014644-7 .
Sergej Melnikov. Permutationer, kombinationer, placeringar: härledning av alla permutationer // Delphi och Turbo Pascal med underhållande exempel. - BHV-Petersburg, 2012. - 448 sid. - ISBN 978-5-94157-886-3 .

Länkar

Arangeman // Encyclopedic Dictionary of Brockhaus and Efron : i 86 volymer (82 volymer och ytterligare 4). - St Petersburg. 1890-1907.