|
이산수학 Discrete Mathematics |
||
|
{{{#!wiki style="margin:0 -10px -5px;min-height:2em" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin:-6px -1px -11px" |
이론 | |
| 기본 대상 | 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수( 공식) · 순열( 완전순열 · 염주순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도 · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 확률 | 사건 · 가능성 · 확률변수 · 확률분포( 정규분포 · 이항분포 · 푸아송 분포 · 카이제곱분포 · t분포) · 조건부확률 · 기댓값 · 도박사의 오류 · 몬티 홀 문제 · 뷔퐁의 바늘 | |
| 기타 | ||
| P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) | ||
| 관련 문서 | ||
| 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:이론 컴퓨터 과학 | }}}}}}}}} | |
1. 개요
數 列 / sequence자연수 집합(또는 양의 정수 집합)을 정의역으로 갖는 함수. 쉽게 말하자면, 수를 늘어놓고 그것에 순번을 붙이는 것이다. 늘어놓는 규칙은 있어도 되고 없어도 된다.[1] 다만 교육과정에서는 주로 규칙적으로 나열된 수열들을 다룬다. 만약 수열의 정의역이 첫 [math(n)]개의 자연수이면 유한수열이라 하며, ([math(\left<1, 6, 3, 9\right>)], [math(\left<3, 4, 7\right>)] 등), 수열의 정의역이 자연수인 경우 무한수열이라 한다. ([math(\left<1, 2, 3, 4,\ldots\right>)], [math(\left<1, 3, 5, 7,\ldots\right>)] 등).
초등학교 수학에서는 뛰어 세기, 규칙과 대응 등으로 수열을 익히기 위한 첫걸음을 뗀다.
2. 상세
2.1. 정의
수열 [math(a)]이란 정의역이
순서수(ordinal number) [math(\alpha\in \bold{ON})]인 함수를 말한다.
[math(a:\alpha\to S)]
일반적으로 함수를 나타내는 기호는 주로 [math(f,g,h)]를 많이 쓰지만, 수열의 경우 [math(a,b,c)] 등을 주로 사용한다.[math(a:\alpha\to S)]
정의역이 유한 순서수([math(n)] 이하의 자연수의 집합)이면 유한수열, 가산 무한 순서수(자연수 집합)이면 무한수열이라고 하며, 일반적으로 순서수 [math(\alpha)]가 정의역이면 [math(\alpha-)]수열([math(\alpha-)]sequence)라고 한다. 자연수집합 뿐만 아니라, 순서수라면 자신의 원소를 정렬하여 나타낼 수 있기 때문에, 정의역이 비가산 무한 서수일 때도 수열이라고 할 수 있다. 이 문서는 물론 정의역이 가산집합일 때(유한수열과 무한수열) 위주로 작성되었다.
공역에 따라서는 공역이 정수이면 정수열, 유리수면 유리수열, 무리수면 무리수열, 실수면 실수열, 복소수면 복소수열, 점이면 점열 등이라고 하며, 문맥을 통해서 공역이 무엇인지 알 수 있으면 생략하여 그냥 수열이라고 할 수도 있다. 고등학교 교육과정에서 수열이라고 하면 주로 실수열을 뜻한다.
실함수에서 다변수 함수가 있듯 수열에서도 이중수열, 삼중수열 등을 정의할 수 있다.
[math(n)]개의 순서수 [math(\alpha_{1},\cdots,\alpha_{n})]에 대하여, [math(n)]중 수열은 정의역이 [math(\alpha_{1}\times\cdots\times\alpha_{n})]인 함수를 말한다.
[math(a:\alpha_{1}\times\cdots\times\alpha_{n}\to S)]
[math(a:\alpha_{1}\times\cdots\times\alpha_{n}\to S)]
[math(n=2)]이고, [math(\alpha_{1})], [math(\alpha_{2})]가 모두 유한 순서수이면, 함수 [math(A:\alpha_{1}\times\alpha_{2}\to S)]를
행렬이라고 한다. 무슨 말이냐면, [math((i,j)\in\alpha_{1}\times\alpha_{2})]에 대응하는 항을 [math(i)]행 [math(j)]열의 성분으로 적으면 된다.
2.1.1. 일반항
수열의 항은 정의역의 특정한 원소에 대응하는 함수값을 의미한다. 수열의 일반항은 수열의 함수식을 뜻한다. 즉, 정의역의 원소와 그에 대한 함수값의 관계를 식으로 표현한 것이다. 일반적으로 수열의 일반항의 독립변수는 [math(x)]대신 [math(n)], [math(m)], [math(k)], [math(i)], [math(j)], [math(l)] 등을 주로 사용한다. 예를 들어서, 무한수열 [math(a:\mathbb{N}\to\mathbb{R})]의 일반항이 [math(a_{n}=2n-1)]로 주어지면 [math(a)]의 3번째 항은 [math(a_{3}=5)]가 된다.2.1.2. 수열의 표기
수열 [math(a)]의 항이 [math(a_{1},a_{2},a_{3}\ldots)]으로 주어졌을 때, 이를 나열하여 수열 [math(a_{1},a_{2},a_{3},\ldots)]이라고 쓰기도 한다. 혹은 괄호 [math((,))] 또는 [math(\langle, \rangle)]등을 사용하여 [math((a_{1},a_{2},a_{3},\ldots))] 또는 [math(\langle a_1, a_2, \ldots\rangle)]로 나타내기도 한다.수열의 일반항 [math(a_{n})]이 주어지면 [math((a_{n}))], [math(\langle a_{n}\rangle)], [math(\{a_{n}\})] 등으로 나타내기도 하고, 여기에 아랫첨자와 윗첨자를 추가하여 정의역까지 나타내는 표기법도 있다. 예를 들어서 [math((2^{n}-1)_{n=0}^{\infty})]는 일반항이 [math(a_{n}=2^{n}-1)]이고 [math(n=0)]부터 시작하는 무한수열이다.
2.1.3. 부분수열
수열 [math(a:\alpha\to S)]에 대하여, [math(\beta\subseteq\alpha)]인 [math(\beta)]에 대하여, 수열 [math(k:\beta\to\alpha)]가 강한 증가함수라고 하자. 이때 합성함수 [math(a\circ k:\beta\to S)]를 [math(a)]의 부분수열이라 한다. 부분수열이 나오는 유명한 정리로는 '어떤 무한수열의 임의의 무한 부분수열이 [math(L)]로 수렴하면, 그 수열은 [math(L)]로 수렴한다'라는 기초 해석학의 정리가 있다.2.2. 수열의 귀납적 정의
수열의 귀납적 정의 문서 참고.2.3. 생성함수
수열 [math(\{a_n\})]에 대해 생각하는 형식적인 멱급수
[math( \displaystyle A(x) = \sum_{i=0}^{\infty} a_i x^i )]
로 정의된다. 자세한 것은 문서를 참고.2.4. 수열의 합
[math( \displaystyle \sum_{k=1}^{n} a_k =a_1+a_2+a_3+...+a_n)]수학에서의 수열 [math( a_1, a_2, a_3, ... , a_n)]이 주어졌을 때 이들의 합을 시그마 기호로 나타낼 수 있다. 시그마를 쓰는 이유는 합을 뜻하는 라틴어 단어 summa의 앞글자를 땄기 때문이다. 그리스 문자 Σ는 로마자의 S에 대응되기 때문. 때문에 영어권에서는 [math(\Sigma)]라고 쓰고 sum이라고 읽는 경우가 거의 대부분이다. 비슷한 것으로 [math(Pi)](파이)가 있는데, 이것은 곱하기 버전 (곱하기의 영문 표현인 product의 p에 대응).
- 시그마 밑에는 각 항수를 대입할 문자를 지정하고, 더하기를 시작할 첫 항을 지정한다. [math(k)]에 대한 일반항을 제1항부터 더할 것이라면, [math(k=1)]이라고 쓰면 된다. 만약 일반항에 여기서 지정한 문자가 아닌 다른 문자가 들어간다면 그 문자는 상수로 취급한다.(문자를 [math(k)]로 지정했는데 일반항에 [math(m)]이 튀어나온다거나)
- 시그마 위에는 마지막 항을 지정한다. 제[math(n)]항까지 더할 것이라면, [math(n)]이라고 쓰면 된다.
- 시그마 오른쪽에는 일반항을 써준다. 항수가 들어갈 문자는 앞에서 지정한 문자와 같아야 한다. 예를 들어 [math(n)]에 대한 수열에서 일반항이 [math(3n-2)]이고 [math(n)]에 들어가는 수가 항수라면, [math(n)] 대신에 앞에서 지정한 문자 (본 예시에서는 [math(k)])로 바꿔 써야 한다.
시그마의 일반적인 성질은 다음과 같다.
1. [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)] (복호동순)
1. [math( \displaystyle \sum_{k=1}^{n}ca_k = c\sum_{k=1}^{n}a_k)] ([math(c)]는 상수)
1. [math( \displaystyle \sum_{k=1}^{n}c = cn)]
1. [math( \displaystyle \sum_{k=1}^{n}ca_k = c\sum_{k=1}^{n}a_k)] ([math(c)]는 상수)
1. [math( \displaystyle \sum_{k=1}^{n}c = cn)]
어린 시절 산수를 배울 때 1에서 10까지 다 더하면1+2+3+4+5+6+7+8+9+10 =55가 된다는 재미있는 사실을 발견한 적 있을 것이다. 이것이 바로 일종의 유한급수이다. 이를 급수식으로 바꿔 보면
[math( \displaystyle \sum_{k=1}^{10}k)]
이렇게 된다.위의 공식을
[math( \displaystyle \sum^{n}_{k=1}k = \frac{n(n+1)}{2} )]
와 같은 일반적인 식으로 나타낼 수도 있으며 10*(10+1)/2=55가 나오는 것을 확인할 수 있다. 여담으로 이걸 그대로 제곱하면 3차항의 합이 된다.
[math( \displaystyle k^2)]의 경우는 아래와 같다.
[math( \displaystyle \sum^{n}_{k=1}k^2 = \frac{n(n+1)(2n+1)}{6} )]
이를 [math( \displaystyle k^c)]일 경우로 일반화한 식이 바로 파울하버의 공식이다. 자세한 것은 문서 참조.
2015 개정 교육과정에서 수열의 합은 수학1 과목에서 다룬다. 한편 [math(n)]항까지 더하는 것이 아니라 무한 개의 항을 모두 합하는 경우도 생각할 수 있는데, 이는 2015 개정 교육과정의 미적분 과목에서 다루며, 자세한 설명은 무한급수 문서를 참고할 것.
수열의 합을 적분을 이용해 나타낼 수도 있다.
생성함수 [math(A(k))]에 대해서
[math(\displaystyle \sum_{k=1}^{n} A(k) = \int_{1}^{n} A(k) \ \mathrm{d}\lfloor k \rfloor)] ([math(\lfloor k \rfloor)]는 최대 정수 함수)
증명은 급수를 각 항의 합으로 나타낸 뒤 정리해주면 된다. 4번의 경우는 너비가 1이고 높이가 [math(A(k))]인
직사각형을 모아서 그 넓이를 합하는 것을 떠올리면 쉽다.[2][math(\displaystyle \sum_{k=1}^{n} A(k) = \int_{1}^{n} A(k) \ \mathrm{d}\lfloor k \rfloor)] ([math(\lfloor k \rfloor)]는 최대 정수 함수)
자세한 설명을 담은 영상
2.4.1. 여러 수열의 합
다음은 고등학교 과정에서 흔히 나오는 수열의 합의 계산이다.
|
|
|
|
위 식들을 일반화하면 다음과 같으나 각각 [math(m=1)], [math(m=2)]인 경우에 해당하는 위 식들 말고는 계산이 지나치게 복잡하다고 하여 거의 나오지 않는다.
|
|
나아가, [math(\displaystyle\sum_{k=1}^n (\sqrt{k+1}-\sqrt k))]의 경우 다음과 같이 변형된 꼴로도 종종 나온다.
|
2.4.1.1. 부분분수분해
|
위 공식을 이용하여, 변형된 수열의 합을 구하는 문제도 나온다. 다음과 같이 부분분수분해를 이용하여 식을 변형한 뒤 위의 방법대로 수열의 합을 구하면 된다.
- [math(\displaystyle\sum_{k=1}^n \dfrac{3}{k(k+2)}=\displaystyle\sum_{k=1}^n \dfrac32\left(\dfrac1k-\dfrac1{k+2}\right))]
2.5. 수열의 극한
3. 목록
3.1. 등차수열
3.2. 등비수열
3.3. 조화수열
3.4. 계차수열
3.5. 다항수열
다항함수로 정의되는 수열. 수열의 합은 각각의 항에 아래 공식들을 따로따로 적용하여 각 항의 계수를 곱해준다.4차항: [math(1/5n^5+1/2n^4+1/3n^3-1/30n)]
3차항: 등차수열의 합을 제곱하면 된다.
2차항: [math(n(n+1)(2n+1)/6)]
1차항: 등차수열 문서 참고.
상수항: n
3.6. 삼각수열
삼각함수로 정의되는 수열. 수열의 합을 구할 때 항을 몇천 개나 합해야 하는 문제가 나오지만 그건 장식이고 주기가 [math(2{\pi})]임을 이용해서 주기만큼 나눈 나머지에 해당하는 항을 더하면 된다.3.7. 계비수열(?)
사실 계비수열이란 용어는 없다. 그저 자주 쓰이는 표현일 뿐이다.모든 항이 0이 아닌 수열 a에 대하여, n번째 항이 a의 n+1번째 항을 a의 n번째 항으로 나눈 것으로 정의되는 수열 b를 a의 계비수열이라 한다.
3.8. 부분군열
4. 기타
OEIS라는 온라인 사전 사이트가 있는데, 수학/물리학에서 다루는 여러 수열에 대해서 볼 수 있는 사이트이다.5. 관련 문서
- 급수(수학)
- 수학적 귀납법
- 점화식
- 피보나치 수열: 황금비가 나온다.
- 콜라츠 수열: 유명한 3n+1의 문제. 1937년에 나온 수열인데 2021년 기준 아직도 수렴하는지 알려지지 않은 난제중 하나이다.
- 수학Ⅰ(2015)
- OEIS