lunes, 29 de septiembre de 2008

TEORIA DE CONTEO

PERMUTACIONES:

Dado un conjunto finito con todos sus elementos diferentes, llamamos permutación a cada una de las posibles ordenaciones de los elementos de dicho conjunto.
Por ejemplo, en el conjunto {1,2,3}, cada ordenación posible de sus elementos, sin repetirlos, es una permutación. Existe un total de 6 permutaciones para estos elementos: "1,2,3", "1,3,2", "2,1,3", "2,3,1", "3,1,2" y "3,2,1".
La noción de permutación suele aparecer en dos contextos:
Como noción fundamental de
combinatoria, centrándonos en el problema de su recuento.
En
teoría de grupos, al definir nociones de simetría.

Definición alternativa:
La permutación antes citada "1,3,2" puede verse como la imagen de una aplicación σ que lleva la lista inicial de objetos (1, 2, 3) en la lista de objetos reordenados (1, 3, 2). De este modo σ(1)=1, σ(2)=3 y σ(3)=2. También podemos definir a la permutación como la propia aplicación σ.
Así, formalmente, una permutación de un conjunto X es una
biyección de X en sí mismo.
Aunque esta segunda definición generaliza a la primera al admitir conjuntos infinitos, el término permutación se usa principalmente para un conjunto finito X, y así lo haremos en el resto del artículo.

En combinatoria:
La combinatoria trata del número de diferentes maneras que existen de considerar conjuntos formados a partir de elementos de un conjunto dado respetando ciertas reglas. Así un problema combinatorio consiste usualmente en establecer una regla sobre como deben ser las combinaciones y determinar cuantas combinaciones existen que cumplan dicha regla.
Un tipo importante de esas combinaciones son las llamadas permutaciones. Dada una n-tupla ordenada de elementos de un conjunto el número de permutaciones es el número de n-tuplas ordenadas diferentes que pueden construirse a partir de dicho conjunto.


COMBINACIONES:

Una combinación es un arreglo donde el orden NO es importante. La notación para las combinaciones es C(n,r) que es la cantidad de combinaciones de “n” elementos seleccionados, “r” a la vez. Es igual a la cantidad de permutaciones de “n” elementos tomados “r” a la vez dividido por “r” factorial. Esto sería P(n,r)/r! en notación matemática.
Ejemplo: Si se seleccionan cinco cartas de un grupo de nueve, ¿cuantas combinaciones de cinco cartas habría?
La cantidad de combinaciones posibles sería: P(9,5)/5! = (9*8*7*6*5)/(5*4*3*2*1) = 126 combinaciones posibles.