부분수열

부분수열, 부분열(subsequence)이란 수학에서 원래의 수열에서 순서는 유지한 채 수열을 이루는 항 중에 일부만 모아 만들어진 수열을 말한다. 예를 들면 크기 순으로 나열된 양의 짝수의 수열은, 크기 순으로 나열된 자연수의 부분수열이 된다.

X가 집합이고, (a_k)_{k ∈ K}이 X에서의 수열이라고 하자. (a_k)가 유한수열이면, K={1,2,3,..,n}이고, 무한수열이라면, k=N 이다. 이 때, (a_k)의 부분수열은 (n_r)이 K에서의 단조 증가(strictly increasing) 수열인 $(a_{n_r})$로 정의된다.