La combinatoria surgió de problemas concretos de organización y azar, y con el tiempo se convirtió en una herramienta fundamental para las matemáticas y la informática.
En el tema anterior vimos que la combinatoria permite contar posibilidades sin enumerarlas una por una. Para aplicar correctamente sus métodos conviene conocer las ideas que los sostienen: distinguir objetos, definir cuándo dos resultados son diferentes y organizar el conteo en etapas.
La combinatoria no apareció de una sola vez. Se desarrolló a partir de preguntas sobre juegos, sorteos, agrupaciones, calendarios, códigos y configuraciones. Cada problema llevó a formular principios más generales.
Desde la antigüedad, distintas culturas estudiaron agrupaciones, patrones numéricos y formas de ordenar objetos. El triángulo que hoy asociamos con Pascal, por ejemplo, aparece con variaciones en trabajos matemáticos de China, India y otras regiones mucho antes de la época moderna.
Estos estudios no siempre utilizaban la notación actual. Sin embargo, ya contenían ideas relacionadas con coeficientes binomiales, sucesiones, elecciones y distribución de elementos.
La idea central era siempre similar: establecer una forma sistemática de obtener resultados a partir de casos más pequeños.
Durante los siglos XVII y XVIII, los problemas relacionados con juegos de azar impulsaron el desarrollo de métodos de conteo más precisos. Las preguntas sobre dados, cartas y apuestas exigían calcular cuántos resultados eran posibles y con qué frecuencia podían ocurrir.
El estudio de estos problemas contribuyó al desarrollo conjunto de la combinatoria y la probabilidad. Para calcular la probabilidad de un evento, primero es necesario conocer el número de casos posibles y el número de casos favorables.
Esta relación será importante cuando estudiemos el curso de Probabilidad para programadores.
Una característica de la combinatoria es transformar un caso particular en una regla aplicable a muchos problemas. Por ejemplo, en lugar de contar manualmente las formas de ordenar tres objetos, podemos descubrir una expresión que funcione para cualquier cantidad de objetos.
Si hay n objetos diferentes y se utilizan todos una sola vez, la cantidad de ordenamientos es:
La letra n representa una cantidad cualquiera. Esta generalización permite resolver problemas grandes con una única fórmula.
Para resolver un problema combinatorio debemos separar dos ideas:
Por ejemplo, si los objetos son A, B y C, algunas configuraciones posibles son:
El conjunto de todas las configuraciones posibles se denomina espacio de configuraciones o espacio de búsqueda. En informática, conocer su tamaño ayuda a estimar el trabajo que tendría que realizar un algoritmo.
Una decisión fundamental consiste en establecer cuándo dos resultados deben considerarse distintos. El orden puede ser relevante o irrelevante según el problema.
| Situación | ¿Importa el orden? | Ejemplo |
|---|---|---|
| Asignar puestos | Sí | Asignar Ana-Beto no es igual que Beto-Ana. |
| Elegir integrantes de un equipo | No | El equipo {Ana, Beto} es el mismo que {Beto, Ana}. |
| Crear una secuencia | Sí | La secuencia 1-2-3 difiere de 3-2-1. |
| Seleccionar características | Depende | Depende de si las posiciones tienen significado. |
También debemos determinar si un objeto puede utilizarse más de una vez. Una secuencia de símbolos puede permitir repeticiones, mientras que una asignación de personas a puestos normalmente utiliza cada persona una sola vez.
Las restricciones reducen el número de configuraciones. Por ejemplo, si una clave debe comenzar con una letra determinada, si dos tareas no pueden ocupar posiciones consecutivas o si una persona no puede recibir cierto puesto, no todos los casos son válidos.
La mayor parte de los métodos de la combinatoria se apoya en algunos principios básicos:
Estos principios se estudiarán con más detalle en los siguientes temas y serán la base para comprender permutaciones, variaciones y combinaciones.
Una correspondencia uno a uno relaciona cada elemento de un conjunto con un único elemento de otro conjunto, sin que sobren ni se repitan elementos. Si podemos construir esta correspondencia, contar un conjunto equivale a contar el otro.
Por ejemplo, las configuraciones de una selección pueden asociarse con las hojas de un diagrama de árbol. Si cada configuración produce una sola hoja y cada hoja representa una sola configuración, la cantidad de hojas es igual a la cantidad de resultados.
Esta idea es útil porque permite reemplazar un problema difícil por otro que sea más sencillo de contar.
En informática, una configuración puede representar una entrada, una asignación, una ruta, una contraseña, un estado o una solución candidata. El algoritmo puede explorar algunas o todas esas configuraciones, según el problema.
La historia de la combinatoria muestra cómo problemas concretos dieron lugar a principios generales de conteo. Sus fundamentos siguen siendo los mismos: identificar los objetos, definir las configuraciones y establecer reglas para contarlas sin omisiones ni repeticiones.
En el próximo tema comenzaremos el estudio de los principios básicos de conteo, que permitirán resolver problemas combinatorios de forma ordenada.