[Discrete Mathematics] 수열(sequence)과 문자열(string)

---

수열 (Sequence)

 

수열 $ s $ 는 정의역 $ D $ 가 정수의 부분집합인 함수이다. $ s(n) $ 대신 $ s_n $ 표기법을 사용하며, 이때 $ n $ 을 수열의 인덱스(index)라 한다. $ D $ 가 유한 집합인 수열을 유한 수열, 그렇지 않으면 무한 수열이라 한다. 수열은 $ s $ 으로 표기하고, 수열의 단일 원소는 인덱스를 붙여 $ s_n $ 으로 나타낸다.

무한 수열은 다음과 같은 수열을 고려해 확인해볼 수 있다. 수열 $ s : 2, 4, 6, \dots , 2n , \dots $ 을 고려하면 $ n $ 번째 원소는 $ 2n $ 이다. 만약 정의역이 양의 정수 집합 $ \mathbb{Z}^+ $ 라면 $ s_1 = 2, s_2 = 4, \dots , s_n = 2n, \dots $ 이므로 수열 $ s $ 는 무한 수열이다. 한편 수열 $ t : a, a, b, a, b $ 를 고려하면 $ t_1 = a, t_2 = a, \dots , t_5 = b $ 이므로 정의역이 $ \{1, 2, 3, 4, 5\} $ 인 유한 수열이다.

수열은 다음에 따라 다르게 표기할 수 있다.

만약 수열 $ s $ 의 정의역이 연속된 정수 집합 $ \{ k, k+1, k+2, \dots \} $ 이고 $ n $ 이 $ s $ 의 인덱스라면 수열 $ s $ 는 $ \{ s_n \} ^{\infty}_{n=k} $ 로 나타낼 수 있다.

만약 정의역이 음이 아닌 정수 집합 $ \mathbb{Z}^{\text{nonneg}} $ 인 수열 $ s $ 는 $ \{s_n\}^{\infty}_{n=0} $ 으로 나타낼 수 있다.

만약 정의역이 연속된 집합 $ \{ i, i+1, \dots, j \} $ 라면 수열 $ s $ 는 $  \{s_n\}^{j}_{n=i} $ 로 나타낼 수 있다.

 

---

증감에 따른 수열 분류

 

• 증가 수열 (Increasing)

수열 $ s $ 가 증가 수열이려면 $ s $ 의 정의역의 모든 $ i , j $ 에 대해 $ i < j $ 일 때 $ s_i < s_j $ 여야 한다.

• 감소 수열 (Decreasing)

수열 $ s $ 가 감소 수열이려면 $ s $ 의 정의역의 모든 $ i , j $ 에 대해 $ i < j $ 일 때 $ s_i > s_j $ 여야 한다.

• 비감소 수열 (Nondecreasing)

수열 $ s $ 가 비감소 수열이려면 $ s $ 의 정의역의 모든 $ i , j $ 에 대해 $ i < j $ 일 때 $ s_i \leq s_j $ 여야 한다.

• 비증가 수열 (Nonincreasing)

수열 $ s $ 가 비증가 수열이려면 $ s $ 의 정의역의 모든 $ i , j $ 에 대해 $ i < j $ 일 때 $ s_i \geq s_j $ 여야 한다.

 

---

부분 수열 (Subsequence)

 

어떤 수열 $ s $ 에서 일부 항들을 선택하여 수열을 만들 때, 그 항들의 순서가 수열 $ s $ 와 동일하다면 그 수열을 부분 수열이라 한다.

예를 들어 수열 $ a, b, c, d, e $ 에서 $ b, c $ 는 부분 수열이지만, $ c, b $ 는 부분 수열이 아니다.

 

---

수치 수열의 덧셈과 곱셈

 

만약 $ \{a_i\}^{n}_{i=m} $ 가 수열이라면 다음과 같이 정의할 수 있다.

$$ \sum^n_{i=m} a_i = a_m + a_{m+1} + \cdots + a_n $$

$$ \prod^n_{i=m} a_i = a_m \times a_{m+1} \times \cdots \times a_n $$

여기서 $ i $ 는 인덱스, $ m $ 은 하한(lower limit), $ n $ 은 상한(upper limit)이라 한다.

만약 $ S $ 가 정수들의 유한 집합이고, $ a $ 가 수열이라면 $ \sum_{i \in S} a_i $ 와 $ \prod_{i \in S} a_i $ 는 각각 $ \{ a_i \mid i \in S \} $ 집합의 원소들의 합과 곱을 나타낸다.

 

---

문자열 (String)

 

집합 $ X $ 가 유한 집합일 때, 문자열이란 $ X $ 의 원소들로 구성된 유한 수열을 말한다.

예를 들어 수열 $ \beta $ 가 있고, $ X = \{ a, b, c \} $ 일 때, $ \beta_1 = b $, $\beta_2 = a $, $\beta_3 = c $ 라면 $ \beta $ 는 문자열이고, $ bac $ 로 표기된다. 문자열은 수열이므로 순서가 중요하고 따라서 $ bac $ 와 $ bca $ 는 다르다.

문자열에서 반복되는 문자는 지수를 이용해 표시할 수 있다. 예를 들어서 문자열 $ baaaaccc $ 는 $ ba^4c^3 $ 으로 표기 가능하다.

아무런 원소가 없는 문자열은 공문자열(null string)이라 하며, $ \lambda $ 로 표시한다. 주의해야 할 것은 $ \emptyset $ 과 $ \{ \lambda \} $ 는 다르다. $ \{ \lambda \} $ 는 $ \lambda $ 가 들어있는 집합이기 때문이다.

$ X^* $ 은 공문자열을 포함한 $ X $ 위의 모든 문자열의 집합이고, $ X^+ $ 는 공문자열을 제외한 모든 문자열의 집합이다.

예를 들어 $ X = \{ a, b \} $ 일 때, $ X^* $ 의 원소로는 $ \lambda $, $ a $, $ b $, $ a^{20}b^4 $ 등이 있다.

 

---

문자열의 길이, 연결, 부분 문자열

 

• 문자열의 길이

문자열의 길이(length)는 문자열의 원소 수로 정의된다. 예를 들어 $ a = abada $ 일 때 $ a $ 의 길이는 5 이고, $ | a | = 5 $ 라 표기한다.

 

• 연결 (Concatenation)

두 문자열을 이어 붙이는 것을 말한다. 예를 들어 두 문자열 $ \alpha $ 와 $ \beta $ 가 있을 때 $ \alpha $ 에 $ \beta $ 를 이어 붙이면, 즉 $ \alpha $ 와 $ \beta $ 를 연결하면 $ \alpha \beta $ 가 된다.

$ \alpha = abb $ 이고 $ \beta = cad $ 라면 $ \alpha \beta = abbcad $ 이고, $ \beta \alpha = cadabb $ 이다. 공문자열을 활용하면 $ \alpha \lambda = \alpha = abb $ 이다.

 

• 부분 문자열 (Substring)

문자열 $ \beta $ 가 문자열 $ \alpha $ 의 부분 문자열이라면, 문자열 $ \gamma $ 와 $ \delta $ 가 존재하여 $ \alpha = \gamma \beta \delta $ 를 만족해야 한다. 반대로 이 조건을 만족한다면 부분 문자열이다.

예를 들어 $ \beta = abb $ 이고, $ \alpha = dcabb $ 라면, $ \gamma = dc $ 이고, $ \delta = \lambda $ 일 때 $ \alpha = \gamma \beta \delta $ 이므로 $ \beta $ 는 $ \alpha $ 의 부분 문자열이다.