Permutació

Les 6 permutacions de 3 boles

Permutació en matemàtiques, és una noció que té significats lleugerament diferents, tots ells relacionats amb l'acte de permutar (rearranjar) objectes o valors.

Les permutacions ocorren, en maneres més o menys prominents, en gairebé cada domini de les matemàtiques. Les permutacions sorgeixen, també, en l'estudi de l'algorisme d'ordenació en informàtica.

Donat un conjunt finit, la permutació és cadascuna de les possibles ordenacions de tots els elements d'aquest conjunt.

Per exemple en el conjunt $\{1,2,3\}$, cada ordenació possible dels seus elements, sense repetir-los, és una permutació. Hi a en total 6 permutacions per a aquests elements: "1,2,3", "1,3,2", "2,1,3", "2,3,1", "3,1,2" i "3,2,1".

Alternativament es pot considerar $n$ objectes diferents, representats per: $a,b,c,d,...$ fins a l'enèsim. De quantes maneres es poden disposar aquests $n$ elements disposant-los en una línia recta? Aquestes maneres d'ordenar tals elements es diuen permutacions.

La noció de permutació acostuma a aparèixer en dos contexts:

• Com noció fonamental de combinatòria, centrant-se en el problema del seu recompte.
• En teoria de grups, al definir els grups simètrics.

Les permutacions es fan servir en gairebé totes les branques de les matemàtiques i en molts altres camps de la ciència. En informàtica, s'utilitzen per analitzar algorismes d'ordenació; en física quàntica, per descriure estats de partícules; i en biologia, per descriure seqüències d'ARN.

El nombre de permutacions de n objectes diferents és n factorial, normalment escrit com n!, que significa el producte de tots els enters positius menors o iguals a n.

Història

Ja al voltant de l'any 1000 abans de Crist es van utilitzar permutacions anomenades hexagrames a la Xina en el llibre Yijing.

A l'Antiga Grècia, Plutarc va escriure que Xenòcrates (396–314 a.C.) va descobrir el nombre de diferents síl·labes que eren possibles en el grec. Aquest podria ser el primer intent de què es té constància de resoldre un problema difícil en permutacions i combinacions.

Al-Khalil (717–786), un criptògraf i matemàtic àrab, va escriure el Llibre de Missatges Criptogràfics. Conté el primer ús de les permutacions i combinacions, en el llistat de totes les possibles paraules de l'àrab amb i sense vocals.

La regla per a determinar el nombre de permutacions de n objectes era coneguda en la cultura Hindú com a mínim des d'aproximadament 1150: el Lilavati pel matemàtic indi Bhaskara II conté un passatge que es tradueix com

El producte de la multiplicació de les sèries aritmètiques que comencen i s'incrementen per unitat i continuada pel nombre de llocs, seran les variacions del nombre amb figures específiques.

Cap a 1770, Joseph Louis Lagrange, en l'estudi d'equacions polinomials, observà que les propietats de les permutacions d'arrels d'una equació estan relacionades amb les possibilitats de resoldre-les. Aquesta línia de treball va resultar en la teoria de Galois d'Évariste Galois, que ofereix una descripció completa del que és possible i impossible pel que fa a la resolució d'equacions polinomials (amb una incògnita) per radicals. En les matemàtiques modernes, hi ha moltes situacions semblants en les quals la comprensió d'un problema requereix estudiar determinades permutacions relacionades.

Les permutacions van tenir un paper important en la criptanàlisi de la màquina Enigma, un dispositiu de xifrat utilitzat per l'Alemanya nazi durant la Segona Guerra Mundial. En particular, una propietat important de les permutacions, és a dir, que dues permutacions es conjuguen exactament quan tenen el mateix tipus de cicle, va ser utilitzada pel criptòleg Marian Rejewski per desxifrar el xifrat de la màquina al torn dels anys 1932-1933.

Definició alternativa

La permutació abans citada "1,3,2" pot veure's com la imatge d'una aplicació injectiva σ de la llista inicial d'objectes (1, 2, 3) en la llista d'objectes reordenats (1, 3, 2). D'aquesta manera $\sigma (1)=1$, $\sigma (2)=3$ i $\sigma (3)=2$. També podem definir la permutació com la mateixa aplicació σ.

Així, formalment, una permutació d'un conjunt X és una bijecció de X en ell mateix.

Encara que aquesta segona definició generalitza la primera a admetre conjunts infinits, el terme permutació es fa servir principalment per a un conjunt finit X, i així es farà en la resta d'aquest article.

En combinatòria

La combinatòria tracta del nombre de diferents maneres que existeixen de considerar conjunts formats a partir d'elements d'un conjunt donat, respectant certes regles. Així un problema combinatori consisteix usualment a establir una regla de com han de ser les combinacions i determinar quantes existeixen que compleixen la regla.

Recompte del nombre de permutacions

Donat un conjunt finit i ordenat$A\,\!$ de $n\,\!$ elements, el nombre de permutacions diferents possibles és igual al factorial de n:
$n!=n(n-1)(n-2)\cdots 2\,\!$.

Demostració

Donat que hi ha $n\,\!$ formes d'escollir el primer element i, una vegada escollit aquest, només tenim $(n-1)\,\!$ formes d'escollir el segon element, i així successivament, veiem que quan arribem a l'element k-èsim només tenim $(n-k+1)\,\!$ possibles elements per a escollir, el que ens porta a que tenim $n(n-1)(n-2)\cdots 2\cdot 1\,\!$ formes d'ordenar el conjunt, justament el que enunciàvem anteriorment. $\Box \,\!$

