Razonamiento combinatorio (Parte 3 y última)

(Viene de la parte 2.)

Uno, uno, dos, cuatro

¿Cuántos números de cuatro dígitos pueden armarse permutando las cifras 1, 1, 2, 4? Para facilitar el razonamiento, imaginemos que las cifras están escitas en cuatro fichas que, además, identificamos con las letras A, B, C, D. Un número se forma, entonces, eligiendo sucesivamente, cada una de estas cuatro fichas; por ejemplo, si elegimos BDAC, en ese orden, obtendremos el número 1.412.

Sin embargo, a priori, no podríamos aplicar el Principio General de Enumeración, porque (como sucedía en el caso de los triángulos) series de elecciones diferentes pueden generar el mismo número. Por ejemplo, la elección ACDB y la elección BCDA generan el número 1.241 (en negrita, las fichas que tienen la misma cifra). De todos modos, la estrategia consistirá en razonar como si las cuatro fichas fueran diferentes, aplicar el Principio General de Enumeración, y después (como hicimos con los triángulos) modificar el resultado obtenido tomando en cuenta las repeticiones.

Si todas las fichas fueran diferentes, el Principio General de Enumeración nos diría que las formas de ordenar las cuatro fichas son $4\times 3\times 2\times 1 = 24$ (que también podemos escribir como 4!), ya que tendríamos cuatro elecciones para primera ficha, tres para la segunda (que debe ser diferente de la primera), etc. Ahora bien, como ya observamos, algunas de estas 24 elecciones representan el mismo número; por ejemplo, el número 1.124 aparece al elegir ABCD y al elegir BACD; el número 1.421 aparece al elegir ADCB y al elegir BDCA; el número 4.211 aparece al elegir DCAB y al elegir DCBA; y así sucesivamente. Vemos así que, en los 24 resultados que calculamos antes, cada número está contado dos veces; en consecuencia, 24 es el doble de la cantidad real de resultados. La respuesta correcta es, entonces:

$\frac {4\times 3\times 2\times 1}{2} = \frac {4!}{2} = 12$

Formulemos una variante de la pregunta anterior: ¿Cuántos números de cinco dígitos pueden armarse permutando las cifras 1, 1, 1, 2, 4? En otras palabras, tenemos ahora cinco fichas.

Para responder la pregunta, repetimos la estrategia anterior y aplicamos primero el Principio General de Enumeración como si las cinco fichas fueran diferentes. El resultado que obtenemos es 5! = 120. A continuación, tenemos que preguntamos cuántas veces, en esos 120 resultados, está representado cada número. 

Observemos que, si intercambiamos entre sí las fichas A, B, C, el número obtenido es siempre el mismo. Por ejemplo, las elecciones ABCDE y BCADE generan ambas el número 11.124. La pregunta, entonces es ¿cuántas formas hay de intercambiar entre sí las letras A, B, C? Tenemos aquí, una vez más, el problema de los seis amigos que se toman una fotografía en fila, sólo que ente caso los amigos son 3; la respuesta es 3! = 6. Es decir, entre los 120 resultados antes calculados, cada número está contado 3! veces. La respuesta, entonces, es que la cantidad de números es:

$\frac {5!}{3!}=20$

Existe otra forma de razonar este problema, para ello imaginemos que las cinco fichas van a ser colocadas en cinco casilleros en fila.

¿Cómo formamos un número? Elegimos primero los tres lugares en lo que vamos a colocar las fichas con el número 1 (en este razonamiento las letras no juegan ningún papel), luego elegimos la casilla donde estará la ficha con el 2, y finalmente, elegimos el lugar para la ficha con el 4. Para la primera elección hay $\left(\begin{array}{cc}{5}\\{3}\end{array}\right)$ posibilidades (de las cinco casillas, elegimos las tres en las que estarán los unos), para la segunda, hay dos opciones (quedan dos casillas para elegir), para la última sólo queda una opción. Así calculada, la cantidad de números es:

$\left(\begin{array}{cc}{5}\\{3}\end{array}\right)$ $\times 2\times 1$ $= 20$

Planteemos, finalmente, una última variante de la pregunta: ¿Cuántos números de seis dígitos pueden armarse permutando las cifras 1, 1, 1, 2, 4, 4? Es decir, tenemos ahora seis fichas.

Si las seis fichas fueran diferentes tendríamos 6! = 720 resultados, pero, como antes, debemos preguntarnos cuántas veces aparece representado cada número. Por ejemplo, ¿cuántas elecciones generan el número 111.244? Para formar este número tenemos que elegir primero una permutación de las fichas A, B, C, después colocamos la ficha D, y finalmente elegimos una permutación de E, F.

