Argumentos básicos de conteo

Con este post estoy inaugurando una sucesión que podría llegar hasta 20. La idea es la misma que la que usé con los GBC-teoremas, es decir, formular una serie de hechos básicos sobre el tema. En los teoremas de geometría básica del círculo me vi limitado por el formato de teorema y no añadí comentarios u otras ayudas didácticas. Es por eso que ahora, para los hechos básicos de combinatoria, elijo la entrada de blog para difundir es conocimiento básico, dada la flexibilidad de su formato.

El lector debería dar prioridad a los esquemas argumentativos expuestos y comentados, es decir, a un modo de razonar que es específico de los problemas combinatorios. Al principio podría imitarlos, pero de lo que se trata es de entenderlos con miras a la solución de problemas de concurso.

Estos posts --que voy a llamar ABC_Combinatorios-- inician con

Argumentos básicos de conteo 1 (Permutaciones)

¿ De cuántas formas se pueden ordenar en una lista $ n $ objetos etiquetados $1,2,\ldots,n$?

Solución

Encabezando la lista se puede poner cualquiera de los $ n $ objetos. Para el segundo lugar nos quedan $n-1$ objetos y, de nuevo, para el segundo lugar podemos elegir cualquiera de los $n-1$ que quedan. Continuando de esta manera, para el último lugar solamente queda uno de los objetos, así que hay una sola posibilidad. 

La respuesta es entonces, de acuerdo al principio multiplicativo, $n(n-1)(n-2)\ldots(2)(1)=n!$ formas de enlistar $ n $ objetos diferentes. (En otras palabras, hay $n!$ listas posibles.)

Digresiones, comentarios, otros argumentos...

En este caso, el principio multiplicativo se aplica con una variante: en cada elección hay un conjunto remanente cuyo tamaño depende de las elecciones anteriores. Es decir, la diferencia con el principio multiplicativo original es que en éste los conjuntos están fijos desde el inicio del conteo; aquí, en cambio, cada elección define un nuevo conjunto (aunque como solamente nos interesa su tamaño se puede pensar que en cada elección la cardinalidad del conjunto disminuye en una unidad).

Solución alternativa (usando recursión)

Sea $P_n$ el número de listas posibles para $ n $ elementos. De esta manera, para cada una de las $ n $ posibilidades de encabezar la lista, hay $P_{n-1}$ de terminarla. Así que $P_n=nP_{n-1}.$ Puesto que para $n=2$ hay solamente dos formas $(12,21)$ entonces $P_3=3P_2=3(2)$, etc. El argumento se formaliza demostrando por inducción que hay $n!$ formas.

Este mismo argumento visto como una clasificación de las listas de $ n $ elementos es así: formamos la clase del 1, es decir, la clase de las listas que tienen el 1 en primer lugar; formamos la clase del 2, etc. Al final hemos formado $ n $ clases de listas: la del 1, la del 2,..., hasta llegar a la del $ n $. Pero cada una de esas clases tiene $P_{n-1}$ elementos (argumente el lector por qué). Es decir, hay $nP_{n-1}$ listas posibles de los $ n $ objetos.

Nota sobre los experimentos imaginarios que están en la base de los argumentos combinatorios

Modelo básico de elección

En la solución, el modelo que está en la base del argumento es un modelo de elección: el argumentador debe imaginar que tiene que decidir cuál elemento poner en primer lugar, cuál en segundo lugar, etc. Para el primero puede poner cualquiera de los n, por lo tanto tiene n elecciones posibles; para el segundo, tiene n-1 elecciones, etc. Como las decisiones son consecutivas, se aplica el principio multiplicativo.

Modelo de urna

Una forma de evitar la elección personal (digo, porque alguien podría decir "con tantas opciones mi cerebro no puede procesar") es el modelo de urna: en una urna como el de la foto (tomada de Google), los objetos están representados con bolas numeradas del mismo tamaño, se le da vuelta a la manivela para asegurar que están bien "revueltas" (esto quiere decir que no hay razón para pensar que alguna de las bolas tiene más chances de salir que las demás) y finalmente se abre un orificio por donde sale una de las bolas.

El mecanismo de la urna asegura la aleatoriedad de la elección --es un modelo básico en argumentos probabilísticos. Digamos, finalmente, que el argumentador no tiene que realizar el proceso de hacer salir una bola de la urna --como tampoco tiene que elegir en el modelo de elección--, basta con imaginar que, en principio, lo puede hacer; y que ese mecanismo asegura que puede salir cualquiera de las bolas que estan en la urna.

Otra cosa: históricamente, la urna era un jarro u otro recipiente con la boca estrecha de tal manera que solamente cabía una mano, y no se podía ver hacia adentro; alguien metía la mano y sacaba una bola... y todo esto de manera imaginaria --lo que se tiene que asegurar con el modelo de urna es que cada una de las bolas en su interior tienen las mismas chances de ser extraídas.

Modelo de clasificación (con elemento señalado)

Retirar el elemento señalado

En la solución alternativa, el modelo es de clasificación. En este modelo uno se imagina que ya están todas las listas generadas y procede a clasificarlas según el primer elemento. Entonces se procede a contar cuantas clases hay y cuántos elementos tiene cada clase. De nuevo, el novicio debe entender que no tiene que hacer el experimento realmente, sino que solamente lo tienen que imaginar. El modelo de clasificación se complementa con un argumento recursivo. Por ejemplo, en la clase del 1 en primer lugar, imaginemos que quitamos el 1 de esas listas; ¿qué queda? Lo que queda son las listas de $n-1$ elementos y, por hipótesis, son $P_{n-1}$ en número.

Agregar un elemento adicional

El modelo de clasificación puede usarse de esta otra manera: a cada una de las listas se le agrega el elemento $n+1.$ Nos interesa el efecto que tiene ese añadido en el número de listas. Dada una de las listas, una de entre las $n!$, el elemento $n+1$ lo puedo colocar en cualquiera de los $n+1$ lugares posibles (al principio,en segundo lugar --entre el primero y el segundo antes de añadirlo--, ..., en último lugar o sea en el lugar n+1). Es decir, cada lista de $ n $ objetos da lugar a $n+1$ listas de $n+1$ objetos y, en resumen, el número de listas será $(n+1)n!$ (o, si todavía no supieramos cuántas corresponden a $ n $, el número de listas de $n+1$ objetos es $(n+1)P_n$)

Los saluda

jmd