Permutació

Cada una de les sis files és una permutació diferent de tres boles distintes.

En matemàtiques, una permutació d'un conjunt és, en térmens generals, una disposició dels seus membres en una seqüència o orde llineal, o si el conjunt ya està ordenat, una variació de l'orde o posició dels elements d'un conjunt ordenat o una tupla. La paraula «permutació» també es referix a l'acte o procés de canviar l'orde llineal d'un conjunt ordenat.^[1]

Les permutació diferixen de les combinacions, que són seleccions d'alguns membres d'un conjunt sense importar l'orde. Per eixemple, escrites com tuplas, hi ha sis permutació del conjunt {1, 2, 3}, a saber (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) i (3, 2, 1). Estes són totes les ordenacions possibles d'este conjunt de tres elements. Els anagrama de paraules les lletres de les quals són diferents també són permutació: les lletres ya estan ordenades en la paraula original, i el anagrama és una reordenació de les lletres. L'estudi de les permutació de conjunts finitos és un tema important en els camps de la combinatòria i la teoria de grups.

Les permutació s'utilisen en casi totes les branques de les matemàtiques i en molts atres camps de la ciència. En informàtica, s'utilisen per a analisar algoritmes d'ordenació; en física quàntica, per a descriure estats de partícules; i en biologia, per a descriure seqüències d'ARN.

Plantilla:AnchorEl número de permutació de $n$ objectes distints és $n$ factorial, normalment escrit com $n!$ , que significa el producte de tots els sancers positius menors o iguals a $n$ .

Tècnicament, una permutació d'un Conjunt $S$ es definix com una biyección de $S$ a sí mateixa.^[2]^[3] És dir, és una funció de $S$ a $S$ per a la qual cada element ocorre exactament una volta com un valor d'image. Açò està relacionat en el reordenamiento dels elements de $S$ en el que cada element $s$ és reemplaçat pel corresponent $f (s)$ . Per eixemple, la permutació (3, 1, 2) mencionada anteriorment és descrita per la funció $α$ definida com:

α (1) = 3, α (2) = 1, α (3) = 2 .

El conjunt de totes les permutació d'un conjunt formen un grup cridat grup simètric del conjunt. L'operació de grup és la composició (realisar dos reordenamientos donats successivament), que dona com resultat un atre reordenamiento. Com les propietats de les permutació no depenen de la naturalea dels elements del conjunt, solen ser les permutació del conjunt ${1, 2, \dots, n}$ les que es consideren per a estudiar les permutació.

En combinatoria elemental, les $k$ -permutació, o permutació parcials, són els apanys ordenats de $k$ elements distints seleccionats d'un conjunt. Quan $k$ és igual al tamany del conjunt, són les permutació del conjunt.

Definició formal

La definició intuïtiva de permutació, com un ordenament dels elements d'un conjunt es formalisa en l'us del llenguage de funcions matemàtiques.

Una permutació d'un conjunt A és una funció biyectiva de dit conjunt en sí mateixa.

Eixemples:

1. En el cas d'un element A={1} solament hi ha una possible permutació: $(1)$ .

\begin{matrix} A & \overset{I d e n t i d a d}{\to} & A \\ 1 & ⟼ & 1 \end{matrix}

2. En el cas de dos elements A={1,2} solament hi ha dos possibles permutació (ordenaments o posicions de cada element): $(1, 2)$ i $(2, 1)$ .

\begin{matrix} A & \overset{I d e n t i d a d}{\to} & A \\ 1 & ⟼ & 1 \\ 2 & ⟼ & 2 \end{matrix}

,

\begin{matrix} A & \overset{(2, 1)}{\to} & A \\ 1 & ⟼ & 2 \\ 2 & ⟼ & 1 \end{matrix}

3. En el cas de tres elements A={1, 2, 3} cada permutació diferent sobre el conjunt {1, 2, 3} equival a una forma d'ordenar els elements.

