Permutaciones Y Combinaciones

Permutaciones y combinaciones

Contamos posibilidades

Comenzamos con un sencillo ejemplo. En España, los coches tienen una matrícula que consta de cuatro dígitos decimales, seguidos de tres letras sacadas de un alfabeto de 26. ¿Cuántas matrículas distintas puede llegar a haber?

Cuando se da una situación en la que cada uno de varios elementos puede tomar valores distintos, o diferentes tareas se pueden hacer de forma distinta, y todos ellos son independientes entre sí, la forma de calcular el número total de posibilidades es multiplicar el número de valores que puede tomar cada elemento, o el número total de formas en las que se puede realizar cada tarea. En nuestro caso, el primer dígito puede tomar uno de 10 valores; para cada uno de estos valores, el segundo dígito puede tomar uno de 10 valores, y así sucesivamente, hasta llegar a la tercera letra, que puede tomar, para cada uno de los casos que tengamos hasta ese momento, uno de 26 valores, para un total de

10 ×10 ×10 ×10 × 26 × 26 × 26 = 175.760.000 posibles matrículas.

Como se puede ver, ¡tenemos matrículas para rato!

Tomemos otro ejemplo sencillo. ¿Cuántos números hay cuya expresión decimal tiene exactamente 6 cifras? (Como es habitual, los ceros a la izquierda se eliminan)

En este caso, uno de los elementos tiene una limitación en su valor: la primera cifra no puede ser cero porque entonces ese cero a la izquierda se eliminaría y el número tendría a lo sumo 5 cifras. Por lo tanto, la primera cifra sólo puede tomar 9 posibles valores (1,2,...,9), para un total de

9 ×10 ×10 ×10 ×10 ×10 = 900.000 números.

Este problema se puede resolver también de otra forma alternativa, ya que el menor número que tiene

exactamente 6 cifras es el 100.000, y el mayor es 999.999, y todos los números entre ambos, y ninguno más, tiene exactamente 6 cifras, para un total de

999.999 −100.000 + 1 = 900.000 números.

Sumamos uno a la diferencia entre 999.999 y 100.000 porque ambos tienen 6 cifras y deben ser contados.

Continuamos con otro ejemplo. En el mus se reparten a cada jugador 4 cartas de una baraja de 40 cartas distintas. ¿De cuántas formas distintas me pueden repartir 4 cartas en el mus? ¿De cuántas formas me pueden tocar los 4 reyes?

Ahora, el resultado de la primera carta que se reparta afecta a las otras 3, porque ninguna de estas 3 puede ser igual a la primera, que ya está repartida. Por lo tanto, aunque la primera carta que me repartan es una de entre 40, la segunda carta deberá ser una de entre las 39 restantes, la tercera una de las 38 restantes, y la cuarta una de entre las 37 restantes, para un total de

40 × 39 × 38 × 37 = 2.193.360

posibles formas de repartir 4 cartas.

Para que me toquen los cuatro reyes, la primera carta debe ser uno de estos cuatro reyes, la segunda uno de los tres restantes, la tercera uno de los dos restantes, y la última el rey que quede, para un total de

4 × 3 × 2 ×1 = 24

posibles formas de repartir los 4 reyes.

¡De repente, tener cuatro reyes parece muy difícil!

¿Importa el orden?

Vamos a cambiar ligeramente el problema anterior: ¿Cuántas posibles manos existen en el mus? Es decir, como una vez que tengo mis cuatro cartas en la mano, la jugada no depende del orden en que me hayan llegado, ¿cuántos son los posibles grupos de 4 cartas que puedo llegar a tener jugando al mus? ¿Cuántas manos tienen 4 reyes?

La respuesta a la última pregunta es claramente que sólo 1 mano tiene 4 reyes, ¡cuando tengo los 4! No importa en este caso el orden en que hayan llegado. Me han podido llegar primero el de oros, luego el de copas, el de espadas y finalmente el de bastos (OCEB), pero me han podido llegar también en cualquier otro orden, (CBEO, BOEC,...). De hecho, como el primero ha podido ser cualquiera de los 4, luego cualquiera de los tres restantes, luego cualquiera de los 2 restantes, y finalmente el único que me falta, hay

4 × 3 × 2 ×1 = 24

posibles formas de ordenar los 4 reyes.

¡Claro, tantas formas como hay para que me repartan los 4 reyes si voy recibiendo las cartas de forma ordenada, de una en una! Vemos que el número total de manos con 4 reyes es el resultado de dividir el número de formas de repartir los 4 reyes, entre el número de formas de ordenar estos 4 reyes. En el caso de todas las posibles manos, sucede lo mismo; una vez que tengo 4 cartas en la mano, me han podido llegar en uno de 24 posibles órdenes, pero cada una de estas 24 formas de ordenarlas se corresponden con exactamente una mano, la formada por esas 4 cartas independientemente del orden en que me lleguen. Así, tenemos entonces que hay

40 × 39 × 38 × 37 = 91.390 posibles manos distintas en el mus.

4 × 3 × 2 ×1

A este número se le llama “combinaciones de 40 cartas tomadas de 4 en 4”, y es el número posible de

grupos de 4 cartas, sin importar el orden, que se pueden tomar de entre 40 distintas.

Formas de ordenar: permutaciones

En este ejemplo sencillo, nos ha bastado con ir contando, pero ¿hay alguna forma general de pensar y calcular que podamos aplicar en ejemplos más complicados? Aunque parezca que estamos “dando más vuelta”, vamos a pensar de otra forma distinta. ¿Cuántas posibles formas hay de ordenar las 40 cartas de la baraja? Siguiendo el mismo razonamiento de antes para ordenar los 4 reyes, vemos que hay

40 × 39 × 38 × 37 × 36 × 35 × ... × 5 × 4 × 3 × 2 ×1 formas de ordenar la baraja.

Si calculamos

...