Clase 10 - Combinatoria I

Muchas veces nos encontramos con problemas o situaciones cotidianas en los que debemos contar. ¿De cuántas formas distintas pueden sentarse 10 personas es una mesa circular? ¿De cuántas formas puedo comparar 8 caramelos si quiero que algunos sean de frutilla, otros de menta y otros de naranja? ¿Cuál es la probabilidad de ganar la lotería?

Todos estos problemas que surgen en la vida diaria pertenecen al análisis combinatorio. Esta rama de las matemáticas nos da una herramienta para poder contar de un modo inteligente. Es decir, como contar de un modo breve y sin tener que enumerar todos los casos, cosa que podría tomarnos años o incluso siglos.

Para comenzar esta clase les proponemos tres problemas:

A. Ocho amigos van al cine y todos quieren sentarse en una misma fila. ¿De cuántas formas pueden hacerlo si Pedro y José no se quieren sentar juntos?

B. Con los dígitos 1, 2, ..., 9, ¿cuántos números de 3 cifras distintas podemos formar, con la condición de que la suma de sus cifras sea par?

C. Aníbal quiere ir de su casa hasta el colegio, pasando primero por la casa de Belén. ¿De cuántas formas puede hacerlo si quiere hacer el mínimo recorrido?

Son muchos casos para contar a mano, ¿no? Veamos algunas ideas y fórmulas que pueden ayudar.

El primer concepto es el Principio del Producto:

Supongamos que una experiencia A puede arrojar m resultados, y otra experiencia B puede arrojar n resultados. Entonces la realización conjunta de A y B puede arrojar m.n resultados.

Suena un tanto abstracto, pero no es tan así. Veamos algunos ejemplos que aclaren un poco las cosas. Si quiero vestirme con un pantalón y una camisa y cuento con 4 pantalones y 3 camisas, ¿de cuántas formas puedo vestirme? Resulta bastante obvio que son 4 x 3 = 12 por el principio del producto o haciendo un diagrama de árbol como en la escuela primaria:

Claro que este último método es bastante largo. Imagínense si hubiera tenido 9563 pantalones y 32773 camisas !!!! Vieron que el principio del producto facilita las cosas.

Ahora, analicemos otro caso: ¿Cuántos números de 6 cifras se pueden formar utilizando a lo sumo una vez los dígitos 1, 2, 3, 4, 5, 6, 7 y 8?

Para poder contarlos fácilmente debemos hallar una forma sencilla de construir estos números. Imaginen que tenemos 6 espacios _ _ _ _ _ _ que debemos completar con algunos de los dígitos 1, 2, ..., 8. Para el primer lugar tenemos 8 posibilidades. Para el segundo lugar tenemos 7 posibilidades pues no podemos repetir el dígito ya utilizado; para el tercer lugar hay 6 posibilidades ya que no podemos utilizar los dígitos colocados en los dos primeros espacios, etc.

Entonces por el principio del producto hay 8 x 7 x 6 x 5 x 4 x 3 = 20160 formas de armar lo número, o cantidad de números con las condiciones del enunciado, que es lo mismo.

Esto último nos da pie para introducir un tipo de número que aparecen frecuentemente en combinatoria: los factoriales. El número n!, que se lee "n factorial", cumple:

n! = n(n-1)(n-2)...3.2.1

Así 3! = 3.2.1 = 6; 4! = 4.3.2.1 = 24, etc. Además definimos 0! = 1 pues nos será útil más adelante cuando hablemos de números combinatorios.

Volviendo al problema anterior, el resultado se podría expresar como 8!/2!. Este es un ejemplo de variaciones.

Una variación de n objetos tomados de a m es una selección ordenada de m objetos tomados de un conjunto de n objetos.

En nuestro problema tomamos 6 dígitos de un conjunto de 8 objetos de forma ordenada. Calculemos una fórmula general para la cantidad de variaciones.

Denotaremos con V(n,m) a la cantidad de variaciones de n objetos tomados de a m. Entonces para la primer posición tendremos n posibilidades para el primer lugar, n-1 para el segundo, ...., (n-m+1) para el m-ésimo lugar. Entonces V(n,m) = n(n-1)(n-2) ... (n-m+1) que si se fijan bien es lo mismo que:

V(n,m) = n! / (n-m)!

Aquí va otro problema de variaciones, pero esta vez les toca a ustedes resolverlo:

Un club tiene 150 integrantes entre los que se tiene que elegir un presidente, un vicepresidente, un tesorero y un secretario. ¿De cuántas formas pueden hacerlo?

El último tema que veremos hoy, antes de entrar de lleno a los problemas, es combinaciones.

Una combinación de n elementos tomados de a m es una selección no ordenada de m elementos de un conjunto de n elementos.

Con selección no ordenada queremos decir que no nos importa el orden en que fueron extraídos los elementos del conjunto. Por ejemplo, si queremos saber cuántos conjuntos distintos hay de cuatro números naturales, todos menores o iguales que 10, no nos importará es qué orden fueron extraídos los 4 números del conjunto de los números del 1 al 10.