Tenemos así que hay $3!\times 1\times 2!$ o también $3!\times 2!$, formas de obtener el número 111.244. El mismo razonamiento vale para cualquier otro número, por ejemplo, para formar 241.141 primero elegimos una permutación de A, B, C (y las colocamos, en orden, en las ubicaciones tres, cuatro y seis), luego ubicamos la ficha D en el primer lugar y, finalmente, elegimos una permutación de E, F (que colocamos, en orden, en los lugares segundo y cuarto).

Como cada número aparece repetido $3!\times 2!$ veces, la cantidad real de números que pueden formarse es:

$\frac {6!}{3!\times 2!} = 60$

Podemos también aplicar el razonamiento de las casillas vacías:

Para formar un número, elegimos primero los tres lugares para colocar las fichas que tienen el número 1 (como antes, las letras no juegan ningún papel). Para esta elección tenemos $\left(\begin{array}{cc}{6}\\{3}\end{array}\right)$ opciones (elegimos tres casillas de un total de 6). Luego elegimos las casillas donde irán las fichas con el número 4; tenemos $\left(\begin{array}{cc}{3}\\{2}\end{array}\right)$ opciones, ya que tenemos que elegir 2 casillas de las tres que quedan libres. Finalmente, hay una sola elección para la ficha con el 2. La cantidad total de números es, entonces:

$\left(\begin{array}{cc}{6}\\{3}\end{array}\right)$ $\times $ $\left(\begin{array}{cc}{3}\\{2}\end{array}\right)$ $\times 1 = 60$

Muchos libros en ocho estantes

¿De cuántas formas pueden distribuirse 72 libros diferentes en 8 estantes? (Cada estante es suficientemente largo como para contener todos los libros.) 

Una estrategia que puede aplicarse, cuando el problema involucra números grandes, es resolver primero un caso que sea más fácil de visualizar, con números pequeños, y luego aplicar la solución que obtengamos al caso que queríamos resolver inicialmente. Podemos preguntarnos, por ejemplo, qué sucede si, en lugar de 72 libros en 8 estantes, tuviéramos que distribuir 5 libros en 3 estantes. Para empezar, debemos analizar cómo podemos representar cada distribución de los libros; una manera de hacerlo es la siguiente:

Los rectángulos con números representan los libros, mientras que los rectángulos de color separan a los distintos estantes. La imagen representa, entonces, la distribución que tiene al libro 4 en el primer estante, a los libros 1, 2 y 3, en ese orden, en el segundo, y al libro 5 en el tercero.

Una distribución de libros puede, a su vez, ser modificada de dos formas; una es permutando los libros en alguno de los estantes:

Otra forma de modificar una distribución, por supuesto, es moviendo los libros de unos estantes a otros (en la imagen que se muestra a continuación, el primer estante ha quedado vacío):

Podemos pensar, entonces, que tenemos nueve fichas, cinco diferentes entre sí (los libros), y otras cuatro que son iguales entre sí (las fichas de color). Cada distribución de los libros se obtiene permutando las siete fichas centrales, ya que las dos de los extremos quedan fijas.

Tenemos que reordenar, entonces, siete fichas, de las cuales cinco (la cantidad de libros) son diferentes entre sí, y dos (una menos que los estantes) son iguales. Si aplicamos el mismo razonamiento del problema anterior (donde había fichas iguales entre sí, ya que tenían la misma cifra), deducimos que la cantidad de formas de distribuir los libros es:

$\frac{7!}{2!} = 2.520$

Otra forma de razonarlo es pensar que las 7 fichas será colocadas en sendas casillas en blanco. Primero elegimos dónde colocaremos las dos que son iguales, elección para la que tenemos $\left(\begin{array}{cc}{7}\\{2}\end{array}\right) $ opciones. Luego, tenemos cinco opciones para la ficha 5, cuatro opciones para la 4, y así sucesivamente. Así pensado el problema, la respuesta es:

$\left(\begin{array}{cc}{7}\\{2}\end{array}\right) \times 5!$

Para el caso de 72 libros en 8 estantes necesitamos 72 fichas diferentes (que representen los libros) y 7 fichas iguales entre sí (una menos que los estantes), con un total de 79 fichas. La respuesta es, entonces:

$\frac{79!}{7!}$

Seis pelotitas en tres cajas

¿De cuántas formas pueden distribuirse 6 pelotitas exactamente iguales en 3 cajas? (Cada caja es suficientemente grande como para contener todas las pelotitas.) 

