Matematicas Discretas(permutacion Y Combinacion)

4.3 PERMUTACIONES Y COMBINACIONES

Una permutación de objetos implica orden mientras que una combinación no toma el orden de los objetos considerados.

Definición:

Dado un conjunto que contiene n elementos distintos X = {x1, x2, .... xn}

a) Una permutación de X es una ordenación de los n elementos x1, x2, .... xn

b) Una permutación–r (ó r-permutación) de X donde r n, es una ordenación de un subconjunto de r elementos de X.

c) El numero de permutaciones-r de un subconjunto de n elementos distintos se denota P(n, r)

d) Una combinación-r (r-combinación) es una selección no ordenada de r elementos de X, es decir, un subconjunto de r elementos de X.

e) El numero de combinaciones-r de un conjunto de n elementos distintos y se denota C(n, r) ó bien .

Ejemplo:

Sea X = {a, b, c}

Algunas permutaciones de X son: abc, acb, bac

Algunas permutaciones-2 de X son: ab, ba, ca

Algunas combinaciones-2 de X son: {a, b}, {a, c}, {b, c}

Teorema:

El número de permutaciones-r de un conjunto de n objetos distintos es

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

La demostración es directa aplicando la regla b) del producto.

Por este teorema el número de permutaciones-2 de X = {a, b, c} es 6, las cuales son: ab, ac, ba, bc, ca, cb

También por este Teorema el número de permutaciones en un conjunto de n elementos es

P(n, n) = (n)(n -1)(n - 2)...(3)(2)(1) = n!

Observese que P(n, r)•(n - r)! = n!, por lo que

Ejemplos:

a) De cuántas maneras se puede seleccionar un presidente, un vicepresidente, un secretario y un tesorero entre un grupo de 10 personas .

La respuesta es P(10, 4) = 10!/(10 - 4)! = 5,040 ó bien 10 • 9 • 8 • 7 = 5,040 maneras diferentes.

b) ¿De cuántas formas puede formarse en una fila 7 mexicanos distintos y 5 gringos distintos si ninguna pareja de gringos puede estar junta?

Podemos formar a los mexicanos y a los gringos mediante un proceso de dos partes. Formando a los mexicanos y a los gringos. Los mexicanos pueden formarse de 7! = 5040 maneras. Una vez formados los mexicanos, como ninguna pareja de gringos puede estar junta, los gringos tienen 8 posiciones en las cuales formarse, es decir:

_ M1 _ M2 _ M3 _ M4 _ M5 _ M6 _ M7 _

Así los gringos pueden formarse de P(8, 5) = 6,720 maneras. Por la regla del producto tenemos que 5,040 • 6720 = 33'868,800 maneras diferentes de formarlos.

c) Se quieren colocar 3 pelotas de color rojo, azul y blanco en cajas numeradas con 1, 2, ... , 10. DEseamos conocer el número de maneras distintas en que las pelotas pueden ser colocadas en cajas, si cada caja es capaz de contener sólo una pelota.

Coloquemos las pelotas una a la vez, iniciando con la pelota roja, luego la azul y después la blanca. Puesto que la pelota roja puede colocarse en cualquiera de las 10 cajas, la azul en cualquiera de las 9 restantes y la blanca en cualquiera de las 8 restantes, el número total de maneras distintas de colocar estas pelotas es 10 • 9 • 8 = 720.

d) ¿De cuantas maneras pueden ser programados tres exámenes dentro de un periodo de 5 días, de modo que el mismo día no sean programados 2 exámenes?

Si consideramos que P(n, r) =(n)(n -1)(n - 2)...(n - r +1) = P(5, 3) = 5 • 4 • 3 = 60 maneras distintas de programas los exámenes.

e) ¿Cuántas permutaciones de las letras ABCDEF contienen la subcadena DEF?

Para garantizar la presencia del patrón DEF en la subcadena, estas 3 letras deben estar juntas y en ese orden. Las letras A, B y C pueden colocarse de manera arbitraria. Así es como tener

...