Tema

4

Combinatoria y recurrencia

Principio de inclusión exclusión. Permutaciones con y sin repetición. Combinaciones con y sin repetición. Fórmulas combinatorias. Teorema binomial. Sucesiones definidas por recurrencia. Resolución de ecuaciones recurrentes por iteración. Relaciones de recurrencia de orden superior con coeficientes constantes. Funciones definidas recurrentemente.

PRINCIPIOS FUNDAMENTALES DEL CONTEO

Regla de la suma :

Si se puede realizar una primera tarea de m maneras, mientras que una segunda se puede efectuar de n maneras, y no se pueden realizar las dos a la vez, entonces tenemos un repertorio de m+n maneras de realizar una tarea.

Regla del producto :

Si un procedimiento se puede separar en las etapas primera y segunda, y si hay m posibles resultados para la primera etapa y n para la segunda, entonces el procedimiento total se puede realizar, en el orden designado, de m·n maneras.

PERMUTACIONES, VARIACIONES, COMBINACIONES.

Para un entero n " 0, n factorial, expresado n!, se define por :

0! = 1,

n! = (n)·(n-1)·(n-2)·...·3·2·1, para n "1

Permutación

Una permutación es una ordenación de los elementos de un conjunto.

En general, si hay n, denominados a1, a2, ..., an, y r es un entero, con 1 "r"n, entonces, por la regla del producto, el

número de disposiciones o permutaciones de tamaño r para n objetos es

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