Permutació

De Viquipèdia
Dreceres ràpides: navegació, cerca
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:

Història[modifica | modifica el codi]

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

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[modifica | modifica el codi]

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 σ(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 é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[modifica | modifica el codi]

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[modifica | modifica el codi]

Donat un conjunt finit i ordenatA \,\! 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 només 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[modifica | modifica el codi]

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[modifica | modifica el codi]

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[modifica | modifica el codi]

Notacions[modifica | modifica el codi]

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 σ(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[modifica | modifica el codi]

Representació gràfica de la permutació σ que mostra la seva estructura composta 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[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Permutació Modifica l'enllaç a Wikidata
  1. N. L. Biggs, The roots of combinatorics, Historia Math. 6 (1979) 109−136

Vegeu també[modifica | modifica el codi]