Hola

Capítulo 4

Combinatoria
La combinatoria trata del estudio de las posibles agrupaciones de objetos. Contar el número de objetos
que verifican ciertas propiedades es uno de los objetivos de lacombinatoria. Problemas muy diversos,
como determinar el número posible de apuestas diferentes en una quiniela, el número posible de posiciones
en que unos corredores pueden terminar una carrera, elnúmero posible de matrículas de los coches de
un país o las diferentes formas de distribuir una serie de objetos en cajas son problemas que se abordan
mediante las técnicas de conteo que veremos eneste capítulo.
Lo que pretendemos es por tanto, contar los elementos de un conjunto, o más precisamente, determinar
su cardinal. Dado un conjunto A denotaremos por |A| a su cardinal. Nosotros aquítrataremos únicamente
con conjuntos que tienen un número finito de elementos. En tal caso, se dice que un conjunto A tiene
cardinal n si existe una biyección entre el conjunto A y el conjunto {0, 1, · ·· , n − 1}. Es claro que si dos
conjuntos son biyectivos tienen el mismo cardinal.
A la hora de contar ciertos objetos, lo que haremos será identificar estos objetos con los elementos de
algúnconjunto del cual sepamos determinar su cardinal (es decir, estableceremos una biyección entre el
conjunto de objetos que queremos contar y otro conjunto del cual hallaremos su cardinal).
Paracomenzar, estudiaremos en primer lugar cómo determinar el cardinal de algunos conjuntos.

4.1.
4.1.1.

Métodos elementales de conteo
Principio de inclusión-exclusión

Proposición 4.1.1 (Principio dela suma). Sean A1 y A2 dos conjuntos disjuntos (es decir, A1 ∩A2 =
∅). Entonces |A1 ∪ A2 | = |A1 | + |A2 |.
Intuitivamente está claro lo que significa este principio. No obstante, si quisiéramos unademostración,
ésta se basaría en que los conjuntos {0, 1, · · · , m − 1} y {n, n + 1, · · · , n + m − 1} son biyectivos.
El principio puede extenderse a tres o más conjuntos. En tal caso, dice...