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...
Regístrate para leer el documento completo.