Aporte Individual

Técnicas de conteo: permutaciones, combinaciones, etc.

Permutaciones

Es un arreglo ordenado que se hace usando algunos o todos los elementos de un conjunto, sin repetirlos. Esto significa que ningún elemento del conjunto aparece más de una vez en el arreglo. Por ejemplo, 312 es una permutación de los dígitos del conjunto {1,2,3}, pero 112 no lo es. ¿Cuántos arreglos diferentes se pueden hacer con las tres letras de la palabra sol usando dos letras al tiempo?

S S

O O

L L

SO, SL, OS, OL, LS, LO Seis posibles arreglos

Definición:

Un arreglo ordenado de r elementos seleccionados de un conjunto de n distintos elementos se llama permutación de n elementos tomados r a la vez ( n ≥ r).

Notación:

Usaremos el símbolo P(n,r) para denotar el número de permutaciones de n objetos diferentes, tomados r a la vez. Así escribimos el número de permutaciones de 5 objetos, tomados 3 a la vez como P(5,3).

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

El 1° se El 2° se El 3° se El r° se

Puede puede puede puede

Escoger escoger escoger escoge de

de n de (n-1) de (n-2) (n(r-1))

formas formas formas formas

Definición de n!:

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

0! = 1

Podemos reescribir P(n,r) como:

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

n!

P (n,r) = ----------

(n-r)!

Ejemplo:

En una pista se encuentran 6 atletas y entran en el carril de los 100 metros. De cuantas maneras se pueden organizar para ganar medallas de oro, de plata y de bronce? Solución Deseamos contar el número de maneras de organizar a 3 de los 6 atletas en la posición ganadora. La solución está dada por:

6!

P(6,3) = ---------- = 12C

(6-3)I

Este problema también se puede resolver usando el principio fundamental de enumeración, puesto que se deben hacer 3 elecciones, con 6 atletas disponibles para la medalla de oro, 5 para la de plata y 4 para la de bronce, encontramos que:

6 * 5 * 4 = 120

Combinaciones

En el análisis anterior estábamos interesados en el número de "n" elementos, donde se consideraba el orden en el que se debían arreglar o escoger, sin embargo, en ciertas aplicaciones el orden de los elementos no es importante. Por ejemplo, si se debe escoger un comité de 2 personas entre 4 estudiantes Angie, Brandon, Cecilia y David,

...