|
이산수학 Discrete Mathematics |
||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" |
이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수( /공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
1. 개요
漸 化 式 / Recurrence relation어떤 수열의 각각의 항들의 관계를 나타낸 식이다. 점화식을 만족시키는 수열을 점화식의 해라 하고, 이 해를 찾는 것을 점화식을 푼다고 말한다. 예로 점화식 [math(a_{n+1} = a_n + d)]은 [math(a_n = a_0 + nd)] (혹은 [math(a_1 + (n-1)d)])로 초항에 따라 유일한 해가 결정되고, 공차가 [math(d)]인 등차수열을 의미한다. 벡터, 행렬 등 다른 수학적 대상의 열을 묘사하는 점화식들도 생각할 수 있고, 마치 파스칼의 삼각형 항등식처럼 2개 이상의 변수를 갖는 수열에 대해서 생각할 수도 있다.
보통 점화식은 [math(n)]번째의 항을 이전에 나온 항들로 나타내는 공식으로 나타나고, 이 점화식을 만족시키는 수열은 초깃값에 따라 유일하게 결정된다. 이렇게 수열을 정의하는 것을 수열의 귀납적 정의(recursive definition)라 한다. 이 방법을 사용하면 일반항으로 수열을 나타내는 것보다 훨씬 다양한 수열을 나타낼 수 있다. 다만 모든 점화식이 [math(n)]번째 항을 명확한 형태로 묘사하는 것은 아니고, 이런 경우에는 둘 이상의 해가 존재할 수 있으며 만족시키는 수열을 모두 구하는 것이 목표가 될 수도 있다. 물론 명시적인 점화식의 경우에도 항을 찾을 수 있을 뿐이지 수열의 일반항을 정리해서 점화식을 푸는 건 쉬운 일이 아니다. 상수 계수 선형점화식을 비롯한 교과서의 몇몇 예외를 제외하면 점화식의 대수적인 일반항(closed form)은 웬만해선 존재하지 않는다고 보아도 좋다.
조합론에서 [math(n)]에 따라 변화하는 어떤 대상의 개수를 구하고 싶지만 직접 일반항 계산이 어려울 때, 점화식을 먼저 만들어놓고 그 다음 점화식을 풀어 개수를 구하는 방식이 많이 쓰인다. 피보나치 수열이나 카탈란 수 등등의 예시가 있다. 물론 이런 쉬운 경우를 제외하면 현실적으로는 점화식만을 세우는 것도 컴퓨터 프로그램으로 [math(n)]번째 항을 계산할 수 있게 해 주기 때문에 위업이며( 동적 계획법과 연관된다), 점근적 성장(asymptotic)을 알아내는 것이 최종목표로 간주된다.
미분방정식이 연속적으로 변하는 대상을 묘사하는 수학적 도구인 것과 비슷하게, 점화식은 이산적으로 변하는 대상을 묘사할 수 있다. 미분방정식이 다루는 연속적 동역학계(continuous dynamical system)와 대비되게 [math(a_{n+1} = f(a_n) )] 류의 식으로 결정되는 시스템을 이산 동역학계(discrete dynamical system)라는 이름으로 부른다. 비교적 근래에 발생한 이 분야는 미분방정식에 비해 덜 알려져서 여러 분야에서 응용가능한 잠재력이 있지만, 실상을 들여다보면 여기도 미분방정식 이상으로 카오스로 가득찬 혼돈의 세계라서 쉽사리 접근하기는 힘들다. 경우에 따라서는 점화식이 미분방정식보다 풀기가 어렵다고 말하는 사람들도 많다.
2020년 현재, 명목상으로는 고교 과정에서 빠졌으나, 수1의 수열단원에서는 이름만 바꾼 '수열의 귀납적 정의'로 등장한다. 게다가 여전히 몇몇 학원가나 사교육 등지에서는 '발화식'이라는 명칭을 직접적으로 사용하는 것이 자연스럽게 여겨질정도니 사실상 안빠지고 계속 교육과정에 남아있다고해도 무방하다. 내신에서는 간단한 명제를 수학적 귀납법으로 증명하는 것이 서술형 단골일뿐더러 빈칸을 뚫어놓고 객관식으로도 출제될 수 있다. 나중에 가면 다른 주요과목을 챙기느라 빵꾸가 난 부분을 채우기 힘들어지니 진도를 나갈 때 꼭꼭 챙겨두자.
2. 선형 점화식
수열 [math(\{a_n\})]에 대하여 [math(\ a_{n+k}+c_1 a_{n+k-1}+c_2 a_{n+k-2}+\cdots+c_k a_n=f(n) )] 의 형태의 점화식을 선형 점화식이라고 한다. (단, [math( c_1, \cdots,c_k)]는 상수, [math(c_k \neq 0 )])고교과정 내의 거의 모든 종류의 점화식은 선형점화식의 일부로 간주할 수 있다.
여기서 [math(f(n)=0)]이면 동차 선형 점화식이라 하고, [math(f(n) \neq 0)]이면 비동차 선형 점화식이라 한다. 비동차 선형 점화식을 동차 선형 점화식으로 바꾸면 일반항을 구하기가 쉬워지는데, 그렇게 만드는 방법은 특수해를 구하는 것이다.
특수해 [math(\{b_n\})]을 구했다고 하자.[1] 그리고 새로운 수열 [math(\{x_n\})]을 [math(x_n = a_n -b_n)]으로 정의한다. 그러면 수열[math(\{x_n\})]에 대한 점화식은
[math(\ x_{n+k}+c_1 x_{n+k-1}+...+c_k x_n=0 )]이 된다. 이로써 특수해만 구할 수 있다면 비동차 선형 점화식은 동차 선형 점화식으로 바꿀 수 있음을 알 수 있다.
이때, [math(r )]에 대한 방정식 [math(r^k+c_1r^{k-1}+\cdots+c_k=0 )]을 이 점화식의 특성방정식이라 한다. 결론부터 말하자면, 특성방정식의 근이 [math(\alpha_1, \alpha_2, \cdots , \alpha_k )] 이면 [math(x_n )]은 [math({\alpha_1}^n, {\alpha_2}^n, \cdots , {\alpha_k}^n )]의 일차결합으로 나타내어진다. 즉, [math(x_n )]의 가능한 모든 일반항은 [math(x_n=A_1{\alpha_1}^n + A_2{\alpha_2}^n+ \cdots + A_k{\alpha_k}^n )]로 나타내어진다. ([math(A_1, A_2, \cdots ,A_k )]는 상수) 따라서 [math(a_n=b_n+x_n=b_n+A_1{\alpha_1}^n + A_2{\alpha_2}^n+ \cdots + A_k{\alpha_k}^n )]이 된다.
단, 여기서 [math(\alpha_1, \alpha_2, \cdots , \alpha_k )]는 모두 서로 달라야 한다(선형 독립). 만약 이 중 서로 같은 것들이 있다면, 즉 특성방정식이 중근을 갖는다면 일반항은 약간 달라진다. 어떤 근 [math(\beta )]가 중복수가 m인 중근이라면 [math({\beta}^n, n{\beta}^n, \cdots , n^{m-1}{\beta}^n )]으로 대신해 일차결합을 해야 한다.
2.1. 동차선형방정식의 해집합 증명
분야마다 다른 다양한 방법이 있다.- 귀납법과 치환을 이용한 초등적 증명
- 우선 [math( a_{n+1} = c a_{n} + f(n) (c \neq 0))] 꼴의 비동차 선형 점화식을 푸는 방법을 정리한다. 양변을 [math(c^{n+1})]로 나누면 [math( a_{n+1}c^{-n-1} = a_{n}c^{-n} + f(n)c^{-n-1})] 이므로 계차수열을 이용해 [math( a_n = c^n (a_0 + \sum f(m) c^{-m-1}))]로 풀 수 있다.
이제 본 문제로 돌아가, 차수에 대한 귀납법을 사용한다. 특성방정식이 [math(r^k+c_1r^{k-1}+\cdots+c_k=(r-\alpha)(r^{k-1}+d_1r^{k-2}+\cdots+d_{k-1}=0))]으로 인수분해된다고 하자. 그러면 [math(b_n = a_{n+1} - \alpha a_{n})]으로 정의한 수열은 점화식 [math( b_{n+k-1} + d_1 b_{n+k-2} + \cdots + d_{k-1} b_n = 0 )]을 만족한다! [math(b_n)]에 대해 귀납가설을 적용해 [math(b_n)]을 [math(n^{k-1} \beta^n)] 등의 일차결합으로 나타내고, 이제 위에서 언급한 비동차방정식 [math( a_{n+1} = \alpha a_n + b_n )]을 푼다.
본래 방정식의 특성방정식이 중근이 없으면 [math(a_n)]은 [math( \sum \alpha^{n-m} \beta^m)]과 [math(\alpha^n)] 꼴의 일차결합으로 이루어지므로 증명된다. 중근이 있다면 [math(m^{k-1} (\beta/\alpha)^m)] 꼴의 수열의 합을 구해야 하는 등 조금 더 귀찮다.
- 생성함수 이용
- 수열 [math(a_n)]의
생성함수(generating function)는 멱급수 [math( \sum_{n=0}^{\infty} a_n x^n)]으로 정의된다. [2]
[math(a_n)]의 생성함수를 [math(A(x))]라 하자. 만약 [math(a_n)]이 점화식 [math( a_{n+k}+c_1 a_{n+k-1}+c_2 a_{n+k-2}+\cdots+c_k a_n=0)]을 만족한다면, [math(C(x) = 1 + c_1 x + c_2 x^2 + \cdots + c_k x^k)]에 대해 식 [math(D(x)=A(x)C(x))]에서 [math(x^{n+k})]의 계수는 [math(a_{n+k}+c_1 a_{n+k-1}+c_2 a_{n+k-2}+\cdots+c_k a_n=0)]이다. 즉 [math(D(x))]는 [math((k-1))]차 이하의 다항식이어야 하고, [math(A(x)=D(x)/C(x))]로 쓸 수 있다.
유리식 [math(A(x)=D(x)/C(x))]의 계수를 다시 전개하기 위해서는 부분분수분해를 사용한다. 주어진 점화식의 특성근이 [math(\alpha_i)]들이라면 [math(C(x)=\prod (1-\alpha_i x)^{e_i} )]꼴로 인수분해되므로, 부분분수분해를 하면 [math(A(x))]를 [math((1-\alpha x)^{-k})]들의 일차결합으로 나타낼 수 있다.
마지막으로 다음 항등식
[math(\frac{1}{(1-\alpha x)^k}= \sum_{n=0}^{\infty} \binom{n+k-1}{k} \alpha^n x^n )]
을 이용한다. 이 전개식의 증명은 [math(k)]에 대한 귀납법, 테일러 정리, 생성함수 전문가라면 좌변을 '조합적으로' 중복조합으로 해석하는 등 어떻게 해도 좋다.
- 행렬의 조르당 형식 이용
- 벡터 [math(v_n=(a_n,a_{n+1},\cdots,a_{n+k-1})^t)]을 생각하고, 이에 대한 점화식을 다음과 같이 구성한다.
[math( v_{n+1} = \left( \begin{array}{c} a_{n+1} \\ a_{n+2} \\ \vdots \\ \vdots \\ a_{n+k} \end{array} \right) = \left( \begin{array} {ccccc} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\-c_k & -c_{k-1} & -c_{k-2} & \cdots & - c_{1} \\ \end{array} \right) v_n )]
[math(A)]를 저 안에 주어진 행렬이라고 하면 [math(v_n = A^n v_0)]으로 점화식이 풀린다. 이제 조르당 분해를 이용해 [math(A^n)]을 구하면 되는데, 한편 [math(A)]가 동반 행렬(companion matrix)임을 관찰하면 [math(A)]의 조르당 분해는 항상 최대 크기의 블록들로 나뉘어짐을 알 수 있다. 여기까지 왔으면 사실상 끝.
3. 점화식과 이산 동역학계
점화식이 '이산 동역학계'라는 이름으로 간주된 것은 상당히 현대적인 관점으로, 미분방정식으로 변화를 바라보는 사고방식이 무르익을 즈음에 이것이 이산적인 형태에 적용되었다고 볼 수 있다. 상미분방정식으로 형성되는 복잡계가 변화율이 연속적인 시간과 현재상태에 따라 결정되는 [math(x'(t) = F(x,t))]의 식을 하고 있듯이, [math(a_{n+1}=f(a_n,n))]의 식은 [math(n)]을 이산적인 시간으로 간주했을 때 어떻게 [math(a_n)]의 상태가 바뀌는지를 묘사한다고 볼 수 있기 때문이다. 개념적으로는 미분을 모르더라도 이해할 수 있는 내용이지만, 이런 식의 해석은 마르코프 연쇄(Markov chain)나 아래 얘기할 로지스틱 사상(logistic map) 등을 생각할 19세기 말에야 이루어졌다. 이러한 관점에서 보면 [math(a_n)]의 식을 풀지 못해도, 수렴, 발산, 진동과 같은 추이만 파악해도 충분한 성과라 볼 수 있겠지만... 점화식의 경우에는 이것이 불가능해지는 카오스가 정말 간단한 형태에서조차 등장한다.함수 로지스틱 사상(logistic map)은 복잡계 [math( a_{n+1} = f(a_n) )]을 결정짓는 다음의 함수로
[math( f(x) = rx(1-x), \quad 0<x<1 )]
여기서 [math(r)]은 [math(0<r<4)] 범위 내의 매개변수이다. 이 식은 생태학에서 생물의 개체수 변화를 설명하는
로지스틱 방정식의 이산적인 형태로, 양변을 [math(x)]로 나누면 바로 유사성을 볼 수 있다. 하지만 간단히 초등함수로 풀려서 그래프 개형도 단순한 로지스틱 방정식의 경우와는 다르게, 이 수열이 보이는 패턴은 수렴하거나, 여러 개 값을 오가며 진동하거나, 어느 것도 아니거나 매우 다양하다. 심지어 이 패턴은 초기값 [math(a_0)]에 따라 겉잡을 수 없이 변한다. 여기에 매개변수 [math(r)]까지 변화시키면 더욱 기가 막힌 일들이 벌어지는데, [math(r)]이 늘어날수록 진동하는 값의 궤도 개수가 2, 4, 8, 16, ... 2배로 계속 늘어나다가, 어느 지점에선 순간적으로 사라지는데 또 랜덤하게 주기성을 갖는 수열이 튀어나온다던가... 이런 정줄놓은 행동을 더 자세히 보려면 분기도(bifurcation diagram)를 찾아보면 알 수 있다.하여튼 점화식의 관점에서 보자면 고작 변수 하나짜리 이차식에서 이런 카오스가 나오는 것인데, 이걸 보면 3차원까지 가야[3] 카오스가 나오는 미분방정식에 비해서도 더 어렵다고 느껴질 수 있다. 이 카오스의 존재는 일반적인 경우에 점화식을 쉽게 푸는 것이 애시당초 불가능했음을 의미하기도 한다. 그렇다고 점화식의 연구가 의미없는 것은 아닌 게, 이산 동역학계에 대한 이러한 관찰들이 카오스 이론을 새로운 방식으로 확장시켰기 때문이다. 예로 상기한 2차 점화식을 복소수로 넓혀 생각한 망델브로 집합(Mandelbrot set)은 점화식
[math( z_{n+1} = z_n^2 + c )]
이 발산하지 않는 초기값 [math(z_0 \in \mathbb{C})]의 집합으로 정의되는 집합으로, 자기닮음 즉 프랙털의 특성을 갖고 있다. 브누아 망델브로(Benoît B. Mandelbrot, 1924-2010)는 사실상 이 집합을 계기로 프랙털 이론을 창안하였는데, 이 이론은 다른 점화식들의 분기에 대해서도 프랙털 현상을 관찰할 수 있음을 증명해냈고 더욱 나아가선 이산 동역학계와 프랙털과의 근본적 관계성을 시사하기도 했다.
4. 관련 문서
[1]
특수해를 구하는 요령은 f(n)이 상수이면 보통 어떤 상수로 특수해를 추측해 보는 것이고, f(n)이 m차식이면 특수해도 m차식으로 추측해 보는 것이다. 하지만 일반적인 방법은 없다.
[2]
급수가 수렴 안 해도 괜찮냐고 의문을 가질 수 있지만, FM대로라면 생성함수는 이 급수가 수렴하건 안 하건 항상 정의될 수 있다. 동차 선형점화식의 경우는 [math(|a_n| \le K^n )]으로 유계를 주는 것이 가능하므로 급수가 항상 수렴해 통상의
테일러 급수로 생각해도 상관이 없다.
[3]
시간 비이존 상미분방정식에 대해서. 2변수 이하는 푸앵카레-벤딕슨 정리(Poincare-Bendixson theorem)에 의해 카오스가 나오지 않는다.