| 이산수학 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. 개요
Pascal's triangle| |
삼각형을 그리는 규칙은 다음과 같다.
- 수가 들어갈 칸을 첫 번째 줄에는 1개, 두 번째 줄에는 2개, 세 번째 줄에는 3개 이런 식으로 한 줄씩 내려가면 한 칸씩 늘어나게 정삼각형 모양으로 만든다.
- 첫 번째 줄과 두 번째 줄의 3칸에는 1을 쓴다.
- 세 번째 줄부터는 줄의 양쪽 끝 칸에는 1을 쓰고 나머지 칸에는 바로 윗줄에 위치한 칸 중 해당 칸과 인접해 있는 두 칸의 수를 더해서 그 값을 쓴다.
다만, 차수가 커지면 삼각형을 그려서 구하는 것보다 이항정리를 사용하여 직접 구하는 것이 좀 더 빠르다. 파스칼의 삼각형을 수식으로 나타내면 아래와 같으며, 이를 파스칼 항등식이라고 한다.
| [math(n)], [math(r)]이 [math(0)] 이상의 정수이고 [math(1\le r\le n-1)]일 때 |
2. 파스칼 항등식의 증명
2.1. 조합론적 증명
[math(n)]개의 물체에서 [math(r)]개를 고른다고 하자. 먼저 [math(n)]개 중 1개를 고정하고 이를 [math(A)]라 한다. 그럼 구하고자 하는 경우의 수는 [math(A)]가 포함되는 경우와 포함되지 않는 경우 이렇게 2가지로 나눌 수 있다.전자의 경우, 나머지 [math(n-1)]개 중 [math(r-1)]개를 고르면 되므로 가짓수는 [math(\binom{n-1}{r-1})]이다. 후자의 경우 나머지 [math(n-1)]개 중 [math(r)]개를 고르면 되므로 가짓수는 [math(\binom{n-1}r)]이다. 확률의 합의 법칙에 의해 총 가짓수는 다음과 같다.
[math(
\dbinom nr \!= \!\dbinom{n-1}{r-1} \!+\!\dbinom{n-1}r
)]
2.2. 대수적 증명
| [math(\displaystyle \begin{aligned} \binom{n-1}{r-1} \!+\!\binom{n-1}r \!&= \frac{(n-1)!}{(r-1)!\,(n-r)!} +\frac{(n-1)!}{r!\,(n-r-1)!} \\ &= \frac{(n-1)!\cdot r}{r!\,(n-r)!} +\frac{(n-1)!\cdot(n-r)}{r!\,(n-r)!} \\ &= \frac{n!}{r!\,(n-r)!} \\ &= \!\binom nr \end{aligned} )] |
3. 여러 가지 성질
맨 윗 줄을 0번째 줄(행), 각 줄의 맨 왼쪽 항을 0번째 항이라고 정의하자.[2]
- 같은 줄의 이웃한 두 수를 더한 값은 아랫줄의 더한 두 수 사이에 있다.[3] 이미지
- [math((a+b)^n)]을 전개한 각 항의 계수는 수들이 나온 순서대로다.
- 홀수행은 항의 개수가 짝수개이고, 가운데의 두 수의 경계선을 중심으로 좌우대칭이며, 짝수행은 항의 개수가 홀수개이고, 가운데 수를 중심으로 좌우대칭이다. 이미지
- 파스칼 삼각형에서 딱 '한 번' 나오는 정수는 2가 유일하다.
- 파스칼의 삼각형에서 2, 4, 6번 등장하는 수는 무수히 많다는 것이 증명되었으며 3, 5, 7번 등장하는 수는 각각 몇 개인지 알려지지 않았다. 반면 8번 이상 등장하는 수는 1, 3003 외에 알려진 바가 없다.[4]
- [math(p)]가 소수라면, [math(p)]번째 행에 놓여있는 수는 양 끝의 1을 제외하고 전부 [math(p)]의 배수이다.
- [math(n)]번째 줄까지의 1의 개수는 [math(2n-1)]개이다.[예시]
- 홀수만 음영 처리하면 시어핀스키 삼각형 모양이 나타난다. 이미지
- 모서리의 1부터 대각선 방향으로 쭉 더한 값은 다음 줄의 같은 방향 수 옆에 있다. 하키스틱 모양처럼 생겨서 '하키스틱 패턴'이라고 부른다. 이미지
- 특정한 사선 방향(45도 이하)으로 더하면 피보나치 수가 나온다. 이미지
- [math(n)]번째 행의 수들의 합은 [math(2^n)]과 같다. 즉, 각 행의 수들의 합은 2의 거듭제곱이다.[6]
- [math(n)]번째 행에서, 0번째 항에 1번째 항을 빼고 2번째 항을 더하고 3번째 항을 빼고... 이 과정을 계속하면 [math(0)]이 나온다. 즉, 짝수 번째 항의 합은 홀수 번째 항의 합과 같다.[7]
- [math(n)]번째 행에서, 오른쪽부터 [math(r)]번째 항에 [math({10}^r)]을 곱한 값을 모두 더하면 [math({11}^n)]이 된다. 이항정리로 증명 가능하다.[8][9]
- [math(n)]행의 각 수에 차례로 열번호를 곱한 후 다 더하면 [math(n\cdot2^{n-1})]이다.[10]
- [math(n)]행의 수를 모두 제곱하여 더하면 [math(2n-1)]행의 가운데 수가 나온다.
- 어떤 수 주위의 꽃잎처럼 생긴 한 바퀴 돌려 감싸는 6개의 수를 번갈아 가며 1칸씩 건너뛴 세 수의 곱은 같다.[11] 이미지
- 수를 정점으로 잡고 이웃한 수를 간선으로 서로 이었을 때, 맨 위의 정점에서 특정 정점까지 최단 거리로 갈 수 있는 경우의 수가 바로 그 정점에 나타난다.
4. 파스칼이 처음 발견했는가
파스칼의 삼각형은 파스칼(1623~1662)이 최초로 발견한 것은 아니다. 동양에선 그보다 훨씬 전부터 알려져 있었다. 중국에서는 송나라의 양휘(?1238~?1298)가 26까지, 원나라의 주세걸(1249~1314)이 28까지의 이항계수를 삼각형 모양으로 배열한 그림을 소개하였다. 또한 서양에서도 16~17세기의 많은 수학자들의 저서에 나타난다.파스칼은 바뤼흐 스피노자와 함께 서양 근대 철학의 문을 연 프랑스의 철학자이자 확률론을 창시한 수학자이다. 파스칼의 삼각형은 그가 확률 연구 도중 발견한 것이며, 이후 파스칼은 이 삼각형의 여러 가지 성질을 발견한 뒤 책 '수삼각형론(Traite du Triangle Arithmetique)'에 발표했다. 파스칼의 삼각형은 파스칼의 바로 이런 업적으로 그의 이름이 붙여진 것이다. 발견한 방법론을 어디에 써먹을지 적절한 곳에 적절하게 집어넣는 것 또한 학계에서의 덕목인 것이다.
5. 관련 문서
[1] 행렬이랑 헷갈릴 수 있는데, 세계적으로는 조합을 표현할 때 [math({}_n{\rm C}_r)] 대신 소괄호를 사용한 [math(\binom nr)]을 더 많이 쓴다.[2] 이렇게 하는 이유는 [math(n)]번째 줄의 [math(r)]번째 항의 수를 [math(\binom nr)]로 놓기 위해서이다.[3] 사실 이게 파스칼의 삼각형의 정의이다.[4] 1과 3003을 제외하면 여덟 번 이상 등장하는 수가 존재하는지조차 미해결 문제이다. 1은 무수히 많이 등장하는 수이며, 심지어 아홉 번 이상 등장하는 수는 1을 제외하면 존재하지 않을 것으로 추정되고 있다.[예시] 5번째 줄: [math(2\times5-1=9)][6] [math(\displaystyle \sum_{r=1}^n \!\binom nr \!= \sum_{r=1}^n \!\binom nr 1^{n-r} 1^r = (1+1)^n = 2^n)][7] [math(\displaystyle \sum_{r=1}^n \!\binom nr 1^{n-r} (-1)^r = (1-1)^n = 0)][8] [math(\displaystyle \sum_{r=1}^n \!\binom nr 10^r = \sum_{r=1}^n \!\binom nr 10^r 1^{n-r} = (10+1)^n = 11^n)][9] 이를 이용하여 [math(11^n)]을 쉽게 계산할 수 있다. 예를 들어 [math(11^4)]의 경우, 파스칼 삼각형의 4번째 줄에 있는 1, 4, 6, 4, 1을 그대로 붙여 만든 14641이 된다. 다만, 수가 두 자릿수를 넘어가는 경우는 자릿수 올림 처리를 해야 한다. 예를 들어 [math(11^5)]의 경우, 파스칼 삼각형의 5번째 줄에 있는 수들은 1, 5, 10, 10, 5, 1이지만 자릿수 올림 처리를 하면 1, 5+1=6, 0+1=1, 0, 5, 1이 되고, 이를 이어 붙이면 161051이다.[10] [math(\displaystyle \frac{\rm d}{{\rm d}x} x^n = \sum_{r=1}^n \!\binom nr 1^{n-r} \frac{\rm d}{{\rm d}x} (x-1)^r = \sum_{r=1}^n (r-1) \binom nr 1^{n-r} (x-1)^{r-1} = n\cdot x^{n-1})]에 [math(x=2)] 대입[11] 예를 들어 3 주위의 수를 곱하여 2×1×6=1×3×4라는 등식을 얻을 수 있다.