En este post voy a presentar algunas de las estrategias que están en la base del problem solving en combinatoria. Se tratará de ilustrar con ejemplos cada una de esas estrategias.
Un problema elemental ilustrativo
¿Cuántos números de cuatro cifras distintas son pares?
Solución
Clasificamos en dos grupos: los que terminan en cero y los que no terminan en cero. Los que terminan en cero son tantos como 9(8)7; para los que no terminan en cero el argumento es el siguiente: elijo la última cifra de 4 formas; me quedan 8 dígitos para elegir la primera cifra (no es el cero ni la cifra final) y 8 para al segunda (no es la última ni la primera pero sí puede ser el cero)y para al tercera tengo 7 posibilidades. La respuesta es entonces 9(8)7+4(8)(8)7.
Comentario
La dificultad de este problema radica en que no podemos aplicar directamente el principio multiplicativo, dado que la cifra par del final y la exigencia de que sean distintas lo impide. De aquí que se tenga que dividir en casos: los que terminan en cero, los que terminan en dos, etc. (Una vez que fijamos la última cifra, ya se puede usar el principio multiplicativo, pero no antes.)
Ahora bien, más acá de los principios y las técnicas y las fórmulas, están las estrategias de base (clasificar o dividir en casos para este problema). Y para aplicar las estrategias de base no hay reglas. ¡Se tiene que ver cuál es la adecuada! Es por eso que para aprender combinatoria es necesario hacer muchos problemas (tantos como las ganas de triunfar del aspirante a campeón).
División en casos
La división en casos equivale a la partición del conjunto que se quiere contar. (Ésta es otra dificultad: ¡hay que aprender el lenguaje de conjuntos!) Un caso particular es el principio aditivo (o de la suma): se quieren contar los elementos de la unión de $A$ y $B$ y se sabe que son disjuntos (sin elementos en común); es casi obvio que tenemos que contar los de cada uno y sumar.
Conteo indirecto
Los números de tres cifras con al menos un cero se cuentan más fácil si pensamos que son todos menos los que no tienen ceros: $9\times 10\times 10-9\times 9\times 9$. Como regla, hay que buscar contar el complemento de un conjunto cuando el conjunto a contar contiene al menos (o a lo más) un elemento de un cierto tipo.
Inclusión-exclusión
También en el lenguaje de conjuntos es fácil de ver que si se desea contar los elementos de la unión de dos conjuntos $A,B$ la estrategia de base es dividir en casos: los elementos de $A$ y los elementos de $B$ que no están en $A$. Es decir, $n(A\cup B)=n(A)+n(B)-n(A\cap B)$
Elementos atados
A veces se desea saber de cuántas formas se pueden ordenar objetos con la restricción de que algunos de ellos deben estar juntos.
Por ejemplo, si los objetos son $m$ de un tipo y $n$ de otro y se desea que los $m$ del primer tipo permanezcan juntos.
El experimento imaginario que hace el truco de conteo es pensar que atamos o pegamos a los del primer tipo (para que permanezcan juntos) y después ordenamos los $n+1$ objetos resultantes de $(n+1)!$, para finalmente desatar los elementos del primer tipo y ordenarlos internamente de $m!$ formas.
Por el principio multiplicativo el número de formas de ordenar esos objetos bajo la restricción dada es $(n+1)!m!$.
Conteo excesivo
¿De cuántas formas se puede formar un collar con 5 cuentas de colores diferentes?
Solución: Si fuese una ordenación de los 5 colores serían $5!$. Pero el collar se puede voltear (dos formas) y se puede girar (5 formas) y permanece el mismo. Por tanto, $5!$ es un conteo excesivo. Por tanto, debemos dividir entre 10 para tomar en cuanta esas dos simetrías. La respuesta es entonces $5!/10$.
¿De cuántas formas se pueden sentar $n$ personas en una mesa redonda?
Solución: Si fuese una ordenación en fila (en una línea) la respuesta sería $n!$. Pero en la mesa redonda, las personas se pueden girar (la persona en la silla 1 se pasa a la 2, y la que estaba en la 2 se pasa a la 3, etc.) es decir, para cada orden hay $n$ equivalentes (el mismo orden relativo). Por tanto, la respuesta es $n/n=(n-1)!$.
¿De cuántas formas se pueden ordenar las letras de la palabra MAMA?
Solución: Si todas las letras fuesen diferentes la respuesta sería $4!$. Pero no lo son. Se tiene pues que corregir tomando en cuenta que la palabra tiene dos A y dos M. Así, la respuesta es $4!/(2!2!)$.
¿De cuántas formas se pueden ordenar $m+n$ objetos, donde $m$ son iguales entre sí y los restantes $n$ también son iguales entre sí?
Solución: Si todos los objetos fuesen diferentes la respuesta sería $(m+n)!$. Pero no lo son. Se tiene pues que corregir tomando en cuenta que hay objetos de dos tipos. Así, la respuesta es $(m+n)!/(m!n!)$.
Doble conteo
Esta estrategia de base consiste en contar el conjunto de objetos de dos formas. Como los dos conteos deben dar el mismo resultado se establece una ecuación. El mejor ejemplo es uno de los argumentos que establecen la fórmula para $C(n,k)$, el número de subconjuntos de tamaño $k$ tomados de $\{1,2,\ldots,n\}$.
¿De cuántas formas se puede elegir un subconjunto de tamaño $k$ de $\{1,2,\ldots,n\}$? (Equivalentemente ¿cuántos subconjuntos de tamaño $k$ tiene el conjunto $\{1,2,\ldots,n\}$?)
Solución (con doble conteo)
Consideremos el conjunto $\{1,2,3,4\}$ y sus subconjuntos de tamaño 3 para ejemplificar el argumento. Para este ejemplo ($n=4,k=3$), los subconjuntos se pueden enumerar y son 4: $\{1,2,3\}$, $\{1,2,4\}$, $\{1,3,4\}$, $\{2,3,4\}$. Trivial, pero nos sirve para ilustrar que con los subconjuntos se pueden generar todas las k-permutaciones de 1234.
123 124 134 234
132 142 143 243
213 214 314 324
231 241 341 342
312 412 413 423
321 421 431 432
En total, las 3-permutaciones de los elementos 1,2,3,4 son 24. Es decir, el número de subconjuntos de tamaño 3 de $\{1,2,3,4\}$ --el número de columnas--, multiplicado por las permutaciones de 3 objetos --el número de renglones.
En general, sea $C(n,k)$ el número de subconjuntos de tamaño $k$ de $\{1,2,\ldots,n\}$ y coloquemos cada uno de ellos encabezando una columna. Ahora enlistemos abajo de cada subconjunto sus posibles permutaciones que son $k!$.
De aquí que, por el principio multiplicativo, las k-permutaciones de los símbolos 123...n son tantas como $C(n,k)k!$. Por otro lado, ya sabemos que las k-permutaciones son tantas como $n!/(n-k)!$.
Hemos contado las k-permutaciones de $\{1,2,\ldots,n\}$ de dos formas y entonces $C(n,k)k!=n!/(n-k)!$. De ahí que $$C(n,k)=\frac{n!}{(n-k)!k!}$$.
Los saluda
jmd