Combinatoria

TEMA 4:

COMBINATORIA

PRINCIPIOS BÁSICOS DE RECUENTO

REGLA DE LA SUMA

Siempre que dos tareas no se puedan realizar simultáneamente.

Una se puede hacer de n formas y la otra de m

EN CONJUNTOS:

REGLA DEL PRODUCTO

Si hay m posibles resultados en una primera tarea, y para cada una de las posibilidades de esa etapa hay n para la segunda

De forma que hay m·n posibilidades

De forma que las dos se podrán hacer de m+n formas

PERMUTACIONES

Si A U B=∅ : Card(A U B) Card(A)+Card(B)

Importa el orden

No se admiten repeticiones

El tamaño de la muestra coincide con el total

P(n)=n!

Selección ordenada de todos los elementos de un conjunto finito

Permutaciones con repetición

PR(n;n1,...,nr)=n!/(n1...nr!)

2 casos particulares

Permutaciones circulares

PR(n-1)!

EJEMPLO: Cuando sentamos a 6 personas en una mesa redonda de 6 sillas

Habría 5!=120 maneras de hacerlo

VARIACIONES

Selección ordenada de parte de los elementos de un conjunto finito

Importa el orden

No se admiten repeticiones

El tamaño de la muestra no coincide con el total

V(n,r)=n!/(n-r)!

Variaciones con repetición

VR(n,r)=n^r

COMBINACIONES

Selección sin orden de parte de los elementos de un conjunto finito

C(n,r)=n!/[r!(n-r)!]

No importa el orden

No se admiten repeticiones

El tamaño de la muestra no coincide con el total

En ciertos problemas podemos expresarlas como permutaciones con repetición:

PRn+r-1;n-1,r

Combinaciones con repetición

CR(n,r)=(n+r-1)!/(n-1)!r!

PRINCIPIO DE INCLUSIÓN Y EXCLUSIÓN

Podemos resolver ciertos problemas de combinatoria planteándolos como problemas de cardinales

Permite calcular el cardinal de la unión de varios conjuntos mediante los cardinales de cada uno de ellos y todas sus posibles intersecciones

RECURSIVIDAD

Cuando una definición de un problema se define en términos de versiones más pequeñas se dice que es recursiva

EJEMPLO: El factorial ya que n!=n·(n-1)!

Al valor inicial lo llamaremos:

VALOR SEMILLA

RELACIÓN DE RECURRENCIA LINEAL

Ecuación que expresa el término an de una sucesión en función de k coeficientes constantes de la siguiente manera:

Si c0= 0 es HOMOGÉNEA

Se puede hallar una fórmula general para la solución

Debe llevar el valor inicial y el segundo valor para ser única

RESOLUCION DE UNA RELACIÓN DE RECURRENCIA LINEAL HOMOGÉNEA DE ORDEN 2 CON COEFICIENTES CONSTANTES

Obtenemos condiciones iniciales a1=α y a2=β

Buscamos soluciones particulares de tipo sucesión geométrica an=(kr)^(n-1), siendo k constante

Esto lo haremos resolviendo la ecuación característica de la recurrencia:

[(r^2)-c1][r-c2]=0

Si obtenemos 2 raíces distintas:

Si obtenemos 1 raíz doble:

SUCESIONES GEOMÉTRICAS

Tenemos una sucesión geométrica de orden n si An=A1[r^(n-1)] para todo n perteneciente al conjunto de los números naturales

La suma de los n 1º términos de una progresión geométrica de razón r viene dada por:

Mº Dolores Romero Espejo

Maria Lenzano Álvarez