Combinatoria

comCapítulo 6 Combinatoria
6.1 Introducción
Se trata de contar el número de elementos de un conjunto finito caracterizado por ciertas propiedades. Principios fundamentales Supongamos que un procedimiento,  puede hacerse de  maneras. Supongamos que un segundo procedimiento  se puede hacer de  maneras.También supongamos que cada una de las maneras de efectuar  puede ser seguida porcualquiera de las maneras de efectuar  Entonces el procedimiento que consta de  seguido por  se puede efectuar de  maneras. Supongamos que un procedimiento,  puede hacerse de  maneras. Supongamos que un segundo procedimiento,  puede hacerse de  maneras Supongamos además que no es posible que   y  se hagan juntos. Entonces el número de manerascomo se puede hacer o  es    2. Principio de la suma 1. Principio de la multiplicación

6.2 Permutaciones
Sea  un conjunto con  elementos y      Definición 1. Llamaremos una  -permutación de los elementos de  a cualquier relación de  elementos de  en el cual importa el orden relativo. El número total de   permutaciones que se puede formar se denotará por  

Teorema 1.
               

    

Demostración. Se desea escoger  de esos elementos u objetos,      y permutamos el  elegido. Se trata de llenar una caja que tiene  compartimentos, y nos detenemos después que se ha llenado el compartimento  -ésimo. Así, el primer compartimento puede llenarse de  maneras, el segundo de    maneras, . . . . y el  -ésimo compartimento de     maneras. Por tanto por el principio de la multiplicación se puede efectuar el proceso completo de                  

y usando la notación factorial se puede escribir
  

Definición 2. En el caso    la  -permutación se llama permutaciones y su número se denota simplemente por   Teorema 2.    La demostración es inmediata, se deja propuesta.Permutaciones con repetición.
 Sea  el número de permutaciones en el caso en que se acepta repetición de los elementos.

Teorema 3
   

Demostración. Es análoga a la demostración del teorema 1, solo que como se acepta la repetición de los elementos, entonces el primer compartimento puede
llenarse de  maneras, el segundo de  maneras, . . . . y el  -ésimo compartimento de maneras. Por tanto por el principio de la multiplicación

       -veces

Si los elementos de  no son todos distintos si no que hay  iguales entre si,  iguales entre si, hasta  iguales con      y            entonces el número de permutaciones de  los  elementos es:   
Teorema 4.
    

         Demostración. Se deja propuesta.

6.3 Combinaciones
Sea  un conjunto con  elementos y      Definición 3 Llamaremos una  -combinación de los elementos de  a cualquier selección de  elementos de  en la cual no importa el orden relativos. El número de    combinaciones que se forman se denotará por  o    Teorema 5                 Demostración. El número demaneras de elegir  objetos entre  y permutar los  elegidos es  igual a  Sea  el número de maneras de elegir  entre , sin considerar     el orden. Observe que una vez que se han escogido los  objetos hay  maneras de permutarlos. Por tanto, aplicando nuevamente el principio de la multiplicación, se tiene        

Así el número de maneras de elegir  entre  objetosdiferentes, sin considerar el orden está dado por  Sea      

  el número de combinaciones de  elementos que se puede formar con  elementos en el caso en que está permitido la repetición de los elementos.

Teorema 6.
    

Demostración. La demostración se deja propuesta.

6.4 Particiones
Los problemas que intentaremos tratar conducen a las particiones de un...