PERMUTACION ANALISIS COMBINATORIO

Permutación

Dado un conjunto de n elementos, se denomina permutación a cada uno de los conjuntos que se pueden formar con estos elementos tales que cada uno de ellos difiere de otro en el orden en que son considerados los elementos.
Dicho de otro modo, dada una colección de n objetos distintos, cualquier disposición lineal de estos objetos se denomina permutación de la colección.

Pongamos un ejemplo: un grupo de 5 personas va a sentarse en fila para una foto. ¿Cuántas disposiciones lineales son posibles?

   5       4       3       2      1

1a pos  2a pos  3a pos  4a pos  5a pos

Cualquiera de las 5 personas puede ocupar la primera posición de la fila. Para la segunda posición podemos elegir entre 4 personas. Continuando de esta manera, sólo tenemos una persona para ocupar la quinta posición. Esto produce un total de 5.4.3.2.1 = 120 disposiciones posibles de las 5 personas. Se obtiene exactamente la misma respuesta si las posiciones se ocupan en otro orden (por ejemplo, 3ª posición, 1ª posición, 4ª, 5ª y 2ª).

En general, si existen n objetos distintos, el número de permutaciones para los n objetos es

n(n-1)(n-2)...1 = n!

|  |    |     |

|  |    |     n-ésima pos 

|  |    3ª pos 

|  2ª pos 

1ª pos

Pn = n!

Se lee "permutaciones de n".

Ejemplo

Dadas las letras a, b, c existen seis formas de disponerlas: P3 = 3! = 3.2.1 = 6.
Las seis permutaciones son:
a b c
a c b
b a c
b c a
c a b
c b a

Definición

Arreglos

Dado un conjunto de n elementos, se denomina arreglos de tamaño r a todos los conjuntos de r elementos escogidos de entre los n, tales que un conjunto difiere de otro en al menos un elemento o en el orden en que se consideran los elementos.

Consideremos el ejemplo siguiente: en un grupo de 10 personas, se elegirá a 5 y se les ubicará en fila para una foto. ¿Cuántas disposiciones son posibles?

  10       9       8       7      6

------  ------  ------  ------  ------

1a pos  2a pos  3a pos  4a pos  5a pos

Cualquiera de las 10 personas puede ocupar la primera posición de la fila. Para ocupar la segunda posición tenemos 9 personas. Siguiendo de esta manera, hay 6 personas de donde elegir para que ocupen la quinta posición. Esto produce 10.9.8.7.6 = 10.240 disposiciones posibles.

En general, si existen n objetos distintos, y r es un entero, con 0 <= r <= n, entonces el número de arreglos de tamaño r para los n objetos es

                          n!   

n(n-1)(n-2)...(n-r+1) = ------

|  |    |     |         (n-r)! 

|  |    |     r-ésima pos

|  |    3ª pos

|  2ª pos 

1ª pos

n      n!  Ar  = ------        (n-r)!

Se lee "arreglos de n en r".

Ejemplo

Dadas las letras a, b, c podemos formar 6 arreglos de tamaño 2.

 3     3!   3.2.1

A2  = --- = ----- = 6

       1!     1

Los 6 arreglos son:
a b
b a
a c
c a
b c
c b