La combinatoria proporciona herramientas para contar, organizar y analizar posibilidades cuando un problema contiene un conjunto finito de opciones.
En muchas situaciones de programación e informática necesitamos responder preguntas como: ¿cuántas configuraciones son posibles?, ¿de cuántas maneras se pueden ordenar unos elementos?, ¿cuántas claves diferentes pueden generarse? o ¿cuántos caminos puede recorrer un sistema?
Cuando la cantidad de posibilidades es pequeña, podemos enumerarlas una por una. Sin embargo, cuando aumenta el número de elementos, esa estrategia deja de ser práctica. La combinatoria permite obtener la cantidad de posibilidades mediante reglas y fórmulas, sin tener que construirlas todas.
La combinatoria es la rama de la matemática que estudia las formas de contar, seleccionar, ordenar y distribuir elementos de un conjunto, considerando si el orden importa, si se permite repetir elementos y si existen restricciones.
Por ejemplo, si una actividad tiene 3 opciones y otra actividad independiente tiene 4 opciones, el número total de elecciones posibles se obtiene multiplicando:
Este razonamiento sencillo es una de las ideas fundamentales del curso: descomponer un problema en decisiones más pequeñas y contar las opciones de cada decisión.
Enumerar significa construir o listar cada caso posible. Contar significa determinar cuántos casos existen, sin necesidad de escribirlos todos.
Supongamos que un sistema debe elegir una opción de cada uno de tres grupos:
Enumerar las 40 configuraciones sería posible, pero el principio del producto permite conocer el resultado directamente. Esta diferencia es muy importante al trabajar con problemas grandes.
Antes de aplicar una fórmula combinatoria conviene analizar las características del problema. Las siguientes preguntas ayudan a elegir el método adecuado:
Responder estas preguntas evita aplicar una fórmula incorrecta y permite describir el problema con precisión matemática.
Imaginemos que un sistema dispone de 5 recursos y debe seleccionar 2 para realizar una tarea. Si el orden de selección no importa, elegir primero el recurso A y después el B representa la misma selección que elegir primero B y después A.
En este caso no estamos formando una secuencia, sino un subconjunto. Más adelante estudiaremos las combinaciones, que permiten resolver precisamente este tipo de situaciones.
Ahora supongamos que tenemos tres tareas y queremos determinar en qué orden se ejecutarán. Las secuencias:
son distintas porque el orden afecta el resultado. En este tipo de problemas utilizaremos permutaciones y, cuando solo se ordene una parte de los elementos, variaciones.
La combinatoria aparece siempre que un sistema debe trabajar con un conjunto de posibilidades. Sus resultados permiten conocer el tamaño de un espacio de búsqueda, anticipar el crecimiento de un problema y diseñar estrategias más eficientes.
| Área | Problema combinatorio | Aplicación |
|---|---|---|
| Algoritmos | Cantidad de soluciones o caminos posibles | Estimar el espacio de búsqueda y analizar alternativas. |
| Estructuras de datos | Ordenamientos, configuraciones y recorridos | Diseñar y recorrer árboles, grafos y otras estructuras. |
| Seguridad | Cantidad de claves o códigos posibles | Evaluar la resistencia de contraseñas y mecanismos de acceso. |
| Probabilidad | Casos favorables y casos posibles | Construir modelos para experimentos aleatorios. |
| Optimización | Combinaciones de decisiones | Comparar alternativas de planificación y asignación. |
Un algoritmo puede parecer sencillo, pero volverse muy lento si debe probar todas las posibilidades. Por ejemplo, al asignar tareas a personas, cada nueva tarea puede aumentar considerablemente la cantidad de asignaciones posibles.
La combinatoria ayuda a detectar este crecimiento antes de ejecutar el algoritmo. Si el número de casos crece de forma exponencial o factorial, puede ser necesario buscar una estrategia diferente, como dividir el problema, descartar casos imposibles o utilizar programación dinámica.
Este procedimiento también es útil al transformar una solución matemática en un algoritmo, porque obliga a definir con exactitud qué casos deben considerarse.
La combinatoria ofrece un lenguaje para estudiar las posibilidades de un problema y una colección de técnicas para contarlas de manera ordenada. Su importancia en informática no se limita a obtener un número: también permite comprender cómo crecen los problemas y tomar mejores decisiones al diseñar algoritmos.
En el próximo tema estudiaremos la historia y los fundamentos de la combinatoria, para comprender cómo se construyeron sus principales ideas.