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
Otro ejemplo de un problema
Otro ejemplo de un problema en el que se puede utilizar este tipo de argumentos:
Problema. En Japón, para escribir se utilizan símbolos para representar sílabas. Por ejemplo, un símbolo significa "tsu", otro significa "na", otro significa "mi", y así sucesivamente. Utilizando los tres símbolos mencionados anteriormente ("tsu", "na" y "mi"), sin repetir símbolos, ¿cuántas palabras de tres símbolos se pueden formar en total?
Solución. Una palabra consiste en una lista ordenada de símbolos (por ejemplo, la palabra "uno" está formada por la lista de los símbolos:
La pregunta en este problema se puede traducir como: "¿de cuántas maneras se puede ordenar la lista de los 3 símbolos: "tsu", "na", "mi"?". Teniendo en mente esa pregunta, vemos que es similar a la que propone al inicio del post, así que utilizando los mismos argumentos podemos afirmar que existen 3 x 2 x 1 = 6 listas, es decir, podemos formar 6 palabras usando "tsu", "na" y "mi".
Sólo para ilustrar mejor la idea, vamos a formar las palabras. Primero las que empiecen con "tsu":
1. "tsu" - "na" "mi" = tsunami,
2. "tsu" - "mi" "na" = tsumina.
Luego las que empiecen con "na":
3. "na" - "tsu" "mi" = natsumi,
4. "na" - "mi" "tsu" = namitsu.
Finalmente las que empiecen con "mi":
5. "mi" - "tsu" "na" = mitsuna,
6. "mi" - "na" "tsu" = minatsu.
Formar las listas no es muy conveniente cuando hay muchos elementos qué ordenar, pues uno corre el riesgo de olvidar algún elemento además de consumir demasiado tiempo (la experiencia me lo dice T_T, buu T_T). Lo importante en este tipo de problemas es comprender el razonamiento que se lleva para llegar a una solución correcta, y desarrollar razonamientos similares para resolver más problemas de conteo.
Excelente ejemplo Zzq.
Excelente ejemplo Zzq. Gracias por la aportación --y el breviario cultural. Y posiblemente alguna vez haya oportunidad de que nos cuentes tu experiencia en problemas de combinatoria. Te preguntaría si, en principio, podrías visitarnos en Cd. Victoria después del 28 de agosto para que te hicieras cargo de un entrenamiento de fin de semana. Consulta tu agenda y me avisas...
Te saluda
Sería un gusto enorme poder
Sería un gusto enorme poder ir allá para esa fecha :D, pero como ya el lunes entro a la universidad sería cuestión de ver qué tan pesada es y todo eso, pero por mí asistiría con muchas ganas :D. Gracias por la invitación :D, de verdad :D. Pero mientras exista esa barrera geográfica (o física) y no pueda estar allá, andaré dándome vueltas por aquí y viendo más problemas y discutir soluciones y así, a ver si a alguien le puede servir :D.
Gracias nuevamente, y saludos :D.
OK. De cualquier manera tu
OK. De cualquier manera tu colaboración a distancia es muy valiosa. (El primer semestre en la universidad es crítico, cualquier descuido y ya te atrasaste en alguna materia... de cualquier manera, pues si ves que hay oportunidad, la invitación está abierta.)
Te saluda