Cuando contamos la cantidad de variaciones de n elementos tomados de a m, hicimos hincapié en el orden. Ahora bien, fijados m elementos, la cantidad de elecciones ordenadas distintas que podemos hacer de los mismos es m!; por lo que al considerar variaciones, estamos contando m! veces cada selección de m elementos. Entonces la cantidad de combinaciones de n objetos tomados de a m, que denotaremos C(n,m) es igual a V(n,m)/m! o lo que es lo mismo:

C(n,m) = n! / (n-m)!m!

Así, por ejemplo, la cantidad de conjuntos de 4 naturales menores o iguales que 10 es igual a 10! / 6! 4! = 10.9.8.7/4! = 210

Los números combinatorios son muy útiles en muchos temas de matemáticas, como probabilidades, binomio de Newton, etc. que veremos en clases posteriores. Ahora sí, vayamos a los problemas:

A. Parece medio complicado contar la cantidad de formar en que los 8 amigos pueden sentarse si Pedro y José no quieren estar juntos. Más fácil sería contar la cantidad total de formas en que se pueden sentar lo 8 amigos y a este resultado restarle los casos en que José y Pedro están juntos.

Contemos primero la cantidad de formas en que pueden sentarse 8 personas en una fila. Es bastante fácil: para el primer lugar hay 8 posibilidades, para el segundo lugar 7, .... Es decir que por el principio del producto hay 8.7.6.5.4.3.2.1 = 8! formas de que se sienten.

Calculemos ahora la cantidad de casos en los que José y Pedro están juntos. Parece difícil, ¿no? La idea es que si están juntos los podemos considerar como un bloque, formado por dos personas. Entonces ahora tenemos 7 objetos para ubicar (6 son personas y el restante es el bloque Pedro-José). Esto claramente tendrá 7! formas para hacerse.

Sin embargo no contamos todas las posibilidades, pues habrá casos donde Pedro esté a la izquierda de José y otros donde estén intercambiados. Es decir, que en total hay 7!.2 casos en lo que José y Pedro están juntos.

Ahora simplemente restamos: 8! - 7!.2 = 30240 posibilidades.

B. Este problema no se puede resolver utilizando simplemente una fórmula. De hecho, la mayoría de los problemas de combinatoria requieren cierto análisis y es necesario separar en casos antes de que sea posible aplicar las fórmulas de variaciones o combinaciones.

El tema aquí es que para que la suma de las cifras sea impar tenemos dos casos:

Caso 1: las tres cifras son impares

Entonces debemos elegir 3 números impares del conjunto {1, 3, 5, 7, 9} donde importa el orden. Es decir, es una variación de 5 objetos tomados de a 3. Entonces hay 5!/2! = 60 posibles números.

Caso 2: hay una cifra impar y dos impares

Este caso es más difícil que el anterior, porque debemos elegir 2 números del conjunto {0, 2, 4, 6, 8} y uno del conjunto {1, 3, 5, 7, 9} luego ordenarlos, y además tener en cuenta que el número no puede empezar en cero pues sino no sería de 3 cifras.

La cantidad de formas de elegir dos números de {0, 2, 4, 6, 8} sin importar el orden es C(5,2) que es igual a 5! / 3!2! = 10, La cantidad de formas de elegir un número del conjunto de los dígitos impares es C(5,1) = 5. Entonces por el principio del producto tenemos 50 formas de elegir los tres dígitos. Para cada grupo de 3 dígitos elegido habrá 3! = 6 posibles números. Por ejemplo, si elegimos los dígitos 2, 8 y 9 se pueden formar los números 289, 298, 829, 892, 928 y 982. Por lo que habrá un total de 50x6 = 300 números.

Sin embargo, contamos los números que comienzan con 0 por lo que ahora debemos restárselos. Contemos la cantidad de números de la forma 0ab donde en el conjunto {a,b} hay un dígito par distinto de cero y un dígito impar (recuerden que en total debía haber dos dígitos pares y uno impar). Hay 4 formas de elegir el dígito par (el cero ya está elegido) y 5 de elegir el impar, entonces hay 20 formas de elegir a los dígitos a y b. Por cada forma escogida hay dos números, uno donde a es par y otro donde a es impar. Entonces hay 40 números que empiezan con cero.

Por lo tanto, si hay un dígitos impar y dos pares, la cantidad de números es 300 - 40 = 260.

Sumando las posibilidades del primer caso tenemos un total de 320 números. ¡Muchos para contarlos a mano! ¿no?

C. Es fácil ver que cualquier camino que tome Aníbal desde A hasta B no condiciona en nada al camino que tome luego, desde B a C. Así que podemos calcular la cantidad de formas que tiene Aníbal para ir de A a B y luego multiplicarla por la cantidad de formas de ir desde B a C.

Estas cuentas pueden hacerse a mano, pero ¿como habrían hecho si el mapa tuviera más calles?

Para que el camino de A a B sea mínimo, Aníbal debe caminar siempre hacia la derecha o hacia arriba y nunca para abajo o para la izquierda (pues estaría volviendo). Entonces deberá ir dos veces para arriba y 3 veces a al derecha.