El problema es muy similar al anterior, sólo que ahora las fichas que representan las pelotitas (y que antes representaban los libros) son todas iguales entre sí.

La imagen representa la distribución en la que hay una pelotita en la primera caja, tres pelotitas en la segunda, y dos en la tercera. Tenemos que reordenar, entonces, 8 fichas, de las cuales dos son iguales entre sí, y las otras seis también son iguales entre sí. Imaginemos que, para armar cada ordenamiento, vamos colocándolas en 8 casillas vacías.

Para colocar fichas, elegimos primero los dos lugares en los cuales vamos a colocar las barras. Tenemos $\left(\begin{array}{cc}{8}\\{2}\end{array}\right) $ formas de hacerlo, ya que elegimos dos lugares de un total de 8. No es necesario hacer más elecciones, porque, una vez que hemos colocado las barra, todos los demás lugares sólo pueden estar ocupados por las fichas que representan las pelotitas. La respuesta es, entonces:

$\left(\begin{array}{cc}{8}\\{2}\end{array}\right) = 28$

En lugar de los lugares para las barras, pueden elegirse también los 6 lugares para las pelotitas; pensado así, el resultado es:

$\left(\begin{array}{cc}{8}\\{6}\end{array}\right) = 28$

Para profesores del Nivel Medio: Sugerencias para el trabajo con los alumnos

1) En 1777 Wolfgang Amadeus Mozart compuso el Juego de Dados Musical para escribir valses con la ayuda de dos dados sin ser músico ni saber nada de composición. Este “juego” consiste en una tabla de 16 columnas, numeradas del I al XVI, y 11 filas, numeradas de 2 a 12. Cada casilla de la columna contiene un compás musical diferente.

Para componer un vals, el músico aficionado elige primero un compás de la columna I; para elegirlo tira dos dados, mira su suma, y se queda con la casilla que corresponde a ese número. Después, otra vez mediante la suma de dos dados, elige un compás de la columna II. Y así sigue hasta completar las dieciséis columnas. Esos compases, tocados uno detrás del otro, forman el vals. Mozart aseguraba que todos ellos sonaban armoniosamente.

Se puede investigar cuántos valses diferentes es posible componer de esta forma. Si suponemos que cada vals dura unos 30 segundos, se puede explorar cuántos años tardaríamos en ejecutarlos todos, uno tras otro.  

2) En 1961, el escritor francés Raymond Queneau, miembro del grupo de literatura experimental Oulipo, publicó el libro Cien mil millones de poemas, una versión literaria del juego musical de Mozart. En este caso, cada lector puede componer un soneto, que es una composición poética de 14 versos; el libro propone 10 opciones para el primer verso, otras 10 para el segundo, y así sucesivamente. Como antes, se puede explorar cuántos sonetos se pueden componer, y cuánto tiempo se demoraría en leerlos todos en voz alta.

3) En su famoso cuento La Biblioteca de Babel, Jorge Luis Borges describe una biblioteca que contiene, una vez cada uno, todos los libros posibles que responden a la siguiente descripción: cada libro tiene cuatrocientas diez páginas, cada página tiene cuarenta renglones, y cada renglón, ochenta letras. Las letras posibles son 25. ¿Cuántos libros contiene la biblioteca que describe Borges? 

4) En la imagen se ve la parte superior del Triángulo de Pascal, un “triángulo” de números que sigue infinitamente hacia abajo. En el extremo superior hay un uno, y todo el lado derecho, así como todo el lado izquierdo están también formados por unos. Cada uno de los demás números es la suma de los dos que están arriba de él.  

Los números que aparecen en el triángulo de Pascal son, en realidad, números combinatorios.

El Triángulo de Pascal tiene numerosas propiedades, que pueden explorarse. Por ejemplo, el “lado derecho” del triángulo está formado solamente por unos; la línea que le sigue paralelamente a ella está formada por los números 1, 2, 3, 4,…; la que le sigue, a su vez, está formada por los números triangulares (1, 3, 6, 10,…). Pueden buscarse otras sucesiones que también aparecen en el triángulo.

Otras propiedades se relacionan con sumas de filas o diagonales; por ejemplo, la suma de cada fila es siempre una potencia de 2. Otra propiedad dice que al sumar ciertas diagonales se va obteniendo la sucesión de Fibonacci (que se define como 1, 1, 2, 3, 5, 8,… donde cada uno es la suma de los dos anteriores). Se pueden explorar otras propiedades similares.