Combinatoria I

Introducción a la combinatoria

La combinatoria es la parte de la matemática que nos enseña a contar de cuántas formas se puede hacer algo. Por ejemplo, si Ana y Beto van al cine y compraron dos asientos consecutivos, ¿de cuántas formas se pueden sentar? La respuesta es $2$ ya que se pueden sentar Ana - Beto ó Beto - Ana. Nuevamente, este ejemplo es fácil, pero vamos a ver ideas que sirvan para contar cuántas formas tenemos de hacer algo, cuando las posibilidades son muchas e ir probando una por una sería muy largo.

1) Juan almuerza en un bar que ofrece un menú con:

• Bebida: agua ó gaseosa 
• Entrada: empanada ó ensalada
• Plato principal: milanesa, carne ó pollo
• Postre: flan, panqueque, ensalada de frutas ó helado 

¿De cuántas formas distintas puede pedir su menú?

Solución: Supongamos que elegimos agua, empanada y milanesa, ¿cuántas posibilidades tengo para elegir el postre? $4$, ya que puedo elegir cualquiera. Luego, si elegimos agua, empanada y carne, también voy a tener $4$ posibilidades. Lo mismo para agua empanada y pollo. Es decir que elegiendo agua y empanada tengo $4+4+4=12$ posibilidades. Ahora, si cambio la empanada por la ensalada, voy a volver a tener otras $12$ posibilidades. Por lo tanto, elegiendo siempre agua voy a tener $24$ posibilidades. Pensando de manera análoga, si cambio el agua por la gaseosa voy a tener otras $24$ posibilidades. Finalmente voy a tener $24+24=48$ posibilidades. Esta forma de pensarlo, en distintas  "ramas", se llama "diagrama de árbol".

Miremos que $48 = 2 \times 2 \times 3 \times 4$. ¿Será casualidad? La realidad es que no, no es casualidad. Pensemos que en la mesa de Juan hay $4$ lugares, destinados uno para poner la bebida, otro para poner la entrada, otro para poner el plato principal y otro para poner el postre. Para el lugar de la bebida tenemos $2$ posibilidades, para el lugar de la entrada tenemos $2$ posibilidades, para el lugar del plato principal tenemos $3$ posibilidades y para el lugar del postre tenemos $4$ posibilidades. Ahora, podemos cambiar un sólo lugar y dejar todos iguales los demás y tenemos distintas posibilidades, por lo tanto por cada elección que yo haga de un lugar voy a tener todas las de los demás lugares. Es por eso que multiplicamos los números. Esta idea, que la vamos a utilizar muchísimo, es la de "llenar cajitas".

2) ¿Cuántos números de dos cifras existen?

Solución $1$: podemos pensar que el número más grande de dos cifras es el $99$. Escribamos los números hasta ese:

$1-2-3- \cdots - 8-9-10-11- \cdots -98-99$

En esta lista tenemos $99$ números, pero a esa cantidad tenemos que sacarle los que no nos sirven, o sea los que no tienen dos cifras... ¿y esos cuántos son? Son $9$, ya que el $10$ es el primer número de dos cifras. Por lo tanto existen $99-9=90$ números de dos cifras.

Solución $2$: utilicemos la idea de llenar cajitas. Lo que nosotros queremos hacer es formar números de dos cifras, por lo tanto vamos a tener $2$ cajitas. Y en cada cajita vamos a tener que poner alguno de los dígitos (0, 1, 2, ..., 9) para formar nuestro número de $2$ cifras. Por ejemplo si en la primera cajita ponemos el $4$ y en la segunda cajita ponemos el $0$, formamos el número $40$.

$\underbrace{\square}_{9 \; \mbox{posib}} \underbrace{\square}_{10 \; \mbox{posib}}$

