Curso de Combinatoria III: Permutaciones con repetición

Suponed que pretendemos hacer un sorteo de esos que se realizaban antes en los descansos de los espectáculos circenses. Vendemos entre el público las consabidas tiras de papel con diferentes cifras y una vez agotadas, nos disponemos a celebrar el sorteo. Contamos para ello con tres ruedas que haremos girar independientemente. En cada rueda se encuentran dibujados los números del 0 al 9. Nos asalta la duda de si en los boletos vendidos existirán más cifras que la cantidad de posibles números ganadores. ¿Cuántos posibles resultados podemos obtener? Esto parece muy fácil: Teniendo en cuenta que cada rueda tiene 10 posibilidades y que tenemos tres ruedas independientes, la cantidad buscada es 10 x 10 x 10 = 1000. Fijaos en la diferencia de esta situación con la de la anterior lección cuando nos referíamos a los atletas y las medallas. Ahora también tenemos que elegir tres elementos, (uno de cada una de las ruedas) y también es importante el orden de salida, ya que no es lo mismo el orden 1, 2, 3 (formando el 123) que la ordenación 2, 3, 1 (formando el 231). Pero sin embargo en esta tesitura se pueden repetir los elementos. Trasladándolo a la prueba de atletismo sería como si un mismo atleta pudiese llevarse el oro, la plata y el bronce. Se entenderá entonces perfectamente el porqué de la denominación de “permutaciones con repetición”. El término permutaciones es porque hay que tener en cuenta el orden de aparición y el término repetición es debido a que podemos repetir varias veces el mismo elemento.

            Obsérvese también que a diferencia de lo que ocurría en las permutaciones “a secas”, en las que obviamente el número de objetos a escoger no podía exceder del número total de ellos, al existir ahora la posibilidad de repetir elección, sí que podría darse el caso de tener que elegir una cantidad de elementos mayor que el número de los que hay en el catálogo. Por ejemplo, podemos formar números de 20 cifras con los dígitos del 0 al 9 ¿verdad? Es claro que esos números tendrán con toda seguridad dígitos repetidos. Ahora bien, ¿cuántos números de esos podremos formar? Deberías ver muy claro que la cantidad es 10 multiplicado por si mismo unas 20 veces, o dicho de otro modo, “10 elevado a la potencia 20.” Vamos, ¡un montonazo!

            En cuanto a la fórmula general, si tenemos una colección de n elementos y queremos elegir m de ellos, influyendo el orden y pudiendo elegirlos repetidos, estamos ante lo que se denominan Permutaciones con repetición de n elementos, tomados de m en m. su fórmula general es:

P_R (n,m) = n^m

            Vayamos ahora con un ejemplo más cotidiano y calculemos cuántas quinielas sencillas hay que cubrir para tener la seguridad de obtener los 15 aciertos. Tenemos 15 casillas y en cada una de ellas podemos poner un 1, una x ó un 2. En total hay tres opciones por casilla. Así pues una apuesta no es más que una permutación con repetición de 3 elementos tomados de 15 en 15. En consecuencia P_R(3,15) = 3¹⁵, son el número de apuestas sencillas entre las cuales se encuentra el único boleto con la combinación correcta. Esto me hace recordar una vieja discusión que tuve cierto día con mi madre. Ella argumentaba que en una quiniela era igual de difícil acertar todas las casillas que no acertar ni una sola. Después de las anteriores reflexiones estamos en condiciones de demostrar que eso no es así. Resulta evidente que la serie correcta en una quiniela es única. Sin embargo, ¿cuántas opciones diferentes tenemos de no acertar ni una? Veamos: En cada casilla hay una opción correcta y dos erróneas, luego se trata de escoger en cada caso una de esas dos opciones incorrectas. Como lo más probable es que no se dé el caso de que las opciones incorrectas en cada uno de los partidos siempre sean las mismas; es decir, siempre x, 2 ó 1, x o cualquier otro par, lo mejor será que las denominemos como: 1ª opción incorrecta y 2ª opción incorrecta. Estamos de nuevo ante permutaciones con repetición de 2 elementos (las opciones erróneas) tomados de 15 en 15. Así pues hay 2¹⁵ formas de cubrir una quiniela asegurando que no damos una en el clavo; mientras que sólo tenemos una posibilidad de acertarlo todo. Sorprendente ¿verdad? O quizá no tanto…

