부분수열

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

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