Permutación

De Wikipedia, la enciclopedia libre

Informalmente, una permutación es un reordenamiento de una colección de objetos. Por ejemplo, si se tienen tres personas, Pedro, Luis y Carlos, cada una de las diferentes formas de ordenarse en fila:

Pedro-Luis-Carlos, Pedro-Carlos-Luis, Luis-Pedro-Carlos, ...

es una permutación de ellos. También se usa el término permutaciones (o variaciones) para referirse al número de diferentes ordenamientos.

[editar] Definición formal

Dado un conjunto X, una permutación es una función biyectiva $f:X\to X$ . Cuando el conjunto es finito, cada permutación corresponde a un reordenamiento de los elementos sin repetición de las "combinaciones primarias" sobre el reordenamiento.

Por ejemplo, si $X = {a, b, c}$ entonces una función biyectiva de X en sí mismo podría ser

$\begin{matrix}f(a) & = & c \\ f(b) & = & b\\f(c) &=& a \end{matrix}$

la cual corresponde al reordenamiento de a b c dado por c b a.

[editar] Permutaciones de conjuntos finitos

Dado un conjunto de n elementos, el número de formas de disponerlos en forma ordenada (permutarlos) es

$n! =n(n-1)(n-2)\cdots 2\cdot 1$

ya que hay n formas de escoger el primer elemento, luego n-1 formas de escoger el n-2 fomas de escoger el tercero, y así sucesivamente. A cada arreglo ordenado de los elementos se le conoce como una permutación del conjunto

Si del conjunto con n elementos deseamos escoger únicamente k de ellos para ordenarlos, el mismo argumento muestra que hay

$P(n,k)=n(n-1)(n-2)\cdots (n-k+1)$

$P(n,k)=\frac{n!}{(n-k)!}$

formas de realizar la tarea.

El número P(n, k) se conoce como permutaciones de n en k, otras notaciones son $P^n_k$ o $\left[{n\atop k}\right]$ (en algunas partes del mundo se le conoce como variaciones y se denota $V^n_k$ ).

Por la forma en que se definieron, se tienen inmediatamente las siguientes propiedades:

$P(n,n) = n!\,$

$P(n,1)=n\,$

Las permutaciones están ligadas a las combinaciones mediante la siguiente identidad:

$P(n,k) = k!\,C(n,k)$

[editar] Permutaciones circulares

Son permutaciones donde no existe un primer y ultimo lugar. Por ejemplo, n personas sentadas alrededor de una mesa circular, el número de permutaciones en las que puede estar distribuidos. Se calcula fijando un elemento y permutando los demás, por tanto: