Tecnico

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 algunos problemassencillos. 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. Problema 2. Las ciudades A, B, yC 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

•

•

•

AC

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 todos los 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 tomemoscomo 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.

24

CAP´ ITULO 2. TEOR´ COMBINATORIA IA

Los tres problemas anteriores tienen caracter´ ı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 resultadogeneral 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 cuatromodelos 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 maneras de completarlo escogiendo un par de zapatos. Por lo tanto el n´mero de u posibles conjuntos de camisa, pantal´n y zapatos es 15 × 4 = 60. o Problema 5. Una costurera...