1. ¿Qué es una sucesión?
Una sucesión es una lista ordenada de valores. Se suele escribir como a0, a1, a2, ... o mediante una función an, donde n indica la posición del término.
En combinatoria, cada término normalmente representa la cantidad de estructuras que pueden construirse para un tamaño determinado.
2. Sucesiones combinatorias
Una sucesión combinatoria relaciona un parámetro de tamaño con un número de configuraciones. Por ejemplo, si contamos subconjuntos de un conjunto de n elementos, obtenemos:
an = 2n
Para n = 0, 1, 2, 3, 4: 1, 2, 4, 8, 16, ...
3. El índice y el significado del término
Antes de analizar una fórmula es importante identificar qué significa n. Puede ser la cantidad de elementos, la longitud de una cadena, el número de pasos o el tamaño de una entrada.
También hay que decidir si la sucesión comienza en n = 0 o en n = 1. Esa elección cambia el primer término y, a veces, la forma de la recurrencia.
4. Sucesiones definidas por una fórmula
Una fórmula directa permite calcular un término sin conocer necesariamente los anteriores. Algunos ejemplos combinatorios son:
an = 2n: subconjuntos de un conjunto con n elementos.
bn = n!: ordenamientos de n elementos distintos.
cn = C(n, k): selecciones de k elementos entre n.
5. Sucesiones definidas por recurrencia
Una relación de recurrencia expresa un término a partir de términos anteriores. Por ejemplo, la sucesión de Fibonacci se define mediante:
F0 = 0, F1 = 1
Fn = Fn-1 + Fn-2, para n ≥ 2.
Las recurrencias son especialmente útiles cuando un problema puede dividirse en casos más pequeños.
6. Ejemplo: cadenas binarias
La cantidad de cadenas binarias de longitud n es 2n, porque en cada posición existen dos elecciones independientes: 0 o 1.
function cadenasBinarias(n) {
return Math.pow(2, n);
}
for (let n = 0; n <= 8; n++) {
console.log("Longitud " + n + ": " + cadenasBinarias(n));
}7. Ejemplo: subconjuntos
La misma sucesión 2n cuenta todos los subconjuntos de un conjunto con n elementos. Cada elemento puede estar incluido o excluido.
function cantidadSubconjuntos(n) {
let total = 1;
for (let i = 0; i < n; i++) {
total *= 2;
}
return total;
}
console.log(cantidadSubconjuntos(5)); // 328. Sucesiones lineales y exponenciales
Una sucesión puede crecer linealmente, como an = 3n + 1, o exponencialmente, como an = 2n. En informática, esta diferencia ayuda a estimar cómo aumenta el espacio de búsqueda.
Los conteos de decisiones independientes suelen producir crecimiento exponencial; las estructuras con una cantidad fija de opciones por posición son un ejemplo típico.
9. Sucesiones y sumas acumuladas
Si an cuenta las configuraciones de tamaño n, la suma An = a0 + ... + an cuenta configuraciones de varios tamaños. Por ejemplo:
1 + 2 + 4 + 8 = 15
La suma de las cantidades de cadenas binarias de longitud 0 a 3 es 15.
10. Sucesiones con restricciones
Cuando se agregan restricciones, la sucesión cambia. Por ejemplo, las cadenas binarias sin dos unos consecutivos producen 1, 2, 3, 5, 8, ... y cumplen la recurrencia:
an = an-1 + an-2
La razón es que una cadena válida termina en 0 o termina en 10; esos casos se reducen a cadenas más pequeñas.
11. Generación iterativa de una sucesión
Una implementación iterativa guarda los términos necesarios y avanza desde los casos iniciales. Este enfoque evita repetir cálculos que ya fueron realizados.
function sinUnosConsecutivos(n) {
if (n === 0) return 1;
if (n === 1) return 2;
let anteriorDos = 1;
let anterior = 2;
for (let i = 2; i <= n; i++) {
const actual = anterior + anteriorDos;
anteriorDos = anterior;
anterior = actual;
}
return anterior;
}
console.log(sinUnosConsecutivos(6)); // 2112. Sucesiones, algoritmos y eficiencia
Una sucesión combinatoria puede describir cuántos estados, caminos o posibilidades debe revisar un algoritmo. Comparar el crecimiento de los términos permite anticipar cuándo una búsqueda exhaustiva será costosa.
13. Simulación: explorar sucesiones combinatorias
Selecciona una sucesión y observa sus primeros términos. La tabla muestra el índice, el valor y la variación respecto del término anterior.
| Índice n | Término an | Incremento |
|---|
14. Resumen
Las sucesiones combinatorias modelan cantidades que dependen de un tamaño. Pueden definirse mediante fórmulas, recurrencias o algoritmos iterativos. Identificar su crecimiento y sus condiciones iniciales permite resolver problemas de conteo y analizar el costo de soluciones informáticas.