Clase 11 - Combinatoria II

La clase pasada vimos como resolver problemas utilizando el principio del producto, variaciones y combinaciones. Ahora, veremos un par de temas más que son muy útiles a la hora de encarar los problemas.

Como siempre, les proponemos algunas situaciones para que intenten resolver por su cuenta, antes de comenzar ...

A. ¿Cuántos anagramas distintos de 8 letras se pueden formar con las letras de la palabra MADRASTRA? Un anagrama es una ordenación de letras que no tiene por qué tener un significado real.

B. Hallar la cantidad de números de 5 cifras tal que la suma de sus cifras sea igual a 10.

Veamos algunas ideas que pueden ayudar a resolver estas situaciones ...

Una permutación de los elementos de un conjunto es una ordenación de los mismos. Por ejemplo, una permutación de los dígitos del 0 al 9 es la siguiente: 1, 4, 2, 3, 7, 5, 0, 9, 8, 6. Calculemos la cantidad de permutaciones de un conjunto de n elementos. Para el primer lugar tenemos n posibilidades, para el segundo n-1, etc. Entonces por el principio del producto hay n! permutaciones.

Como verán, varios de los problemas de la clase pasada utilizaban el concepto de permutación. Lo interesante que veremos hoy son las permutaciones con repetición. En el ejemplo anterior todos los elementos del conjunto eran distintos, pero ¿qué hubiese pasado si algunos fueran iguales entre sí?

Si tenemos k clases distintas de elementos e(1), e(2), ..., e(k) en un conjunto, y n(1), n(2), ..., n(k) son la cantidad de veces que cada elemento está repetido, entonces la cantidad de permutaciones que se pueden realizar es igual a:

[n(1) + n(2) + ... + n(k)]!
n(1)! n(2) ! ..... n(k)!

Veamos un ejemplo para aclarar mejor las cosas. ¿Cuántos anagramas se pueden formar con las letras de la palabra MATEMATICA? La idea acá, es hallar la cantidad de permutaciones de las letras. Tenemos la siguientes clases de letras: M, A, T, E, I y C. Además tenemos dos letras M, tres A, dos T, una E, una I y una C. Entonces la cantidad de permutaciones es igual a:

(2+3+2+1+1+1)! = 151.200
2! 3! 2! 1! 1! 1!

El otro tema que veremos hoy es distribuciones, es decir una disposición de n objetos iguales en k cajas distinguibles. Esto responde a preguntas como las siguientes:

¿De cuántas formas puedo colocar n bolitas en k cajas?

Si en un restaurante hay 4 platos principales y diez personas hacen un pedido, ¿cuántos pedidos distintos pueden haber?

¿Cuántas distribuciones de edades puede haber en una población de 1000 personas?

Resolvamos el problema para n bolitas distribuidas en k cajas. Podemos suponer que los bordes de las cajas son palitos, por lo que una posible distribución de 7 bolitas en 4 cajas es la siguiente:

oo | o | | oooo

Aquí vemos que en la primer caja hay dos bolitas, en la segunda hay una bolita, la tercer caja está vacía y la cuarta caja tiene 4 bolitas. Fíjense que para cada distribución de bolitas hay una única representación con palitos y circulitos y para cada representación con palitos y circulitos hay una única distribución de bolitas.

Por lo tanto, para contar la cantidad de distribuciones podemos contar la cantidad de formas de ordenar n circulitos y k-1 palitos (fíjense que sólo importa las divisiones entre las cajas y no los extremos).

Esto último puede verse como una permutación con repeticiones por lo que la cantidad de distribuciones es igual a (n+k-1)!/n!(k-1)! = C(n+k-1, n). ¿Se les ocurre como probar esta fórmula usando combinaciones en vez de permutaciones?

Vayamos, entonces, a los problemas que propusimos al principio de la clase. Ahora, es un buen momento para encararlos nuevamente en caso de que no les hayan salido antes.

A. Este problema tiene una pequeña variación con el caso del anagrama de la palabra MATEMATICA, pues en este caso no utilizaremos todas las letras de la palabra, sino que sólo 8 de ellas.

Por lo tanto, debemos ver que pasa en cada caso cuando dejamos una de ellas fuera de la representación.

En total habrá 30.240 posibles anagramas.

B. Este problema, en principio parece un tanto complicado. Sin embargo un buen modelo ayuda muchísimo a la hora de contar. Supongamos que cada cifra (las decenas de mil, las unidades de mil, las centenas, las decenas y las unidades) son 5 cajas, y que cada dígito corresponde a una cantidad de bolitas: al dígito cero no le corresponde ninguna, al 1 una bolita, ..., y al 9 nueve bolitas.

Sin embargo, no podemos hacer las distribuciones así nomás porque para que el número sea de 5 cifras el dígito de las decenas de mil no puede ser el cero. Así que podemos considerar como que en la primer caja ya hay puesta una bolita.

Lo que debemos hacer ahora es contar la cantidad de formas de distribuir las otras 9 bolitas en las 5 cajas, lo cual da C(9+5-1, 9) = C(13, 9) = 715.

Tenemos que tener en cuenta que estamos contando de más pues entre nuestras posibles distribuciones está la que tiene 10 bolitas en la primer caja y ninguna en las demás. Pero, no existe el dígito 10, por lo que debemos restar este caso. Entonces tendremos un total de 714 números de 5 cifras tal que la suma de las cifras es 10.

Para terminar esta clase les dejamos más problemas de combinatoria. No se olviden de contestar la encuesta que está al final de la clase!!!

Problemas

1. Hallar la cantidad de números de 5 cifras tal que la suma de sus dígitos es 11.

2. Hallar la cantidad de anagramas de la palabra ENTUSIASMO que tienen las vocales en orden alfabético.

3. Si en un restaurante hay 4 platos principales y diez personas hacen un pedido, ¿cuántos pedidos distintos pueden haber? ¿Y si al menos una persona pidió cada plato?

4. Fernando tiene 6 jaulas y tiene 10 canarios. ¿Cuántas distribuciones se pueden hacer si no pueden haber dos jaulas en las cuales las cantidades de canarios difieran en más de dos?

5. Hallar la cantidad de números quese obtengan como permutaciones del número 111122256 que sean divisibles por 12?

6. ¿De cuántas formas distintas se pueden sentar n personas en una mesa circular?

Esta fue la décimo primer 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