\begin{matrix} A & \overset{I d e n t i d a d}{\to} & A \\ 1 & ⟼ & 1 \\ 2 & ⟼ & 2 \\ 3 & ⟼ & 3 \end{matrix}

,

\begin{matrix} A & \overset{(2, 1, 3)}{\to} & A \\ 1 & ⟼ & 2 \\ 2 & ⟼ & 1 \\ 3 & ⟼ & 3 \end{matrix}

,

\begin{matrix} A & \overset{(3, 2, 1)}{\to} & A \\ 1 & ⟼ & 3 \\ 2 & ⟼ & 2 \\ 3 & ⟼ & 1 \end{matrix}

,

\begin{matrix} A & \overset{(1, 3, 2)}{\to} & A \\ 1 & ⟼ & 1 \\ 2 & ⟼ & 3 \\ 3 & ⟼ & 2 \end{matrix}

,

\begin{matrix} A & \overset{(2, 3, 1)}{\to} & A \\ 1 & ⟼ & 2 \\ 2 & ⟼ & 3 \\ 3 & ⟼ & 1 \end{matrix}

,

\begin{matrix} A & \overset{(3, 1, 2)}{\to} & A \\ 1 & ⟼ & 3 \\ 2 & ⟼ & 1 \\ 3 & ⟼ & 2 \end{matrix}

En la definició de permutació, no s'establix condició alguna sobre A, el qual pugues inclús ser infinit. No obstant, és comú considerar únicament el cas en que A és un conjunt finito en estudiar permutació.

En combinatoria

La combinatòria tracta del número de diferents maneres que existixen de considerar conjunts formats a partir d'elements d'un conjunt dau, respectant certes regles, com el tamany, l'orde, la repetició, la partició. Aixina un problema combinatori consistix usualment en establir una regla sobre cóm deuen ser les agrupacions i determinar quàntes existixen que complixquen dita regla. Bàsicament, tres assunts: permutació, combinacions i variacions.

Un tipo important d'eixes agrupacions són les anomenades permutació. Donada una n-tupla ordenada dels elements d'un conjunt, el número de permutació és el número de n-tuplas ordenades possibles.

Fòrmula del número de permutació

Donat un conjunt finito $A$ de $n$ elements, el número de totes les seues permutació és igual a factorial de n:

P_{n} = n! = n (n - 1) (n - 2) \dots 1

Demostració: Ya que hi ha $n$ formes de triar el primer element i, una volta triat est, solament tenim $(n - 1)$ formes de triar el segon element, i aixina successivament, veem que quan apleguem l'element k-ésimo solament tenim $[n - (k - 1)]$ possibles elements per a triar, lo que nos du a que tenim $n (n - 1) (n - 2) \dots 2 \cdot 1$ formes d'ordenar el conjunt, justament lo que enunciem anteriorment.

Eixemple: siga el conjunt A={1,2,3} en este cas hi ha 6 permutació, en forma compacta: 123, 132, 213, 231, 312, 321. En àlgebra, per a estudiar els grups simètrics es presenten entre paréntesis i en dos files, en la primera sempre apareix 1 2 3.

