permutaciones

la definición intuitiva de permutación, como reordenamientos de los elementos de un conjunto se formaliza con el uso del lenguaje de funciones matemáticas

Ejemplos:

1. En el caso de dos elementos {1,2} solo hay dos posibles posiciones: ${\displaystyle (1,\,2)}$ y ${\displaystyle (2,\,1)}$.
2. En el caso de tres elementos {1, 2, 3} cada permutación diferente sobre el conjunto {1, 2, 3} equivale a una forma de ordenar los elementos.

${\displaystyle {\begin{matrix}A&{\xrightarrow {Identidad}}&A\\1&\longmapsto &1\\2&\longmapsto &2\\3&\longmapsto &3\\\end{matrix}}}$, ${\displaystyle {\begin{matrix}A&{\xrightarrow {(2,\,1,\,3)}}&A\\1&\longmapsto &2\\2&\longmapsto &1\\3&\longmapsto &3\\\end{matrix}}}$, ${\displaystyle {\begin{matrix}A&{\xrightarrow {(3,\,2,\,1)}}&A\\1&\longmapsto &3\\2&\longmapsto &2\\3&\longmapsto &1\\\end{matrix}}}$, ${\displaystyle {\begin{matrix}A&{\xrightarrow {(1,\,3,\,2)}}&A\\1&\longmapsto &1\\2&\longmapsto &3\\3&\longmapsto &2\\\end{matrix}}}$, ${\displaystyle {\begin{matrix}A&{\xrightarrow {(2,\,3,\,1)}}&A\\1&\longmapsto &2\\2&\longmapsto &3\\3&\longmapsto &1\\\end{matrix}}}$, ${\displaystyle {\begin{matrix}A&{\xrightarrow {(3,\,1,\,2)}}&A\\1&\longmapsto &3\\2&\longmapsto &1\\3&\longmapsto &2\\\end{matrix}}}$

La combinatoria trata del número de diferentes maneras que existen de considerar conjuntos formados a partir de elementos de un conjunto dado, respetando ciertas reglas, como el tamaño, el orden, la repetición, la partición. Así un problema combinatorio consiste usualmente en establecer una regla sobre cómo deben ser las agrupaciones y determinar cuántas existen que cumplan dicha regla. Básicamente, tres asuntos: permutaciones, combinaciones y variaciones.

Un tipo importante de esas agrupaciones son las llamadas permutaciones. Dada una n-tupla ordenada de los elementos de un conjunto, el número de permutaciones es el número de n-tuplas ordenadas posibles.

La primera forma de escribir una permutación ${\displaystyle \sigma }$, aunque no es la más compacta, consiste en escribirla en forma de matriz de dos filas, situando en la primera los elementos ordenados del dominio 1, 2, 3,...,n, y en la segunda fila las imágenes correspondientes a los elementos reordenados ${\displaystyle \sigma (1),\,\sigma (2),\,\sigma (3),\,\dots ,\,\sigma (n).}$

Por ejemplo, dado el conjunto ordenado ${\displaystyle \{1,...,8\}}$ podemos expresar una permutación ${\displaystyle \sigma }$ sobre éste mediante una matriz de correspondencias:

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

Existe otra notación más compacta, llamada notación de ciclos. Un ciclo de longitud es una permutación que intercambia cíclicamente elementos y fija los restantes. Esta notación revela mejor la estructura interna de la permutación. Para ello:

1. Empezamos con cualquier elemento. Lo escribimos, a su derecha escribimos su imagen, a la derecha de esta, la imagen de su imagen, y seguimos así hasta que se complete un ciclo.
2. Luego cogemos cualquier elemento no contenido en el primer ciclo, volvemos a escribir su imagen a su derecha, y continuamos hasta completar el segundo ciclo.
3. El proceso continúa hasta que la permutación entera ha quedado descrita como producto de ciclos disjuntos.

Siguiendo con el mismo ejemplo de antes, en notación de ciclos, ${\displaystyle \sigma }$ quedaría expresada como composición de dos ciclos:

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

Una trasposición es una permutación que intercambia dos elementos y fija los restantes. Dicho de otro modo, es un ciclo de longitud 2. Una propiedad interesante es que cualquier permutación se puede construir como una composición de transposiciones, aunque no de manera única. Dadas dos descomposiciones en transposiciones de una permutación se cumple que ambas usaran un número par o ambas usarán un número impar, eso permite definir de manera unívoca la signatura de una permutación.

Las trasposiciones permiten descomponer una permutación cualquiera de una forma diferente a la descomposición en ciclos. En particular, las trasposiciones que aparezcan no tendrán que ser disjuntas: Por ejemplo, el ciclo (1 2 3 4) = (1 2) (2 3) (3 4). Aquí el orden de aplicación es importante: en primer lugar (3 4) deja el 4 en su sitio definitivo y el 3 descolocado. Después (2 3) deja en su sitio definitivo el 3 y el 2 descolocado, que quedará recolocado definitivamente por (1 2).

Para ver que cualquier permutación se descompone como producto de trasposiciones bastará ver que todo ciclo lo hace. La descomposición no es única. Por ejemplo:

${\displaystyle (a_{1},\ldots ,a_{n})=}$

${\displaystyle (a_{1},a_{2})(a_{2},a_{3})\cdots (a_{n-1},a_{n})=(a_{1},a_{n})(a_{1},a_{n-1})\cdots (a_{1},a_{2}).}$

El número de trasposiciones de la descomposición tampoco es único. Por ejemplo:

${\displaystyle (a_{1},\ldots ,a_{n})=}$

${\displaystyle (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})\cdots (a_{1},a_{2}).}$