delsekvenser

Delsekvenser, eller subsekvenser, er sekvenser som dannes fra en opprinnelig sekvens ved å fjerne enkelte elementer uten å endre rekkefølgen til de gjenværende elementene. Gitt en sekvens a1, a2, ..., an, er en delsekvens av typen a_{i1}, a_{i2}, ..., a_{ik} hvor 1 ≤ i1 < i2 < ... < ik ≤ n.

Hvis indeksene i1, i2, ..., ik er fortløpende (i_{t+1} = i_t + 1 for alle t), blir delsekvensen en kontinuerlig del av sekvensen, også kalt et segment.

For en endelig sekvens med lengde n finnes det 2^n delsekvenser (inkludert tomsekvensen). Antall delsekvenser av lengde k er binomialkoeffisienten C(n, k).

I analysen spiller delsekvenser en sentral rolle i studiet av grenseverdier og konvergens. En følge kan ha mange konvergente delsekvenser, og Bolzano–Weierstrass-satsen sier at hver avgrenende følge i et kompakt rom har en konvergent delsekvens. Innen kombinatorikk og informatikk brukes delsekvenser i mønstermatching og i problemet med lengste felles delsekvens (LCS).

Eksempel: La a = (3, 1, 4, 1, 5). En delsekvens med indeksene 1, 3, 5 er (3, 4, 5). En kontinuerlig delsekvens fra posisjonene 2 til 4 er (1, 4, 1).

Delsekvenser er et grunnleggende begrep i matematikk og datavitenskap, og beskriver hvordan man kan bevare orden selv når man fjerner elementer.