(\begin{matrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{matrix}) .

Un atre eixemple de lo mateix: si es va a formar un comité que involucra president, tesorer i secretari, havent tres candidats a, b, c ; quan s'elegix per sorteig els càrrecs successivament, hi ha sis possibilitats o ordenacions: abc, acb, bac, bca, cab, cba.

En teoria de grups

Notacions

Representació gràfica de la permutació

σ

que revela la seua estructura composta per 2 cicles de llongitut 4.

La primera forma d'escriure una permutació $σ$ , encara que no és la més compacta, consistix en escriure-la en forma de matriu de dos files, situant en la primera els elements ordenats del domini 1, 2, 3,...,n, i en la segona fila les imàgens corresponents als elements reordenados $σ (1), σ (2), σ (3), \dots, σ (n) .$

Per eixemple, donat el conjunt ordenat ${1, ..., 8}$ podem expressar una permutació $σ$ sobre este per mig d'una matriu de correspondències:

σ = (\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & 4 & 5 & 7 & 6 & 1 & 8 & 2 \end{matrix})

Per ser biyectiva per definició, podem trobar una aplicació inversa $σ^{- 1}$ de manera que la seua composició genera l'aplicació identitat. Per a això, en primer lloc intercanviem les files i finalment reordenamos les columnes de modo que els elements del domini queden ordenats de forma natural:

σ^{- 1} = (\begin{matrix} 3 & 4 & 5 & 7 & 6 & 1 & 8 & 2 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \end{matrix}) = (\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 6 & 8 & 1 & 2 & 3 & 5 & 4 & 7 \end{matrix})

Notació de cicles

Existix una atra notació més compacta, cridada notació de cicles. Un cicle és una permutació que intercanvia cíclicamente elements i fixa els restants. Esta notació revela millor l'estructura interna de la permutació. Per a això:

Escomencem en qualsevol element. Ho escrivim, a la seua dreta escrivim la seua image, a la dreta d'esta, l'image de la seua image, i seguim aixina fins que es complete un cicle.
Després agarrem qualsevol element no contingut en el primer cicle, tornem a escriure la seua image a la seua dreta, i continuem fins a completar el segon cicle.
El procés continua fins que la permutació sancera ha quedat descrita com a producte de cicles disjuntos.

Seguint en el mateix eixemple d'abans, en notació de cicles, $σ$ quedaria expressada com a composició de dos cicles:

σ = (1356) (2478)

.

Un cicle de llongitut k és cridat k-cicle.

Descomposició d'una permutació en cicles disjuntos

La descomposició realisada pel procediment anterior no és única en principi, puix podrien haver-se obtingut qualsevol d'estos resultats equivalents:

σ = (1356) (2478) = (2478) (1356) = (8247) (6135) = (3561) (4782) = (5613) (7824) = (6135) (8247)

La descomposició canònica d'una permutació com a producte de cicles s'obté en dos passos (segons Miklós Bóna):

Dins de cada cicle, s'escriu primer l'element més gran;
A continuació, ordenem els cicles en orde creixent segons el primer element de cada cicle.

Freqüentment, solen ometre's els cicles de llongitut 1. Aixina la permutació (1 3)(2)(4 5) s'escriu simplement com (3 1)(5 4) en forma canònica.

Richard P. Stanley crida «representació estàndar» a esta forma,^[4] mentres que Martin Aigner usa el terme «forma estàndar».^[5] Sergey Kitaev també usa el terme «forma estàndar» pero invertix els criteris: en cada cicle es llista primer l'element més chicotet i després els cicles s'ordenen de major a menor segons el primer element.^[6]

Com a curiositat, la forma canònica permet eliminar els paréntesis sense que hi haja pèrdua d'informació, o be recuperar la posició dels paréntesis a partir d'un llistat d'elements sense ells. Per eixemple, usant els criteris de Miklós Bóna, en una forma canònica que haja «perdut» els paréntesis, com 3 1 2 5 4 6, el primer cicle estarà format pel primer element de la llista, 3, i els següents que siguen menors que ell: (3 1 2). El següent element major que el primer (5 > 3) inicia un nou cicle, junt en els següents menors que ell, i aixina successivament. Per lo tant, la forma canònica ha de ser (3 1 2) (5 4) (6).

Descomposició d'una permutació en transposició

Archiu:Symmetric group 4; permutation list.svg

Archiu:Loupe light.svgPermutació de 4 elements

D'esquerra a dreta apareixen les permutació en forma matricial, en forma de vector i com a producte de transposició. Els números a la dreta indiquen la cantitat de transposició en que es pot escriure cada permutació (este número no és únic, pero sí la seua paritat). Les permutació impars estan marcades en vert o taronja.

Una transposició és una permutació que intercanvia dos elements i fixa els restants. Dit d'un atre modo, és un cicle de llongitut 2. Una propietat interessant és que qualsevol permutació es pot construir com una composició de transposició, encara que no de manera única. Donades dos descomposicions en transposició d'una permutació es complix que abdós usaren un número par o abdós usaran un número impar, això permet definir de manera unívoca la signatura d'una permutació.

Les transposició permeten descompondre una permutació qualsevol d'una forma diferent a la descomposició en cicles. En particular, les transposició que apareguen no tindran que ser disjuntas: Per eixemple, el cicle (1 2 3 4) = (1 2) (2 3) (3 4).

Note's la diferència entre permutació, cicle i transposició, donat lo similar de la notació, l'expressió anterior és equivalent a:

(\begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{matrix}) = (\begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 3 & 4 \end{matrix}) \circ (\begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{matrix}) \circ (\begin{matrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4 \end{matrix}) \circ (\begin{matrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 4 & 3 \end{matrix})

La composició senyalada com: $\circ$ s'opera de dreta a esquerra i no és conmutativa.

Ací l'orde d'aplicació és important: en primer lloc (3 4) deixa el 4 en el seu lloc definitiu i el 3 descolocado. Despuix (2 3) deixa en el seu lloc definitiu el 3 i el 2 descolocado, que quedarà recolocado definitivament per (1 2).

Per a vore que qualsevol permutació es descompon com a producte de transposició bastarà vore que tot cicle ho fa. La descomposició no és única. Per eixemple:

(a_{1}, \dots, a_{n}) =

(a_{1}, a_{2}) (a_{2}, a_{3}) \dots (a_{n - 1}, a_{n}) = (a_{1}, a_{n}) (a_{1}, a_{n - 1}) \dots (a_{1}, a_{2}) .

El número de transposició de la descomposició tampoc és únic. Per eixemple:

(a_{1}, \dots, a_{n}) =

(a_{n - 1}, a_{n}) (a_{1}, a_{n - 1}) (a_{n - 1}, a_{n}) (a_{1}, a_{n - 1}) (a_{1}, a_{n - 2}) \dots (a_{1}, a_{2}) .

Pero la paritat del número de transposició de la descomposició sí està determinada. És dir, per a qualsevol parell de descomposicions distintes de $σ$ en n i en m transposició, respectivament, n i m tenen la mateixa paritat (seran simultàneament parells o impar).

Donada una permutació qualsevol, es definix el següent homomorfisme de grups:

a on $S_{n}$ és el grup simètric de n elements i m és un número entero, tal que existixen transposició $τ_{i}$ tals que:

$σ = τ_{1} τ_{2} \dots τ_{m} \in S_{n} .$

Permutació parell i permutació impar

Artícul principal → Paritat d'una permutació.

Cridarem permutació parell (resp. impar) a la que s'escriu com a composició d'un número par (resp. impar) de transposició.

En general, es demostra que la mitat de les n! permutació d'un conjunt de n elements són parells i l'atra mitat impars. Açò sorgix com a conseqüència directa de l'existència del morfismo $ε : S_{n} \to ({- 1, 1}, \cdot)$ que té com a núcleu justament a les permutació pares.

Estructura de grup

Artícul principal → grup simètric.

Dau un número natural $n \geq 1$ , considerem el conjunt $X = {1, 2, ..., n}$ . Definim el grup de permutació de $n$ elements, que denotarem per $S_{n}$ , o lo que és lo mateix, el conjunt d'aplicacions biyectivas de $X$ a $X$ .

Les permutació pares formen un subgrup normal d'índex 2 del grup S_n, al que cridarem grup alternat, i notarem per $A_{n}$ .

Desorde

Permutació completa o desorde és una permutació d'objectes en la que cap dels elements apareix en el seu lloc natural.

Per eixemple: la permutació 23451 és un desorde o permutació completa d'un 12345 ya que cap sifra es troba en la seua posició original. Pero si la permutació fòra 15423 no es consideraria un desorde, degut a que el número 1 es troba en la seua posició natural.

Teorema

El número de permutació completes d'un conjunt de

n

elements és:

P C_{n} = n! (1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + ... + (- 1)^{n} \frac{1}{n!})

Es pot demostrar utilisant el principi d'inclusió-exclusió.

Senya històrica

Archiu:Augustin Louis Cauchy.jpg

Augustin Louis Cauchy

L'estudi de les permutació de les raïls d'equacions algebraiques li va permetre a Galois elaborar els inicis de la teoria de grups i usar este vocablo, per primera volta, en matemàtiques. I va escomençar pels grups no abelianos.

El concepte de permutació apareix en l'obra hebrea Séfer Yetzirah ('El llibre de la creació'), un manuscrit elaborat per un místic entre l'any 200 i el 600. Pero existia ya un resultat anterior de Jenócrates de Calcedonia (396-314 a. C.)^[7]

Vore també

Referències

↑ Webster (1969)
↑ McCoy (1968, p. 152)
↑ <Nering (1970, p. 86)
↑ Stanley, Richard P. (2012). Enumerative Combinatorics: Volume I, Second Edition, Cambridge University Press, p. 23. ISBN 978-1-107-01542-5.
↑ Aigner, Martin (2007). A Course in Enumeration, Springer GTM 238, pp. 24–25. ISBN 978-3-540-39035-0.
↑ Kitaev, Sergey (2011). Patterns in Permutations and Words, Springer Science & Business Mija, p. 119. ISBN 978-3-642-17333-2.
↑ Grimaldi, Ralph: «Matemàtiques discreta i combinatòria» 0-201-65376-1 , pág.44

Bibliografia

(1990).«Introductory Combinatorics».Harcourt Brace Jovanovich.
(2004).«Combinatorics of Permutations».Chapman Hall-CRC.
(2012).«Combinatorics of Permutations».CRC Press.
(2010).«Introductory Combinatorics».Prentice-Hall.
(1994).«Combinatorics: Topics, Techniques, Algorithms».Cambridge University Press.
(1956).«Introduction to the theory of Groups of Finite Order».Dover.
(1976).«A First Course In Abstract Algebra».Addison-Wesley.Reading:
(1987).«Discrete Mathematics and Algebraic Structures».W.H. Freeman and Co..
(1959).«The Theory of Groups».MacMillan.
(1996).«A course in group theory».Oxford University Press.
(1973).«Sorting and Searching».3 This book mentions the Lehmer code (without using that name) as a variant C₁,...,C_n of inversion tables in exercise 5.1.1–7 (p. 19), together with two other variants.
(2005).«Generating All Tuples and Permutations».Addison–Wesley.4 Fascicle 2, first printing.
(1968).«Introduction To Modern Algebra, Revised Edition».Allyn and Bacon.Boston:
(1970).«Linear Algebra and Matrix Theory».Wiley.New York:
(2002).«Advanced Modern Algebra».Prentice-Hall.
(1677).«Campanalogia». The publisher is given as "W.S." who may have been William Smith, possibly acting as agent for the Society of College Youths, to which society the "Dedicatory" is addressed. In quotations the original long "S" has been replaced by a modern short "s".
«Webster's Seventh New Collegiate Dictionary».G. & C. Merriam Company.Springfield:

Referències

Este artícul conté una traducció derivada de «Permutación» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Webster (1969)

[2] McCoy (1968, p. 152)

[3] <Nering (1970, p. 86)

[Stanley2012-4] Stanley, Richard P. (2012). Enumerative Combinatorics: Volume I, Second Edition, Cambridge University Press, p. 23. ISBN 978-1-107-01542-5.

[Aigner2007-5] Aigner, Martin (2007). A Course in Enumeration, Springer GTM 238, pp. 24–25. ISBN 978-3-540-39035-0.

[Kitaev2011-6] Kitaev, Sergey (2011). Patterns in Permutations and Words, Springer Science & Business Mija, p. 119. ISBN 978-3-642-17333-2.

[7] Grimaldi, Ralph: «Matemàtiques discreta i combinatòria» 0-201-65376-1 , pág.44

[1]

[2]

[3]

[4]

[5]

[6]

[7]