Problemas clásicos

En el arte de contar existen los "problemas clásicos", es decir, preguntas que aparecen frecuentemente a la hora de contar cosas que, en principio, podrían no tener nada que ver con estos "problemas clásicos".

En esta sección mezclo ejemplos con números concretos con fórmulas para las situaciones más generales, donde la cantidad de objetos (remeras, libros, etc.) son una variable "$n$" o "$r$". No es tan importante entender "la fórmula" en sí, sino más bien entender cómo llegar a ella en cada caso particular.

Regla del producto

La primera técnica es la que podríamos llamar la regla del producto en la combinatoria. Responde a la pregunta de "cómo se pueden combinar" las posibilidades de tomar muchas elecciones independientemente. El ejemplo perfecto para esta idea es el siguiente:

También podemos visualizar la regla del producto usando un árbol de posibilidades. En hecho de que las elecciones sean independientes se entiende viendo que en el árbol, todas las ramas están "balanceadas", es decir, de cada ramificación salen exactamente la misma cantidad de ramitas. Esto también explica por qué la respuesta termina siendo un producto.

Una situación muy frecuente en la que podemos aplicar esta regla es en los problemas que nos piden hallar la cantidad de números cuyos dígitos satisfacen cierta relación. En estos problemas, podemos imaginar que nosotros construimos el número eligiendo cada dígito por separado, y luego ver cuántas de esas elecciones satisfacen las relaciones que nos pide el problema.

Una pregunta necesaria: ¿Cuándo sirve aplicar la regla del producto? Inlcuso, una pregunta aún más útil es saber cuándo no se puede aplicar la regla del producto. Los siguientes escenarios pueden servir de guía general:

• Cuando hay que combinar cosas que son independientes entre sí: el ejemplo típico: combinar remeras y pantalones.

• No se aplica si no todas las combinaciones son válidas, por ejemplo, si el color de la remera depende del del pantalón.

• No se aplica para juntar cuentas de casos distintos, en ese caso se suman las posibilidades.

Justamente, la dificultad de los problemas de contar posibilidades aparece cuando tenemos que contar combinaciones de elecciones que no son independientes entre sí. En estos casos, tendremos que arreglárnoslas para contar solamente las combinaciones "válidas". Veremos varios casos donde ocurre esto en las siguientes secciones:

Permutaciones y variaciones

Supongamos que ahora queremos saber cuántas formas tenemos de elegir una de nuestras $5$ remeras para cada uno de los $5$ días de la semana: eso sí, no queremos repetir (por higiene).

Las variaciones de un conjunto de elementos son las formas de formar una lista ordenada con algunos de sus elementos, sin repetir. Si se usan todos los elementos, tenemos una permutación. La dificultad en contar variaciones/permutaciones está en que ahora las elecciones no son independientes, sino que cada una depende de la anterior; por ejemplo, si el lunes elegí la remera verde, entonces el jueves no puedo volver a elegir la remera verde.

En general, si tenemos $n$ objetos y queremos formar una lista ordenada de $r$ de ellos, sin repetir, la cantidad de formas de hacer esto es

$$n\times (n - 1)\times (n - 2)\times \cdots (n - r + 2)\times (n - r + 1) = nVr$$

Para no tener que escribir toda la multiplicación, se puede usar el símbolo de la derecha, que se lee $n$ permutados de a $r$.

Por ejemplo, la respuesta del primer ejemplo puede escribirse como

$$10V5 = 30.420$$

Para que esta cuenta tenga sentido, debemos tener $n \ge r$ (por ejemplo, si sólo tengo $4$ remeras, ¿es posible no repetir remera dos días de semana distintos?). Pero, si $n = r$, tenemos otra interpretación de qué es lo que estamos contando. La multiplicación quedaría:

$$n \times (n - 1) \times (n - 2) \times \cdots \times 1 = n!$$

Y en este caso, la multiplicación de tales números se escribe como $n!$, y se lee "$n$ factorial". El factorial de un número cuenta la cantidad de permutaciones (es decir, reordenamientos) de un conjunto con esa cantidad de elementos. La siguiente imagen muestra los valores y los significados de los primeros números factoriales:

[IMAGEN]

Otra ventaja de inventarle un nombre a $n!$ es que ahora podemos escribir la respuesta al problema de las varianciones de la siguiente forma:

$$nVr = \frac{n!}{(n - r)!}$$

Para entender por qué esto es cierto, tenemos que escribir cada factorial como la multiplicación correspondiente y cancelar los términos iguales en el numerador y el denominador.

De ahora en más, usaremos la expresión en el lado derecho de la igualdad, pues es lo más frecuente. Resulta fácil alarmarse al ver que la respuesta a un problema de contar viene dada expresada como una fracción, sin embargo, al escribir el desarrollo de los factoriales resulta claro por qué este temor es infundado.

Veamos otra situación, en apariencia bastante distinta, donde también tenemos que contar unas permutaciones.

Combinaciones

Supongamos ahora que vamos a un viaje de $3$ días y tenemos que elegir qué remeras llevarnos. Sabemos cuántas formas hay de planificar cuál usamos para día, pero eso ya no nos importa: queremos saber cuántas formas hay de elegir $3$, no importa cuál usemos qué día.

Las combinaciones de un conjunto de elementos son las formas de elegir algunos de sus elementos, sin importar el orden en que se elijan. La nueva dificultad para contar combinaciones es lograr no contar por duplicado dos elecciones de los mismos elementos en otro orden. Y esto no es menor: uno de los problemas capitales de la combinatoria consiste en cómo evitar contar cosas repetidas. Por suerte, hay una forma muy elegante de evitarlo en este caso.

En general, si tenemos $n$ objetos y queremos seleccionar $r$ de ellos, no importa en cuál orden, tenemos:

$$\frac{n\times (n-1)\times (n-2)\times \cdots\times (n-r+1)}{r\times (r-1)\times (r-2)\times \cdots\times 1} = \frac{n!}{(n-r!) r!} = nCr = \binom{n}{r}$$

Las dos expresiones de la derecha son dos abreviaciones distintas de la cantidad de combinaciones de r números de un total de n, y se leen "$n$ tomados de a $r$". (La primera, $nCr$ es la que aparece en las calculadoras científicas, pero la segunda $\binom{n}{r}$, es por lejos la más común.)

En este caso, resulta mucho más preocupante que la respuesta termine siendo un número entero o no (para nuestra tranquilidad, siempre lo es, así que Pepito no va a terminar con una cantidad racional de amigos), y el hecho de que siempre lo sea es una curiosidad aritmética bastante menos obvia que en el caso anterior. Por ahora, puede tranquilizar ver algunos ejemplos de números combinatorios en acción:

[IMAGEN]

Los números combinatorios son muy especiales (no por nada reciben un nombre propio) y aparecen frecuentemente en combinatoria y en otras áreas, como la teoría de números.

Para calentar los motores

Antes de pasar a la lista de problemas, dejo unos problemas seleccionados con sus soluciones para ver cómo los argumentos se vuelven más intrincados y astutos. Por supuesto, antes de lanzarse a la solución, recomiendo pensar al menos 15 minutos cada problema.

Lista de problemas