Permutació

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

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 ${\displaystyle \{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".^[2]

Alternativament es pot considerar ${\displaystyle n}$ objectes diferents, representats per: ${\displaystyle a,b,c,d,...}$ fins a l'enèsim. De quantes maneres es poden disposar aquests ${\displaystyle 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.^[3]

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.^[4]

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.^[5]

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.^[6]

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.^[7]

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.^[8] 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.^[9] En les matemàtiques modernes, hi ha moltes situacions semblants en les quals la comprensió d'un problema requereix estudiar determinades permutacions relacionades.^[10]

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.^[11][12]

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 ${\displaystyle \sigma (1)=1}$, ${\displaystyle \sigma (2)=3}$ i ${\displaystyle \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${\displaystyle A\,\!}$ de ${\displaystyle n\,\!}$ elements, el nombre de permutacions diferents possibles és igual al factorial de n:^[13]
${\displaystyle n!=n(n-1)(n-2)\cdots 2\,\!}$.

Demostració

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

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

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

Variacions

A aquest nombre se l'anomena ordenacions o arranjaments de n en k. Altres notacions són ${\displaystyle P_{k}^{n}}$ o ${\displaystyle \left[{n \atop k}\right]}$ (en algunes parts del món se'l coneix com a variacions i es denota ${\displaystyle 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 ${\displaystyle 1,2,3,...,n}$, i en la segona les imatges corresponents als elements reordenats ${\displaystyle \sigma (1),\sigma (2),\sigma (3),...,\sigma (n)}$.
Per exemple, donat el conjunt ordenat ${\displaystyle \{1,...,8\}}$ podem expressar una permutació ${\displaystyle \sigma }$ sobre aquest mitjançant una matriu de correspondències:

${\displaystyle \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 ${\displaystyle \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:

${\displaystyle \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}}}$

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, ${\displaystyle \sigma }$ quedaria expressada com composició de dos cicles:

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