En la primera cajita hay $9$ posibilidades, ya que un número de dos cifras no puede empezar con cero. En la segunda hay $10$ posibilidades, porque podemos poner cualquier dígito. Finalmente va a haber $9 \times 10 = 90$ números distintos de dos cifras. (Tenemos que multiplicar esos números porque podríamos construir el árbol de este problema y estaríamos en el mismo caso que antes).

3) ¿Cuántos números de dos cifras iguales existen?

Solución: Los números de dos cifras iguales son nueve: $11$, $22$, $33$, $44$, $55$, $66$, $77$, $88$ y $99$.

4) ¿Cuántos números de dos cifras distintas existen?

Solución: pensemos que un número de dos cifras, o bien tiene sus cifras iguales, o bien tiene sus cifras distintas. Luego, como ya sabemos que en total existen $90$ números de dos cifras, y que $9$ de ellos tienen sus cifras iguales, los que tienen sus cifras distintas deben ser $90-9=81$ números.

5) ¿Cuántos números de tres cifras existen?

Solución $1$: podemos pensar que el número más grande de tres cifras es el $999$. Escribamos los números hasta ese:

$1-2-3- \cdots -98-99-100-101- \cdots -998-999$

En esta lista tenemos $999$ números, pero a esa cantidad tenemos que sacarle los que no nos sirven, o sea los que no tienen tres cifras... ¿y esos cuántos son? Son $99$, ya que el $100$ es el primer número de tres cifras. Por lo tanto existen $999-99=900$ números de tres cifras.

Solución $2$: utilicemos la idea de llenar cajitas. Lo que nosotros queremos hacer es formar números de tres cifras, por lo tanto vamos a tener $3$ cajitas. Y en cada cajita vamos a tener que poner alguno de los dígitos (0, 1, 2, ..., 9) para formar nuestro número de $3$ cifras. Por ejemplo si en la primera cajita ponemos el $4$, en la segunda cajita ponemos el $0$ y en la tercera cajita ponemos el 2, formamos el número $402$.

$\underbrace{\square}_{9 \; \mbox{posib}} \underbrace{\square}_{10 \; \mbox{posib}} \underbrace{\square}_{10 \; \mbox{posib}}$

En la primera cajita hay $9$ posibilidades, ya que un número de tres cifras no puede empezar con cero. En la segunda y en la tercera hay $10$ posibilidades, porque podemos poner cualquier dígito. Finalmente va a haber $9 \times 10 \times 10 = 900$ números distintos de tres cifras. (Tenemos que multiplicar esos números porque podríamos construir el árbol de este problema y estaríamos en el mismo caso que antes).

6) ¿Cuántos números de tres cifras iguales existen?

Solución: Los números de tres cifras iguales son nueve: $111$, $222$, $333$, $444$, $555$, $666$, $777$, $888$ y $999$.

7) ¿Cuántos números de tres cifras distintas existen?

Solución: Notemos que ahora no es tan simple contarlos como en el caso de dos cifras. Vamos a 

intentar crear todos los números de tres cifras distintas.

¿Cómo podemos crearlos? Bueno, sin lugar a dudas tenemos que llenar tres espacios. 

Por lo tanto los números de tres cifras distintas serán números de esta forma: $\square \; \square \; \square$

Notemos que en el primer cuadradito no se puede poner un cero, ya que sino pasaría a ser de dos cifras. Entonces en el primer cuadradito tendremos $9$ posibilidades para llenarlo (las cifras del $1$ al $9$). En el segundo cuadradito tendremos también $9$, ya que no podemos usar el número que pusimos en el primer lugar pero podemos usar el cero. Finalmente en el tercer cuadradito tendremos $8$ posibilidades, las diez cifras menos las dos que ya usamos. Es decir:

$\underbrace{\square}_{9 \; \mbox{posib}} \underbrace{\square}_{9 \; \mbox{posib}} \underbrace{\square}_{8 \; \mbox{posib}}$

Por lo tanto tendremos $9\cdot9\cdot8=648$ números de tres cifras distintas.