Mate Discretas

La Combinatoria es la parte de las Matemáticas que se dedica al estudio de los conjuntos finitos.
Puesto que la propiedad principal de estos conjuntos es que se puede representar su número deelementos 
mediante un número natural (llamado cardinal de dicho conjunto), la tarea básica de la Combinatoria es 
precisamente el cálculo del cardinal de dichos conjuntos.
Para dicho cálculo se necesitadefinir los llamados números combinatorios: 
 
        (1) Números factoriales: se define n! mediante la ley de recurrencia
                        n! = n · (n-1)!
                y la condicióninicial 0! := 1. De forma iterativa, se tiene
                        n! = n · (n-1) · (n-2) · ... · 3 · 2 · 1
        n! es el número de permutaciones de n elementos, es decir, es el número totalde formas de ordenar n elementos 
        de todas las formas distintas posibles. 
 
        (2) Coeficientes binomiales: se definen por la fórmula
                        
        El número "nsobre k" es el número de combinaciones de n elementos tomados de k en k, es decir, 
        el número de subconjuntos distintos de k elementos que tiene un conjunto con n elementos.
        Loscoeficientes binomiales tienen dos propiedades básicas:
                (a)
                        
                (b)
                         
 
        Como aplicación de los númeroscombinatorios y del Binomio de Newton, podemos contar el número total de 
        subconjuntos que tiene un conjunto A con n elementos, es decir, el cardinal de partes de A; para ello, notemos 
        que elnúmero de tales subconjuntos se obtiene sumando el número de subconjuntos de 0 elementos más los de 
        1 elemento, más los de 2 elementos, y así hasta los de n elementos, es decir: 
                          
 
        Pero esta cantidad corresponde a desarrollar mediante el binomio de Newton la expresión
                (1+1)n  = 2n
        Así pues se obtiene que #  (A) = 2n si #...