Recompte del nombre de conjunts ordenats de k elements amb k<n

Donat un conjunt $A$ finit de cardinal $n$, tenim $P(n,k)={\frac {n!}{(n-k)!}}$ formes de construir un conjunt ordenat $B$ de $k$ elements on $k\leq n$.

Variacions

A aquest nombre se l'anomena ordenacions o arranjaments de n en k. Altres notacions són $P_{k}^{n}$ o $\left[{n \atop k}\right]$ (en algunes parts del món se'l coneix com a variacions i es denota $V_{k}^{n}$).

En teoria de grups

Notacions

La primera forma d'escriure una permutació σ, encara que no la més compacta, consisteix a escriure-la en forma de matriu de dues fileres, situant a la primera filera els elements del domini $1,2,3,...,n$, i en la segona les imatges corresponents als elements reordenats $\sigma (1),\sigma (2),\sigma (3),...,\sigma (n)$.
Per exemple, donat el conjunt ordenat $\{1,...,8\}$ podem expressar una permutació $\sigma$ sobre aquest mitjançant una matriu de correspondències:

$\sigma ={\begin{pmatrix}1&2&3&4&5&6&7&8\\3&4&5&7&6&1&8&2\end{pmatrix}}$

Clarament és bijectiva, ja que podem trobar una aplicació inversa $\sigma ^{-1}$ de forma que la seva composició genera l'aplicació identitat. Per a això, en primer lloc intercanviem les fileres i finalment reordenem les columnes de manera que els elements del domini queden ordenats de manera natural:

$\sigma ^{-1}={\begin{pmatrix}3&4&5&7&6&1&8&2\\1&2&3&4&5&6&7&8\end{pmatrix}}={\begin{pmatrix}1&2&3&4&5&6&7&8\\6&8&1&2&3&5&4&7\end{pmatrix}}$

Representació gràfica de la permutació σ que mostra la seva estructura composta per 2 cicles de longitud 4.

Notació de cicles

Hi ha una altra notació més compacta anomenada notació de cicles. Un cicle de longitud s és una permutació que intercanvia cíclicament s elements i fixa els restants.

Seguint amb el mateix exemple anterior, en notació de cicles, $\sigma$ quedaria expressada com composició de dos cicles:

$\sigma =(1\ 3\ 5\ 6)(2\ 4\ 7\ 8)$

Referències

Bibliografia complementària

• Bogart, Kenneth P. Introductory Combinatorics (en anglès). 2a edició. Harcourt Brace Jovanovich, 1990. ISBN 978-0-15-541576-8. 
• Bona, Miklos. Combinatorics of Permutations (en anglès). 2a edició. CRC Press, 2012. ISBN 978-1-4398-5051-0. 
• Brualdi, Richard A. Introductory Combinatorics (en anglès). 5th. Prentice-Hall, 2010. ISBN 978-0-13-602040-0. 
• Cameron, Peter J. Combinatorics: Topics, Techniques, Algorithms (en anglès). Cambridge University Press, 1994. ISBN 978-0-521-45761-3. 
• Carmichael, Robert D. Introduction to the theory of Groups of Finite Order (en anglès). Dover, 1956. ISBN 978-0-486-60300-1. 
• Fraleigh, John B.. A First Course In Abstract Algebra (en anglès). 2nd. Reading: Addison-Wesley, 1976. ISBN 0-201-01984-1. 
• Gerstein, Larry J. Discrete Mathematics and Algebraic Structures (en anglès). W.H. Freeman and Co., 1987. ISBN 978-0-7167-1804-8. 
• Hall, Marshall Jr. The Theory of Groups (en anglès). MacMillan, 1959. ISBN 9780486828244. 
• Humphreys, J. F.. A course in group theory (en anglès). Oxford University Press, 1996. ISBN 978-0-19-853459-4. 
• Knuth, Donald E. The Art of Computer Programming: Sorting and Searching, Volume 3 (en anglès). Addison-Wesley Professional, 1998-04-24. ISBN 978-0-321-63578-5. «This book mentions the Lehmer code (without using that name) as a variant C1,...,Cn of inversion tables in exercise 5.1.1–7 (p. 19), together with two other variants» 
• Knuth, Donald. Generating All Tuples and Permutations (en anglès). 4. Addison–Wesley, 2005. ISBN 978-0-201-85393-3. 
• McCoy, Neal H.. Introduction To Modern Algebra, Revised Edition (en anglès). Boston: Allyn and Bacon, 1968. LCCN 68015225. 
• Nering, Evar D.. Linear Algebra and Matrix Theory (en anglès). 2nd. Nova York: Wiley, 1970. LCCN 76091646. 
• Rotman, Joseph J. Advanced Modern Algebra (en anglès). Prentice-Hall, 2002. ISBN 978-0-13-087868-7. 
• Stedman, Fabian; S, F. Campanalogia: Or the Art of Ringing Improved ... To which is Added, Great Variety of New Peals. [The Dedication is Signed F.S., I.e. Fabian Stedman..] (en anglès). W. Godbid, for W.S., 1677. 
• Webster's Seventh New Collegiate Dictionary (en anglès). Springfield: G. & C. Merriam Company, 1969. 

Vegeu també

Viccionari

• Combinació