Permutaciones

From MM*Stat International

Jump to: navigation, search
English
Português
Français
‎Español
Italiano
Nederlands


Todo grupo de n elementos que contiene todos los n elementos se denomina permutación de esos elementos. Las diferentes permutaciones de un mismo grupo de elementos se diferencian entre ellas sólo por la ordenación de los elementos. Existen tres tipos de permutaciones:

Permutaciones sin repetición

Las permutaciones sin repetición son aquellas permutaciones e las que cada elemento está contenido sólo una vez, y de esta manera, todos los n elementos son diferentes. El número de permutaciones sin repetición, que denotaremos desde ahora como P(n), es: P(n) = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n = n \,
!

Ejemplos:

  • Para dos elementos diferentes ( y ) el número de posibles permutaciones es P(2)=1 \cdot 2 = 2\,! = 2. Lógicamente, las dos posibles permutaciones son:

y

  • Para tres elementos diferentes (, y ) el número de posibles permutaciones es P(3) = 1 \cdot 2 \cdot 3 = 3\,! = 6. Todas las posibles seis permutaciones son las siguientes:


Permutaciones con repetición

Este tipo de permutaciones nos permite ordenar grupos de elementos en los que algunos elementos son los mismos (estan repetidos). Supongamos que hay g elemntos idénticos entre todos los n elementos en una permutación. El número de posibles permutaciones con repetición de n elementos es denotada como P(n; g) y puede ser generada por la siguiente fórmula: P(n; g) = \frac{n\,!}{g\,!} \qquad g \leq n
\text{ ,} donde g es el número de elementos idénticos (el tamaño de sus grupos).

Ejemplos:

  • Primero, considerese el caso de los dos elementos:

    Para dos elementos distintos ( y ) el número de posibles permutaciones es P(2) = 2\,! / 1\, ! = 2 (que es el mismo que para el caso sin repetición):
    y

    Para dos elementos iguales ( y ) el número de posibles permutaciones es P(2;2) = 2\,!/2\,! = 1. Las únicas permutaciones posibles son:

  • Para un grupo de tres elementos, es posible tener g=1 (lo mismo que para permutaciones sin repetición), g=2 (dos elementos son iguales, mientras que el tercero es distinto) o g=3 (los tres elementos son iguales):

    Para g=1 es el grupo formado por , , y , por lo que el número de posibles permutaciones es P(3) = 3\,!/1\, ! = 6.
    Las seis permutaciones son las siguientes:

    Para g=2 (, , ), el número de posibles permutaciones es P(3;2) = 3\,!/2\, ! = 3.
    Las tres posibles permutaciones son:

    Para g=3 (, , ), el número de posibles permutaciones son P(3;3) = 3\,!/3\, ! = 1
    y la única posible permutación es:

Aparentemente, las permutaciones sin repetición son un caso especial de las permutaciones con repeteción. Las permutaciones con repetición son por lo tanto un caso especial de permutaciones con más grupos de elementos iguales.

Permutaciones con más de un grupo de elementos idénticos

Para permutaciones de este tipo, es posible que existan más grupos (diferentes) de elementos idénticos entre todos los n elementos de una permutación. Para r grupos, el número de permutaciones es P(n;g_1, \dots, g_r) = \frac{n\,!}{g_1\,!
\cdot g_2\,! \cdot \dots \cdot g_r\,!} \text{ } donde g_i representa el tamaño i-esimo grupo y cumple que g_1 + g_2 +
g_3 + \dots + g_r \leq n. Hay 14 participantes en un concurso de belleza. Cada miembro del jurado debe crear su propio orden (o ranking) de las 14 participantes. ?‘Cuantos jurados son necesarios con el fin de tener todos los posibles ordenes (una forma diferente para cada uno) de las 14 participantes si suponemos que tienen gustos distintos? Para crear un ranking, es necesario ordenar los n elementos (14 participantes) de esta forma, cada uno de los miembros del jurado tiene que crear una permutación. Ahora, vamos a tratar de diferenciar entre permutaciones con y sin repetición. Como cada participante puede estar incluida en el ranking de cada jurado una sóla vez, vamos a considerar permutaciones sin repeticíon. P(n) = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n = n! P(14) = 1 \cdot 2 \cdot 3 \cdot \dots \cdot 14 = 14! = 87,178,291,200 Para todos las posibles ordenaciones, más de 87 billones de jurados serían necesarios. Claramente, no sería sencillo encontrarlos ya que la población total de la tierra es aproximadamente de 6 billones.