martes, 26 de marzo de 2013

Combinatoria: Variaciones

Si en un maratón popular participan 2.500 atletas, ¿cuántas apuestas hay que hacer para acertar con seguridad los tres primeros puestos?

Se trata de un sencillo problema de combinatoria y cualquier estudiante de bachillerato debería saber resolverlo. El número total de apuestas son las Variaciones de 2.500 elementos tomados de 3 en 3.

Las Variaciones de m elementos tomados de n en n se pueden calcular con varias fórmulas:

Fórmula 1

Fórmula 2

Fórmula 3

Como las Permutaciones son un caso particular de las Variaciones, Excel dispone de una única función, llamada PERMUTACIONES, para ambos casos. Como es lógico, esta función es la que nos permite hacer el cálculo del modo más fácil, pero vamos a explorar otras posibilidades.

En C3 pondremos los participantes (elementos) y en C4 los aciertos (número de elementos de cada agrupación). En C6:C10 obtendremos las diferentes soluciones del problema.

Comenzamos con la solución sencilla; es decir, empleando la función PERMUTACIONES.

En C6:
=PERMUTACIONES(C3;C4)     [Resultado: 15.606.255.000]

En C7 vamos a utilizar la fórmula 3.  Esta fórmula utiliza factoriales y puede dar problemas por desbordamiento. Excel calcula perfectamente el factorial de cualquier número pequeño, pero si es superior a 170 se produce un desbordamiento y devuelve el error #¡NUM!

En C7:
=FACT(C3)/FACT(C3-C4)     [Resultado: #¡NUM!]

Vamos a buscar otra solución; la anterior no sirve. Emplearemos la fórmula 1. Según esta fórmula, hay que multiplicar una secuencia de números decrecientes que empieza por 2.500 y terminan en 2.498. Es decir: 2500 x 2499 x 2498

¿Cómo generar automáticamente la secuencia? Muy sencillo, basta crear un nombre con las funciones FILA y DESREF de esta manera:

Accedemos a Fórmulas + Asignar nombre y creamos el siguiente nombre:

 Secuencia  =Hoja1!$C$3-FILA(DESREF(Hoja1!$A$1;;;Hoja1!$C$4))+1

Podemos comprobar que Secuencia genera los números 2500, 2499 y 2498 seleccionando H2:H20 y escribiendo: =Secuencia     [Terminar con Ctrl + Mayús + Intro]

En C8:
=PRODUCTO(Secuencia)     [Resultado: 15.606.255.000]

La fórmula 2 exige usar las funciones COMBINAT y PERMUTACIONES, algo absurdo cuando podemos hallar el resultado utilizando únicamente PERMUTACIONES, pero el método es completamente correcto.

En C9:
=COMBINAT(C3;C4)*PERMUTACIONES(C4;C4)     [Resultado: 15.606.255.000]

El último caso que vamos a ver es largo y rebuscado, pero es interesante estudiarlo para poderlo utilizar cuando se produzcan desbordamientos. Consiste en tomar logaritmos de las operaciones que pueden desbordar la capacidad de Excel y, posteriormente, aplicar el antilogaritmo para obtener el resultado final. Vamos a hacerlo paso a paso en C12:C14. La fórmula definitiva la pondremos en C10.

Partiremos de la fórmula 3, que antes no nos ha servido porque al calcular el factorial de 2.500 [FACT(C3)] se produce un desbordamiento. Vayamos razonando paso a paso. El cálculo que tenemos que hacer es el siguiente:

Tomamos logaritmos decimales (es igual hacerlo con neperianos):

Ahora, hallamos el antilogaritmo:

Desarrollando el exponente:

Hemos transformado el factorial en suma de logaritmos. Ya no hay peligro de desbordamiento.

Ahora, tenemos que generar una lista de números consecutivos del 1 al 2.500 (en realidad el valor de C3) y otra del 1 al 2.497 (C3-C4). Lo haremos con dos nuevos nombres:

 Participantes  =FILA(DESREF(Hoja1!$A$1;;;Hoja1!$C$3))
 Resta  =FILA(DESREF(Hoja1!$A$1;;;Hoja1!$C$3-Hoja1!$C$4))

En C12, calculamos (log 1 + log 2 + log 3 + ... + log 2500):
=SUMAPRODUCTO(LOG10(Participantes))     [Resultado: 7.411]

En C13, calculamos (log 1 + log 2 + log 3 + ... + log 2497):
=SUMAPRODUCTO(LOG10(Resta))     [Resultado: 7.401]

En C14, calculamos 10 elevado a la diferencia de los dos valores anteriores:
=10^(C12-C13)     [Resultado: 15.606.255.000]

En C10, ponemos la fórmula compuesta:
=10^(SUMAPRODUCTO(LOG10(Participantes))-SUMAPRODUCTO(LOG10(Resta)))

Podemos eliminar las filas 12, 13 y 14; no son necesarias.




No hay comentarios:

Publicar un comentario