Si el símbolo ^ indica que subió una cuadra y el símbolo > indica que fue a la derecha entonces los caminos estarán determinado inequívocamente por combinaciones del tipo >^^>>, ^>>^>, >>^>^, etc. Veamos cuantas formas tenemos de colocar los símbolos.

Para ello, consideremos como distintas los tres símbolos > y los dos ^ poniéndoles colores. Entonces queremos ver la cantidad de formas de ordenar los símbolos >, >, >, ^, ^. Claramente son 5! formas pues hay 5 posibilidades para el primer lugar, 4 para el segundo, etc.

Ahora bien, como en realidad los símbolos ^ y ^ son iguales cada ordenación de nuestros símbolos negros fue contada dos veces una donde primero esta ^ y otra donde primero estaba ^.

Del mismo modo, cada ordenación de los símbolos negros fue contada 3! veces según el orden en que aparecían >, > y >.

Por lo tanto en total habrá 5! / 3!.2 = 10 ordenaciones de símbolo, o lo que es lo mismo, de caminos. En general si queremos ordenar n símbolos X y m símbolos Y tenemos (n+m)!/n!m! formas, que justamente es C(n+m, n).

La cantidad de formas de ir de B a C se cuenta de la misma manera sólo que ahora habrán dos símbolos ^ y cuatro >. Por lo que la cantidad de formas de ir de B a C es C(6, 2) = 15.

Entonces la cantidad de caminos que puede tomar Aníbal es 150. Calculemos por curiosidad de cuantas formas podía ir Aníbal desde A hasta C, pasando o no por B. Fíjense que hay que ordenar 7 símbolos > y 4 ^ lo cual se puede hacer de C(7+4, 7) = 330. Es decir que casi la mitad de los caminos desde A hasta C pasan por B. Sorprendente, ¿no?

Las fórmulas e ideas que vimos hoy se fijan bien sólo con la resolución de problemas así que les dejamos unos cuantos problemas para que practiquen.. Si quieren ampliar un poco los temas les sugerimos que vean estos libros:

-Becker, Pietrocola, Sanchez, Notas de Combinatoria, Red Olímpica, Buenos Aires, 1996.

-Guzmán, Colera, Salvador, Matemáticas - Bachillerato 1, Anaya, Barcelona, 1987.

Ambos pueden conseguirse en la OMA.

Problemas

1. ¿Cuántos números de 6 cifras hay con la condición que no todas sean distintas?

2. Hallar la suma de todos los números de 5 cifras distintas que utilicen como dígitos solamente a los números 1, 2, 3, 4 y 5.

3. Pedro vive a 10 cuadras de María, pero no se acuerda cuantas cuadras hacia el norte y cuantas hacia el oeste eran. Lo único que recuerda es que la cantidad de formas que tenía para ir era menor que 250 y mayor que 150. ¿Cuántas cuadras al norte está la casa de María?

4. En el problema C de la clase de hoy. ¿De cuántas formas distintas puede ir Aníbal desde A hasta C con un camino de exactamente 13 cuadras si no puede salirse del mapa?

5. Cuatro matrimonios van al cine y se sientan en una misma fila. ¿De cuántas formas pueden hacerlo si cada marido tiene que sentarse junto a su mujer?

6. ¿Cuántos múltiplos de 9 hay que sean de la forma 9_ _ 1 _ ?

7. Tengo 4 pares de zapatillas, 4 pantalones y 4 camisas, que son azules, verdes, rojas o negras (una de cada una). ¿De cuántas formas puedo vestirme si el pantalón y las zapatillas tienen que ser de distintos color, y la camisa y el pantalón deben ser de distintos color?

8. ¿Cuántos subconjuntos tiene un conjunto de n elementos?

9. Hallar la suma C(n,0) + C(n, 1) + ... + C(n, n-1) + C(n, n).

10. Probar que C(n, k) + C(n, k+1) = C(n+1, k+1).

11. Una termita camina por el interior de una ladrillo de madera de 3x4x5 que está dividido en cubitos de lado 1. ¿Cuántos caminos de longitud mínima tiene para ir desde un vértice del ladrillo al vértice opuesto?

Esta fue la décima clase de Miscelánea, el curso de matemáticas por Internet. Esperamos que les haya gustado. En quince días, ofreceremos una nueva clase.

Ahora, es el turno de ustedes. Queremos que hagan los problemas y ejercicios que fuimos dando a lo largo de la clase. Cuéntennos lo que consiguieron y pregunten lo que no les salió. Envíen sus preguntas, dudas, sugerencias, experiencias y propuestas. Nuestra dirección es misc@oma.org.ar .

También nos gustaría saber tu opinión sobre esta clase. Te pedimos que te tomes unos instantes y contestes estas preguntas. Con tu ayuda podremos hacer un curso cada vez mejor.

Miscelánea OmaNet	Internet vía OmaNet    www.oma.org.ar/omanet | omanet@oma.org.ar
mensajes webmaster@oma.org.ar