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ó es 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 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.

Història

La regla per a deterninar 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 nobre 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.

Definició alternativa

La permutació abans citada "1,3,2" pot veure's com l'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 σ(1)=1, σ(2)=3 y σ(3)=2. També podem definir la permutació com la pròpia aplicació σ.

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

Encara que aquesta segona definició generalitza la primera en 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. Aixi un problema combinatori consisteix usualment en 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 a la 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 nomes tenim $(n-k+1) \,\!$ possibles elements per a escollir, el que ens porta aque tenim $n(n-1)(n-2) \cdots 2 \cdot 1 \,\!$ formes d'ordenar el conjunt, justament el que enunciàvem anteriorment. $\Box \,\!$

Recompte del mombre 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^n_k$ o $\left[{n\atop k}\right]$ (en algunes parts del món se'l coneix com variacions i es denota $V^n_k$ ).

En teoria de grups

Notacions

La primera forma d'escriure una permutació σ, encara que no la més compacta, consisteix en 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 σ(1), σ(2), σ(3),...,σ(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 forma 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}$

Notació de cicles

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

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

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Permutació

Vegeu també

• Combinació