|
이산수학 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색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
- 수 열(number sequence), 곧 공역이 수인 열에 대해 다룹니다.
1. 수열의 일반항 정의
다음은 두 가지의 수열을 나타낸 것이다.- [math(1 \quad 3 \quad 5 \quad 7 \quad 9\quad 11\quad\cdots)]
- [math(1 \quad 2 \quad 4 \quad 8 \quad 16\quad 32\quad\cdots)]
수열을 이루는 각 수를 항이라고 한다. 예를 들어 [math(n)]번째 수는 제[math(n)]항인 것이다. 수열을 나타낼 때는 [math(\{a_{n}\})]과 같이 나타낸다. [math(a)]는 수열을 명명하는 문자이며, [math(a_{n})] 자체는 수열 [math(\{a_{n}\})]의 [math(n)]번째 항을 나타내며, 일반항이라 한다.
예를 들어 수열 [math(\{n^2-1\})]은
| [math(\begin{aligned} 0\quad3\quad8\quad15\quad24\quad 35 \quad \cdots \end{aligned})] |
2. 주요한 수열들
- 등차수열: 이웃하는 항의 차(공차)가 일정한 수열. 즉, 항의 값이 일차함수와 같이 선형적인 수열
- 등비수열: 이웃하는 항의 비(공비)가 일정한 수열. 즉, 항의 값이 지수함수와 같이 지수적인 수열
- 조화수열: 각 항의 역수가 등차수열인 수열
- 계차수열: 어떤 수열의 이웃한 항 사이의 차로 구성된 수열
- 특정 함수로 정의되는 수열
- 다항수열: 다항함수로 정의되는 수열. 수열의 합은 각각의 항에 거듭제곱의 합 공식을 따로따로 적용하여 각 항의 계수를 곱해준다. 정적분과 원리가 다소 비슷하다.
- 삼각수열: 삼각함수로 정의되는 수열. 수열의 합을 구할 때 항을 몇천 개나 합해야 하는 문제가 나오지만 그건 장식이고 주기가 [math(2{\pi})]임을 이용해서 주기만큼 나눈 나머지에 해당하는 항을 더하면 된다.
- 부분군열
- 피보나치 수열: 가장 단순한 이계 동차 선형점화식을 따르는 수열로, 일반항에 황금비가 등장한다.
-
콜라츠 수열: 유명한
[math(3n+1)]의 문제. 1937년에 나온 수열인데 2024년 기준으로 아직도 수렴하는지 알려지지 않은 난제 중 하나이다.
3. 수열의 귀납적 정의
4. 수열의 합
이제 수열 [math(\{a_{n} \})]의 [math(n)]항까지의 합을 생각할 수 있고, 그것을 기호로| [math(\begin{aligned} \sum_{k=1}^{n} a_{k} =a_{1}+a_{2}+a_{3}+ \cdots +a_{n} \end{aligned})] |
- 합의 기호 밑에는 각 항수를 대입할 문자(index)를 지정하고, 더하기를 시작할 첫 항을 지정한다. [math(k)]에 대한 일반항을 첫째 항부터 더할 것이라면, [math(k=1)]이라고 쓰면 된다. 만약 일반항에 여기서 지정한 문자가 아닌 다른 문자가 들어간다면 그 문자는 상수로 취급한다.
- 합의 기호 위에는 마지막 항을 지정한다. 제[math(n)]항까지 더할 것이라면, [math(n)]이라고 쓰면 된다.
- 합의 기호 오른쪽에는 일반항을 써준다. 항수가 들어갈 문자는 앞에서 지정한 문자와 같아야 한다. 예를 들어 [math(n)]에 대한 수열에서 일반항이 [math(3n-2)]이고 [math(n)]에 들어가는 수가 항수라면, [math(n)] 대신에 앞에서 지정한 문자로 바꿔 써야 한다.
합의 기호에 대한 일반적인 성질은 다음과 같다.
- [math( \displaystyle \sum_{k=1}^{n}\left(a_k \pm b_k\right) = \sum_{k=1}^{n}a_k \pm \sum_{k=1}^{n}b_k)] (복부호동순)
- [math( \displaystyle \sum_{k=1}^{n}ca_k = c\sum_{k=1}^{n}a_k)] (단, [math(c)]는 상수)
- [math( \displaystyle \sum_{k=1}^{n}c = cn)][1]
위를 종합하여 1부터 100까지의 합은 다음과 같이 나타낼 수 있을 것이다.
| [math(\begin{aligned} \sum_{k=1}^{100} k=5050 \end{aligned})] |
또한, 첫째 항부터 [math(n)]번째 항까지의 합을 [math(S_{n})]이라 한다면,
| [math(\begin{aligned} S_{n}-S_{n-1}=a_{n} \end{aligned})] |
4.1. 자연수 거듭제곱 꼴의 합
다음은 외워두면 편리하다.- [math(\displaystyle \sum_{k=1}^{n} k =\dfrac{n(n+1)}{2})]
- [math(\displaystyle\sum_{k=1}^{n} k^2 =\dfrac{n(n+1)(2n+1)}{6})]
- [math(\displaystyle\sum_{k=1}^{n} k^3 =\biggl\{ \dfrac{n(n+1)}{2} \biggr\}^{2})]
위를 이용하여 홀수의 제곱의 합을 구해보자. 홀수는 [math((2n-1))]로 나타낼 수 있으므로 다음과 같다.
| [math(\begin{aligned}\displaystyle \sum_{k=1}^{n} (2k-1)^{2}&=\sum_{k=1}^{n} (4k^2-4k+1) \\ &=4\sum_{k=1}^{n}k^2-4\sum_{k=1}^{n}k+\sum_{k=1}^{n} 1 \\&= 4 \cdot \frac{n(n+1)(2n+1)}{6}+4\cdot \frac{n(n+1)}{2}+n \\ &=\frac{n(4n^2-1)}{3} \end{aligned})] |
4.2. 무리식과 유리식에 대한 합
- 무리식 관련
- 분수꼴로 된 무리식과 관련한 수열의 합을 구할 때는 유리화를 사용한다.
| [math(\begin{aligned}\displaystyle \sum_{k=1}^{n} \dfrac{1}{\sqrt{k}+\sqrt{k+1}}&=\sum_{k=1}^{n} \dfrac{\sqrt{k}-\sqrt{k+1}}{(\sqrt{k}+\sqrt{k+1})(\sqrt{k}-\sqrt{k+1})} \\ &=-\sum_{k=1}^{n}(\sqrt{k}-\sqrt{k+1}) \\&=-(1-\sqrt{2}+\sqrt{2}-\sqrt{3}+\sqrt{3}-\cdots+\sqrt{n}-\sqrt{n+1}) \\ &=\sqrt{n+1}-1 \end{aligned})] |
- 유리식 관련
-
유리식과 관련한 수열의 합을 구할 때는
부분분수 분해
[math(\dfrac{1}{AB}=\dfrac{1}{B-A} \biggl(\dfrac{1}{A}-\dfrac{1}{B} \biggr)\quad)] (단, [math(A \neq 0)], [math(AB \neq 0)])
을 이용한다.
[math(\begin{aligned}\displaystyle \sum_{k=1}^{n} \frac{1}{k(k+1)} &= \sum_{k=1}^{n} \biggl( \frac{1}{k}-\frac{1}{k+1} \biggr) \\&=1-\frac{1}{2}+\frac{1}{2}-\frac{1}{3}+\frac{1}{3}-\cdots+\frac{1}{n}-\frac{1}{n+1} \\&=\frac{n}{n+1} \end{aligned})]
또한 다음을 참고한다.
| [math(\begin{aligned}\displaystyle \sum_{k=1}^{n} (\sqrt{k+m}-\sqrt{k})&=\sum_{k=1}^{m}(\sqrt{n+k}-\sqrt{k}) &&\quad (n \geq m) \\ \sum_{k=1}^{n} \biggl(\frac{1}{k}-\frac{1}{k+m} \biggr)&= \sum_{k=1}^{m} \biggl(\frac{1}{k}-\frac{1}{k+n} \biggr) &&\quad (n \geq m)\end{aligned})] |
5. 수열의 곱
수열의 합을 [math(\Sigma)]로 나타냈듯이 곱도 [math(\Pi)]로 나타낼 수 있다.| [math(\begin{aligned} \prod_{k=1}^{n}a_{k}=a_{1}a_{2}a_{3} \cdots a_{n} \end{aligned})] |
6. 생성함수
수열 [math(\{a_n\})]에 대해 생각하는 형식적인 멱급수
| [math(\begin{aligned} \displaystyle A(x) = \sum_{i=0}^{\infty} a_i x^i \end{aligned})] |
생성함수로 수열의 합을 계산할 수 있다.
| [math(\displaystyle \sum_{k=1}^{n} A(k) = \int_{1}^{n} A(k) \ \mathrm{d}\lfloor k \rfloor \quad)] (단, [math(\lfloor k \rfloor)]는 최대 정수 함수) |
7. 수열의 극한
8. 기타
9. 관련 문서
[1]
[math(c)]가 아님에 유의