Teoria combinatoria

Cap´
ıtulo 2

Teor´ Combinatoria
ıa
La Teor´ Combinatoria es la rama de las matem´ticas que se ocupa del estudio de las formas de
ıa
a
contar. Aparte del inter´s que tiene en s´ misma, la combinatoria tiene aplicaciones de gran importancia
e
ı
en otras ´reas, y en particular a la Teor´ de Probabilidades.
a
ıa

2.1.

Dos Principios B´sicos.
a

Comencemos por considerar algunosproblemas sencillos.
Problema 1. En una tienda hay cinco modelos de camisa y tres de pantal´n. ¿Cu´ntos conjuntos distintos
o
a
de pantal´n y camisa podemos comprar?
o
La camisa la podemos elegir de cinco maneras distintas. Para cada una de ellas podemos escoger el
pantal´n de tres maneras distintas. Por lo tanto hay 5 × 3 = 15 maneras de escoger un pantal´n y
o
o
una camisa.
Problema2. Las ciudades A, B, y C est´n conectadas seg´n lo muestra la figura 2.1: hay seis caminos
a
u
de A a B y cuatro de B a C. ¿De cu´ntas maneras podemos ir de A a C?
a
Para cada camino que escojamos entre A y B podemos escoger cuatro para continuar hasta C.
Como hay seis caminos entre A y B la respuesta es 6 × 4 = 24.
B

•

.......
.......... .
.
....... ...................
.......................... .
.
.. . .
.. . ..... ..... . ..... . ...
.... .... ...... ........ ....
... .... .... ... .... .... ....
... .... ... .... ..... .... ....
.
... .... .... ..... ........ ...... .....
... .... ..... ..... ........ ...... .....
..
..
.. .... .... ...
........ ...... ........
........ ..... ........
.. .... .... ....
.
.
.
.
.. .... .... ....
.. .
. ...
.. .... ... ....
.. .... .... ...
.. ... ..
.
.. .. ... .... ....
... ... ..
..
.. ..... ..... ....
.. .. ... ... ...
.. .. ..
... ... ...
..
...... .... .... .....
... ... ..
...... ..... ..... ......
..
.
... ... ..
..
... .. ..
..
.... ..
. .. ...
... .. ..
.... ..... ..... .......
.
..
..
... ... ..
..
. . ..
... ... .
. ... ...
..
......... ..... .......
..
.... ... .
...
... .. ..
...
.. ...
.. ... ...
... .. ..
........ ..... ... ...
..
... ... .
...
...
... ....
...... ... . ... ..
....... ..... .... ....
... ....
...
...
... ....
..
..... ... ... ..
.
..... .
..... ..... ..........
...
...
.......
.
.
..
......
.
.......... .... ....
...
.
....
.....
.......... ............
..
.
.
....
....
..
.. ..
......
.. ...... .. .....
.. ..
.....................
....... .....
...........
..............
..
...............
.
.
......

•

•

A

C

Figura 2.1
Problema 3. El conjunto A = {a1 , a2 , . . . , ak } tiene k elementos mientras que B = {b1 , b2 , . . . , bn } tiene
n. ¿Cu´ntos elementos tiene el producto cartesiano A × B?
a
El producto cartesiano A × B est´ formado por todoslos pares ordenados (a, b) donde el primer
a
elemento, a, est´ en A y el segundo, b, est´ en B. Para cada uno de los k elementos de A que
a
a
tomemos como primer miembro del par hay n posibilidades para escoger el segundo a partir de los
elementos de B. Por lo tanto tendremos k × n pares ordenados.

CAP´
ITULO 2. TEOR´ COMBINATORIA
IA

24

Los tres problemas anteriores tienencaracter´
ısticas similares: Se trata de escoger dos elementos, cada
uno de un conjunto distinto y queremos contar el n´mero de maneras de hacer esto. El resultado general
u
puede enunciarse de la siguiente manera:
Principio de Multiplicaci´n. Si tenemos dos conjuntos de k y n elementos, respectivamente, y quereo
mos escoger dos elementos de modo que uno sea del primero y el otro del segundo,esto lo podemos hacer
de k × n maneras.
El principio de multiplicaci´n puede ser aplicado reiteradamente:
o
Problema 4. En la tienda del problema 1 hay tambi´n cuatro modelos distintos de zapatos. ¿De cu´ntas
e
a
maneras podemos escoger un conjunto de camisa, pantal´n y zapatos?
o
Podemos ahora comenzar con cualquiera de los 15 conjuntos de camisa y pantal´n del problema
o
1. Hay cuatro...