Curso de Combinatoria II: Permutaciones

Una vez que han quedado claros los principios de la suma y el producto, vamos a dar un paso más hacia nuestro objetivo de obtener un razonable conocimiento del tema de la Combinatoria.  Recordad que esto no es más que contar de manera ordenada y que lo fundamental es saber cuándo y dónde colocar  las multiplicaciones y las sumas.

           

            Imaginad que se va a celebrar una carrera en la que se han apuntado diez atletas, con dorsales del uno al diez. Es decir: Atletas = {1,2,3,4,5,6,7,8,9,10}. Nos gustaría saber de cuántas formas posibles puede estar formado el pódium final para la entrega de medallas. No sólo se trata de elegir entre los diez atletas aquellos tres que configurarán el pódium, sino que también es importante el orden de elección; pues como comprenderéis no es lo mismo quedar primero que quedar segundo o tercero. Vamos a intentar contar las diferentes configuraciones de las medallas. Suponed que en un acto de corrupción sin precedentes nos erigimos en dueños del destino de nuestros deportistas y somos capaces de determinar “a dedo” los tres primeros puestos de la carrera. ¿Cuántas formas distintas tenemos de hacerlo? Veamos:

             

         Para elegir al ganador tenemos diez posibilidades. Sin embargo, una vez elegido el ganador, la elección del segundo tiene una posibilidad menos; es decir, nueve. Finalmente, la elección del tercero sólo cuenta con ocho posibilidades. Es evidente que no puede haber diez opciones para cada puesto ya que no es factible que un mismo atleta sea primero, segundo y tercero simultáneamente. Por otro lado, aplicando el principio del producto o “atuendo” (como lo hemos llamado en la lección anterior), cada una de las diez posibilidades de elección del ganador se puede “combinar” con  todas las posibles elecciones del segundo; y cada una de estas combinaciones se puede combinar con todas las posibilidades para el tercero. En total tenemos como opciones totales para las medallas,  10 x 9 x 8 =720. ¿Son muchas eh?. Quizá alguno de vosotros pueda pensar que el hecho de elegir primero el que se llevará el oro, luego el que recibirá la plata y finalmente el que obtendrá el bronce hace que las cuentas no estén bien realizadas. Si eso es lo que sospecháis podríamos hacerlo de la siguiente forma: Suponed que sobre la mesa hay tres cajas cerradas. Una tiene la medalla de oro, otra tiene la de plata y la última la de bronce. No hay forma de saber qué medalla hay en cada una de las cajas. Entonces se elije un atleta que se llevará la medalla de la primera caja (10 posibilidades); luego otro que se llevará la de la segunda caja (9 posibilidades) y a continuación el tercero para la última de las cajas (8 posibilidades). Ahí tenéis de nuevo 10 x 9 x 8 = 720.

Este tipo de situaciones también se dan en casos como éstos: formar una bandera bicolor con los siete colores del arco iris tiene 7 x 6 = 42 posibilidades. Otorgar 4 juguetes diferentes entre 8 niños se puede hacer de 8 x 7 x 6 x 5 = 1680 formas. Observad que la característica común de los casos descritos es la necesidad de elegir una cantidad m de elementos, de entre un conjunto total de n; considerando también el orden de disposición de los m elementos elegidos. En el caso de los atletas m = 3, n = 10. Para la bandera m = 2, n = 7 y para los juguetes m = 4, n = 8. Obviamente el número m ha de ser como mucho igual al número n. Volviendo al ejemplo inicial, ahora debería ser fácil entender que si queremos dar todas las clasificaciones completas posibles tras la finalización de la carrera tendríamos que hacer el cálculo siguiente: 10 x 9 x 8 x … x 2 x 1. Esto es multiplicar todos los números enteros desde el 1 hasta el 10. Esta operación se conoce como el factorial de 10 y se representa como 10! Es posible que el signo de admiración sea debido a que el resultado de la operación es más grande de lo que en un principio podría parecer. 10! = 3628800.

     En consecuencia y para terminar esta segunda lección. Si tenemos una colección de n elementos distintos y queremos escoger m de ellos para una cuestión en la que además interviene el orden entre los escogidos, estamos ante lo que se denominan “permutaciones de n elementos tomados de m en m”. Dicho número está representado como P(n,m). La fórmula del cálculo ya vista para los ejemplos considerados tiene la siguiente expresión general:

