Array ( [0] => 14697387 [id] => 14697387 [1] => cswiki [site] => cswiki [2] => Permutace [uri] => Permutace [3] => [img] => [4] => [day_avg] => [5] => [day_diff] => [6] => [day_last] => [7] => [day_prev_last] => [8] => [oai] => [9] => [is_good] => [10] => [object_type] => [11] => 0 [has_content] => 0 [12] => [oai_cs_optimisticky] => ) Array ( [0] => {{Upravit}} [1] => {{Neověřeno}} [2] => '''Permutace''' ''n''-prvkové [[množina|množiny]] je uspořádaná ''n''-tice obsahující každý prvek právě jednou, takže jednoznačně určuje jedno z možných uspořádání těchto prvků. Odtud (řídce užívané) české synonymum pro permutaci '''pořadí'''. Ekvivalentní definice je, že se jedná o ''n''-prvkovou [[Variace (kombinatorika)|variaci]] z ''n'' prvků. [3] => [4] => V [[Kombinatorika|kombinatorice]] se také uvažují ''permutace s opakováním'', zahrnující i taková uspořádání prvků, ve kterém se některé prvky vyskytují vícekrát. [5] => [6] => Obecně je permutace (bez opakování) chápána jako [[bijekce|bijektivní zobrazení]] [[množina|množiny]] na sebe. [7] => [8] => == Permutace bez opakování == [9] => Pokud se prvky ve výběru nemohou opakovat, pak počet všech možných pořadí je určen vztahem [10] => [11] => : \ P(n) = n!, [12] => [13] => kde ''n!'' (čteme "en faktoriál") označuje hodnotu [[posloupnosti]] zvané [[faktoriál]] čísla ''n.'' [14] => [15] => Pokud se hovoří o permutacích prvků, jsou tím obvykle myšleny permutace bez opakování. [16] => [17] => === Příklad === [18] => Mějme tři různé prvky a,b,c. [19] => [20] => Permutace těchto prvků představují skupiny abc, acb, bac, bca, cab, cba. Jejich počet je tedy [21] => [22] => : \ P(3) = 3! = 6 [23] => [24] => == Permutace s opakováním == [25] => Pokud se prvky ve výběru mohou opakovat, pak počet permutací s opakováním z ''n'' prvků je určen jako [26] => [27] => :P'{(k_1,k_2,...,k_n)} = \frac {(k_1+k_2+...+k_n)!}{{k_1!}\cdot{k_2!}\cdot...\cdot{k_n!}}, [28] => [29] => kde se jednotlivé prvky opakují \ k_1,k_2,...,k_n -krát. [30] => [31] => === Příklad === [32] => Mějme skupinu tří písmen a,a,b. Trojice je tedy složena ze dvou prvků (tedy \scriptstyle n=2), přičemž první prvek \scriptstyle a se opakuje dvakrát, tzn. \scriptstyle k_1 = 2, a druhý prvek \scriptstyle b se opakuje jednou, tzn. \scriptstyle k_2 = 1. [33] => [34] => Permutacemi s opakováním získáme trojice aab, aba, baa. Počet těchto trojic je tedy roven [35] => [36] => :P'(2,1) = \frac{3!}{{2!}\cdot{1!}} = 3 [37] => [38] => == Zápis == [39] => Permutace lze zapsat tabulkou, kde v horním řádku je vstupní hodnota [[Funkce (matematika)|funkce]] a v dolním její výsledná hodnota. Nebo se zapisuje jako spojení [[cyklus (algebra)|cyklů]] nebo [[transpozice (algebra)|transpozic]]. [40] => [41] => Permutace je [[Sudá a lichá čísla|lichá]], pokud lze vyjádřit spojením lichého počtu [[cyklus (algebra)|cyklů]] délky 2. Permutace je [[Sudá a lichá čísla|sudá]], pokud lze vyjádřit spojením sudého počtu [[cyklus (algebra)|cyklů]] délky 2. [42] => [43] => === Příklad zápisu === [44] => Pomocí tabulky lze permutaci množiny \{1,2,3,4,5,6\} zapsat jako [45] => :\pi = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 1 & 5 & 2 & 4 &6\end{pmatrix} [46] => [47] => Pomocí cyklů a transpozic lze předchozí permutaci zapsat jako [48] => :\pi = (1,3,5,4,2) = (1,3) \circ (3,5,4,2) = (1,3) \circ (3,5) \circ (5,4) \circ (4,2) [49] => Tato permutace je sudá. [50] => [51] => == Samodružný prvek == [52] => Každý prvek r \in M, pro který platí \pi(r)=r, se nazývá ''samodružným prvkem'' (bodem). V opačném případě se jedná o prvek ''nesamodružný''. [53] => [54] => Naříklad permutace [55] => [56] => :\pi = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 3 & 2 & 5 & 4 &6\end{pmatrix} [57] => má samodružné prvky 1 a 6. [58] => [59] => Jestliže každý prvek permutace je samodružný, pak jde o ''[[identita (matematika)|identickou]] (jednotkovou) permutaci''. [60] => [61] => Počet všech permutací n-prvkové množiny bez samodružných prvků se nazývá [[subfaktoriál]] a značí "!n". [62] => [63] => == Inverzní permutace == [64] => K permutaci [65] => [66] => :\pi = \begin{pmatrix}a_1 & a_2 & ... & a_n \\ b_1 & b_2 & ... & b_n\end{pmatrix} [67] => [68] => je možné vytvořit ''inverzní permutaci'' [69] => [70] => :\pi^{-1} = \begin{pmatrix}b_1 & b_2 & ... & b_n \\ a_1 & a_2 & ... & a_n\end{pmatrix} [71] => [72] => Inverzní permutaci značíme \scriptstyle \pi^{-1} [73] => [74] => Složením permutace \scriptstyle \pi a k ní inverzní permutace \scriptstyle \pi^{-1} získáme identickou permutaci. [75] => [76] => == Skládání permutací == [77] => Mějme na množině M dvě permutace [78] => [79] => :\pi_1 = \begin{pmatrix}a_1 & a_2 & ... & a_n \\ b_1 & b_2 & ... & b_n\end{pmatrix} [80] => :\pi_2 = \begin{pmatrix}b_1 & b_2 & ... & b_n \\ c_1 & c_2 & ... & c_n\end{pmatrix} [81] => [82] => ''Složením permutací'' \pi_1, \pi_2 (hovoříme také o ''součinu permutací'') je permutace [83] => [84] => :\pi = \begin{pmatrix}a_1 & a_2 & ... & a_n \\ c_1 & c_2 & ... & c_n\end{pmatrix} [85] => [86] => (pozor, toto je skládání ''zleva doprava'', někdy se používá opačné) [87] => [88] => [[Násobení|Součin]] permutací zkráceně zapíšeme \pi = \pi_1 \circ \pi_2 [89] => [90] => Násobení permutací není v obecném případě komutativní, tzn. \pi_1 \circ \pi_2 \neq \pi_2 \circ \pi_1. [91] => [92] => === Příklad === [93] => :\pi_1 = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 4 & 3 & 1 & 5 & 2\end{pmatrix} [94] => :\pi_2 = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 2 & 4 & 1 & 3 & 6\end{pmatrix} [95] => [96] => Za použití výše uvedené metody způsobu zápisu permutace vypadají následovně [97] => :\pi_1 = (1, 6, 2, 4) [98] => :\pi_2 = (1, 5, 3, 4) [99] => [100] => Složením permutací \pi_1 a \pi_2 rozumíme permutaci \pi_2 \circ \pi_1 = (1, 5, 3, 4) \circ (1, 6, 2, 4) [101] => Permutace skládáme jako funkce, tedy zprava doleva. Nejprve se podíváme na první prvek permutace \pi_1 . V ní číslo 1 jde na číslo 6. Pak se podíváme kam jde 6 v \pi_2. Permutace \pi_2 o čísle 6 nic neříká, tedy píšeme [102] => [103] => (1 6 [104] => [105] => Teď se podívám kam jde 6 v \pi_1. Na 2. Druhá permutace opět o 2 nehovoří. Tedy pokračujeme v zápisu [106] => [107] => (1 6 2 [108] => [109] => Číslo 2 jde \pi_1 na 4, ale číslo 4 jde v \pi_2 na 1 a tento prvek už máme jako začátek našeho cyklu. Tedy zatím počítáme správně. Pokud by nám vyšlo nějaké číslo, které není na začátku cyklu, pak je někde chyba. Tedy uzavíráme cyklus. [110] => [111] => (1 6 2) [112] => [113] => Teď se podíváme na číslo do permutace vpravo, které jsme ještě nepoužili (není napsáno v již uzavřeném cyklu). Takovým číslem je 4. Číslo 4 jde v \pi_1 na 1 a ta jde v \pi_2 na 5. To zapíšeme [114] => [115] => (1 6 2)(4 5 [116] => [117] => a provedeme tento postup pro zbylá čísla (zde chybí už jenom číslo 5). [118] => Tedy výsledek je [119] => [120] => \pi_2 \circ \pi_1 = (1, 5, 3, 4) \circ (1, 6, 2, 4) = (1, 6, 2)(4, 5, 3) [121] => [122] => Pozn.: Výsledek lze interpretovat také třeba jako (216)(534), neboť (216) = (162) = (621). [123] => [124] => === Vlastnosti === [125] => Máme-li na dané množině M permutace \scriptstyle \pi, \pi_1, \pi_2, \pi_3 \,\! a identickou permutaci \scriptstyle I \,\!, pak platí vztahy [126] => [127] => :\pi_1 \circ ( \pi_2 \circ \pi_3) = ( \pi_1 \circ \pi_2) \circ \pi_3 \,\!
[128] => :\pi \circ I = I \circ \pi = \pi \,\!
[129] => :\pi^{-1} \circ \pi = \pi \circ \pi^{-1} = I \,\! [130] => [131] => To jsou axiomy [[Grupa|grupy]] splněné obecně pro každou množinu permutací P(n), kde grupovým násobením je součin dvou permutací. Tedy množina permutací P(n) společně se skládáním permutací tvoří grupu. [132] => [133] => === Řád permutace === [134] => Máme-li permutaci \scriptstyle \pi, \scriptstyle \pi^k značí permutaci vzniklou ''k''-násobným složením permutace \scriptstyle \pi, tj. \scriptstyle \pi^1 = \pi, \scriptstyle \pi^k = \pi \circ \pi^{k-1}. Řád permutace je nejmenší [[přirozené číslo]] ''k'' takové, pro které platí \scriptstyle \pi^k = I, tj. po ''k'' složeních vznikne identická permutace. [135] => [136] => == Příklad == [137] => Zobrazení \scriptstyle f(a)=a+1 na [[celé číslo|celých číslech]] je permutace. [138] => Máme-li nyní permutaci \scriptstyle g(a) = a-3 definovanou na celých číslech. Pak :f \circ g(a) = f(g(a)) = f(a - 3) = a - 2. [139] => [140] => == Poznámky == [141] => * [[Determinant]] je definován pomocí permutací. [142] => [143] => == Literatura == [144] => * {{Citace monografie [145] => | příjmení = [146] => | jméno = [147] => | příjmení2 = [148] => | jméno2 = [149] => | odkaz na autora = [150] => | titul = Odmaturuj z matematiky [151] => | vydavatel = [[Didaktis]] [152] => | místo = [153] => | rok = 2003 (druhé opravené vydání) [154] => | isbn = 80-86285-97-9 [155] => | kapitola = 35. Kombinatorika [156] => | strany = [157] => }} [158] => [159] => == Související články == [160] => * [[Variace (kombinatorika)|Variace]] [161] => * [[Kombinace]] [162] => * [[Znaménko permutace]] [163] => * [http://cs.wikibooks.org/wiki/Java/Algoritmy/V%C3%BDpo%C4%8Det_permutrac%C3%AD Algoritmus Permutace] [164] => [165] => == Externí odkazy == [166] => * {{Commonscat}} [167] => * {{Otto|Permutace}} [168] => [169] => {{Pahýl}} [170] => [171] => {{Autoritní data}} [172] => {{Portály|Matematika}} [173] => [174] => [[Kategorie:Kombinatorika]] [175] => [[Kategorie:Algebra]] [] => )
good wiki

Permutace

Permutace n-prvkové množiny je uspořádaná n-tice obsahující každý prvek právě jednou, takže jednoznačně určuje jedno z možných uspořádání těchto prvků. Odtud (řídce užívané) české synonymum pro permutaci pořadí.

More about us

About

Expert Team

Vivamus eget neque lacus. Pellentesque egauris ex.

Award winning agency

Lorem ipsum, dolor sit amet consectetur elitorceat .

10 Year Exp.

Pellen tesque eget, mauris lorem iupsum neque lacus.

You might be interested in

,'cyklus (algebra)','Variace (kombinatorika)','Sudá a lichá čísla','množina','posloupnosti','Kategorie:Kombinatorika','faktoriál','Kombinace','transpozice (algebra)','Kombinatorika','bijekce','přirozené číslo'

Bijekce

Faktoriál

Kategorie:Kombinatorika

Kombinace

Kombinatorika

Kombinatorika je matematická disciplína, která se zabývá studiem kombinací, aranžmá a permutací prvků v dané množině.

Množina