Combinatoria Y Recurrencia

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 lasdos 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 posiblesresultados 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 unconjunto.
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 esn • (n-1) • (n-2) • ... • (n-r+1) = (n)(n-1)(n-2) ... (n-r+1) •
(la fracción cuyo resultado es 1, es una movida para llegar al resultado simplificado).
En general, si hay n objetos con n1 deun primer tipo, n2 de un segundo tipo, ..., y nr de un r-ésimo tipo,
donde n1 +n2 +...+nr = n, entonces hay permutaciones de los objetos dados.
Variación (de orden r de A) : Es una secuencia deorden r de los elementos de A
Si son con repetición pueden repetirse elementos.

Combinaciones
Sea A un conjunto finito de n elementos tomados de r en r.
Una combinación de orden r de A esun conjunto de r elmentos distintos y perteneceientes a A.
Si son con repetición pueden repetirse elementos.

En general, dados n objetos distintos de los cuales se quiere seleccionar, conrepetición, r de objetos,
su número sera .
En consecuencia, el número de combinaciones con repetición de objetos, tomados de r en r, es C(n+r-1,r).



Teorema binomial Grimaldi 14
Si...