P(n,m) = n x (n-1) x (n-2) x … x (n-m+1)

Observad que se verifica para todos los casos descritos. Además podéis comprobar que en el caso en el que tengamos que escogerlos todos; es decir  n = m, la fórmula es:

P(n,n) = n x (n-1) x (n-2) x … x 1 = n!

A ver si lo habéis entendido. Volvamos de nuevo al ejemplo de los atletas. ¿Podríais decirme cuantas posibles asignaciones de medallas hay para cada terna de atletas que configuren un pódium?

Curso de Combinatoria I: Principio de la suma y del producto

No sé si será porque soy matemático, pero en algunas de las largas sobremesas que suceden a una copiosa comida familiar de esas que se producen periódicamente, ya sea por Navidad, Año Nuevo o en eventos sacramentales como bautizos, comuniones y bodas, terminan formulándose preguntas como las siguientes: ¿Es igual de difícil acertar todo en la quiniela que no acertar nada?, ¿Cuántos boletos sencillos hay que rellenar para asegurarse de que tenemos seis aciertos en la primitiva? ¿Qué es más difícil de conseguir en el sorteo de los Euromillones: dos aciertos en números y uno en estrellas o viceversa? Todas estas cuestiones se resuelven mediante la rama de las matemáticas denominada Combinatoria. Podríamos decir que la Combinatoria proporciona técnicas para poder contar de manera organizada en situaciones especiales. Saber cuántas personas hay en un determinado espacio es bastante sencillo, siempre y cuando todos se estén quietecitos y no demasiado desperdigados. Ahora bien, determinar cuántos grupos de tres personas distintas podemos formar con un centenar, ya resulta bastante más complejo ¿verdad? Durante varias entradas del blog trataré de explicar de manera sencilla y medianamente inteligible las principales técnicas y fórmulas que responden a algunas de las preguntas del tipo enunciado anteriormente.

En primer lugar veremos que lo fundamental en todo esto es saber sumar y multiplicar. A partir de ahí se deduce todo lo demás. Comenzaremos con los denominados “principio de la suma” y “principio del producto”. No tengáis ningún miedo pues esto es muy sencillo. Veamos un par de ilustrativos ejemplos: Considerad las zapatillas  que tenéis en casa, los zapatos que poseéis, las botas de las que disponéis, los playeros que hay en vuestro domicilio,.. y decidme: ¿De cuántas formas distintas podéis calzaros? De momento no vamos a permitir poner en un pie un tipo de calzado y en el otro pie otro tipo. Vamos a calzarnos de manera racional. La respuesta a esta pregunta es, en efecto, muy fácil. Como seguramente todos vosotros habréis deducido, el número de opciones es el resultado de sumar los pares de zapatillas, zapatos, botas, playeros y demás prendas del pie de las que dispongáis. Vayamos ahora con otra situación un tanto diferente aunque también dentro del tema de las prendas de vestir. Sacad de vuestro armario todas las camisetas y pantalones. Ahora respondedme a esta pregunta. ¿De cuantas formas “decorosas” podéis vestiros para salir a la calle? En este caso parece claro que la respuesta será el producto del número de camisetas y el número de pantalones, ya que cada una de las partes superiores puede emparejarse con todas y cada una de las partes inferiores. El primero de los ejemplos corresponde al denominado principio de la suma, mientras que el segundo se refiere al principio del producto. Es fundamental en Combinatoria detectar en qué situación nos encontramos: Si estamos en un caso del tipo “calzado” o bien del tipo “atuendo camiseta-pantalón”. Además estos dos principios se pueden combinar en situaciones donde el fondo de armario es extenso. Si sacamos todas nuestras camisetas, camisas, vestidos de una pieza, pantalones y faldas ¿cuántos modelos diferentes podemos conformar? Ahora para dar con la respuesta correcta hay que combinar ambos principios y se debe realizar el producto del número total de partes superiores (camisetas más camisas) y el número de partes inferiores (pantalones más faldas) y a continuación añadirle a ese resultado el número de vestidos de una pieza.

En consecuencia y para finalizar esta primer lección del mini curso, no olvidéis las características propias de estas dos ilustrativas situaciones: “calzado” y “atuendo”. Para contar en la primera lo fundamental es sumar mientras que para la segunda la multiplicación es obligada.