Cap6

Capí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
1. Principio de la multiplicación
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
serseguida por cualquiera de las maneras de efectuar
Entonces el
procedimiento que consta de
seguido por
se puede efectuar de
maneras.
2. Principio de la suma
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

6.2Permutaciones
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 tienecompartimentos, 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
denota simplemente por-permutación se llama permutaciones y su número se

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 demaneras, 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

elementosy

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 de maneras de elegir
igual a

Sea

objetos entre

y permutar los

el número de maneras de elegir

entre

elegidos es

, sin considerar

el orden. Observe que unavez 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
el orden está dado por

entre

objetos diferentes, sin considerar

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.

Sea

Teorema6.

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

6.4 Particiones
Los problemas que intentaremos tratar conducen a las particiones de un conjunto,
es decir que los elementos u objetos que intervienen deben particionarse en dos o
más conjuntos que verifican ciertas condiciones. Es usual confundirlas con las
permutaciones y combinaciones con repetición, por la similitud de sus fórmulas,
pero losproblemas en si son distintos.
Es conveniente, en lugar de dividir los elementos de un conjunto es pensar que
deben ser separados en cajas.
Teorema 7.
El número de maneras en que se puede dividir objetos distintos en cajas, de
modo que la primera contenga
elementos, la segunda
la última
elementos, de modo que
Demostración.
Se debe seleccionar

elementos de los

objetos, esto es posible hacerlo...