1. Combinatoria y estructuras de datos
Una estructura de datos organiza elementos siguiendo reglas determinadas. La combinatoria permite contar cuántas organizaciones distintas pueden formarse y estudiar qué ocurre cuando se agregan restricciones.
Ese conteo aparece al analizar memoria, recorridos, índices, configuraciones y operaciones posibles.
2. Secuencias ordenadas
Si n elementos distintos se colocan en una secuencia, existen n! ordenamientos posibles. El orden importa porque cambiar dos posiciones produce una secuencia diferente.
Con los elementos A, B y C se pueden formar: ABC, ACB, BAC, BCA, CAB y CBA.
Total: 3! = 6.
3. Listas con elementos repetidos
Cuando algunos valores se repiten, varias permutaciones dejan de ser distinguibles. Si hay n elementos y repeticiones de tamaños r1, r2, ..., el número de secuencias diferentes es:
n! / (r1! r2! ...)
Este conteo es útil para analizar listas con categorías o valores duplicados.
4. Pilas y colas
En una pila, los elementos se retiran en el orden inverso al de inserción. En una cola, se retiran en el mismo orden en que llegaron.
La combinatoria ayuda a contar secuencias de operaciones válidas, especialmente cuando se mezclan inserciones y extracciones bajo una regla de disponibilidad.
5. Secuencias de operaciones válidas
Una secuencia de operaciones de pila puede representarse con un símbolo de inserción y otro de extracción. Nunca puede haber más extracciones que inserciones en un prefijo, y al final ambas cantidades deben coincidir.
Por esa condición de balance, la cantidad de secuencias válidas está relacionada con los números de Catalan.
6. Árboles binarios
Los árboles binarios organizan cada nodo con hasta dos descendientes. Para una cantidad fija de nodos, pueden existir muchas formas estructurales distintas.
El número de árboles binarios completos con n nodos internos es Cn, un número de Catalan. La raíz separa el árbol en un subárbol izquierdo y uno derecho.
function catalan(n) {
const valores = [1];
for (let tam = 1; tam <= n; tam++) {
valores[tam] = 0;
for (let izquierda = 0; izquierda < tam; izquierda++) {
valores[tam] += valores[izquierda] * valores[tam - 1 - izquierda];
}
}
return valores[n];
}
console.log("Árboles con 3 nodos internos:", catalan(3)); // 57. Árboles de búsqueda
Al insertar claves distintas en un árbol de búsqueda, el orden de inserción puede producir estructuras diferentes. Para n claves, el número de formas estructurales posibles está relacionado con los números de Catalan.
La forma del árbol influye en la altura y, por tanto, en el costo de buscar, insertar o eliminar elementos.
8. Montículos y restricciones de orden
Un montículo es un árbol que cumple una relación de prioridad entre padres e hijos. No todas las permutaciones de valores son válidas; la propiedad de orden filtra las configuraciones posibles.
Contar estas configuraciones permite estudiar cuántos estados puede alcanzar una estructura durante un algoritmo.
9. Tablas y asignación de posiciones
Una tabla con n posiciones y valores elegidos de un conjunto de tamaño k puede tener kn configuraciones si se permite repetir valores. Si no se permite repetir, el número es una variación:
V(k, n) = k(k - 1)(k - 2) ... (k - n + 1)
10. Conjuntos y subconjuntos
Una estructura que representa una colección puede tener cualquier subconjunto de un universo de n elementos. Por eso existen 2n configuraciones posibles, incluyendo el conjunto vacío y el conjunto completo.
Si se fija el tamaño de la colección en k, el conteo se reduce a C(n, k).
11. Grafos almacenados como estructuras
Un grafo con n vértices puede tener diferentes conjuntos de aristas. En un grafo simple no dirigido, cada par de vértices puede estar conectado o no:
2C(n, 2) grafos simples distintos sobre n vértices etiquetados.
Esta cantidad explica por qué enumerar todos los grafos se vuelve costoso incluso con pocos vértices.
12. Recorridos y representaciones
Una misma estructura puede recorrerse de diferentes maneras. En árboles aparecen recorridos en preorden, inorden y postorden; en grafos, recorridos en anchura o profundidad.
El conteo permite distinguir entre las formas de recorrer una estructura y las configuraciones estructurales que pueden existir.
13. Ejemplo: configuraciones de una estructura
La siguiente función calcula cuántas formas existen de elegir y ordenar k elementos de un conjunto de n elementos. Es el conteo de variaciones sin repetición.
function variaciones(n, k) {
if (k > n || k < 0) return 0;
let resultado = 1;
for (let i = 0; i < k; i++) {
resultado *= n - i;
}
return resultado;
}
console.log(variaciones(5, 3)); // 6014. Simulación: configuraciones según la estructura
Selecciona una cantidad de elementos y compara el número de secuencias ordenadas, subconjuntos y árboles binarios asociados.
| Estructura o colección | Cantidad de configuraciones |
|---|
15. Elegir una representación
El conteo no reemplaza el diseño de una estructura de datos, pero permite conocer sus posibilidades y límites. Una representación adecuada debe facilitar las operaciones más importantes y evitar guardar información innecesaria.
16. Resumen
La combinatoria se aplica a listas, pilas, colas, árboles, conjuntos, tablas y grafos. Permutaciones, subconjuntos, variaciones y números de Catalan permiten contar configuraciones y secuencias válidas. Estos conteos ayudan a analizar memoria, recorridos, operaciones y complejidad algorítmica.