subsecuencia

Una subsecuencia de una secuencia (a_n) es una secuencia obtenida eliminando algunos términos de la original, sin cambiar el orden de los términos que permanecen. Formalmente, si n_1 < n_2 < ... es una sucesión de enteros naturales, entonces (a_{n_k}) es una subsecuencia de (a_n). Por ejemplo, de la secuencia (3, 8, 2, 7, 4, 9) se puede obtener la subsecuencia (3, 2, 4) tomando los índices 1, 3 y 5.

La subsecuencia se distingue de una subsecuencia contigua (también llamada subarreglo o subcadena en otros contextos), que exige que los términos elegidos correspondan a posiciones consecutivas: (a_m, a_{m+1}, ..., a_{m+t}). En una subsecuencia no es necesario que los índices sean consecutivos.

Propiedades y notación. Si (a_n) es una secuencia y n_1 < n_2 < ... es una sucesión de índices, entonces la longitud de la subsecuencia (a_{n_k}) es el número de términos que contiene. La subsecuencia vacía tiene longitud 0. Las subsecuencias pueden ser finitas o infinitas conforme a la longitud de la secuencia original.

Aplicaciones. En matemáticas y teoría de la computación, las subsecuencias son herramientas clave. Problemas como la subsecuencia común más larga (LCS) entre dos secuencias y el problema de la subsecuencia creciente más larga (LIS) son fundamentales en algoritmos y bioinformática. En análisis, a menudo se emplea la idea de extraer subsecuencias convergentes para estudiar límites de series.

Notas. El concepto es central en la definición de convergencia y en técnicas de prueba, y se aplica tanto a secuencias numéricas como a cadenas de caracteres o arreglos biológicos. Ver también subsecuencia contigua y subsecuencia en teoría de grafos y combinatoria.