|
이산수학 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색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
Pascal's triangle
1. 개요
이항계수를 삼각형 모양으로 나열한 것. 블레즈 파스칼이 만13세 때 발견하여 이항계수를 구할 때 사용했다.
삼각형을 그리는 규칙은 다음과 같다.
- 숫자가 들어갈 칸을 첫 번째 줄에는 1개, 두 번째 줄에는 2개, 세 번째 줄에는 3개 이런 식으로 한 줄씩 내려가면 한 칸씩 늘어나게 정삼각형 모양으로 만든다.
- 첫 번째 줄과 두 번째 줄의 3칸에는 1을 쓴다.
- 세 번째 줄부터는 줄의 양쪽 끝 칸에는 1을 쓰고 나머지 칸에는 바로 윗줄에 위치한 칸 중 해당 칸과 인접해 있는 두 칸의 숫자를 더해서 그 값을 쓴다.
다만 차수가 커지면 삼각형을 그리는 것보다 이항정리를 사용하여 직접 구하는 쪽이 좀 더 빠르다. 삼각형을 수학 공식으로 나타내면 아래와 같으며, 이를 파스칼 항등식이라고 한다.
[math(n,r)]가 음이 아닌 정수이고, [math(1\leq r\leq n-1)]일 때, [math(\displaystyle \binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r})].[1]
2. 파스칼 항등식의 증명
2.1. 조합론적 증명
[math(n)]개의 물체에서 [math(r)]개를 고른다 하자. 먼저 [math(n)]개중 1개를 고정, A라 한다. 그럼 구하고자 하는 경우의 수는 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(\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r})].
2.2. 대수적 증명
[math(\displaystyle \binom{n-1}{r-1}+\binom{n-1}{r}=\frac{\left(n-1\right)!}{\left(r-1\right)!\left(n-r\right)!}+\frac{\left(n-1\right)!}{r!\left(n-r-1\right)!}=\frac{\left(n-1\right)!r}{r!\left(n-r\right)!}+\frac{\left(n-1\right)!\left(n-r\right)}{r!\left(n-r\right)!}=\frac{n!}{r!\left(n-r\right)!}=\binom{n}{r})].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부터 대각선 방향으로 쭉 더한 값은 다음 줄의 같은 방향 숫자 옆에 있다.[6]
- 특정한 사선 방향(45도 이하)으로 더하면 피보나치 수가 나온다.[7]
- [math(n)]번째 행의 수들의 합은 [math({2}^{n})]과 같다. 즉 각 행의 수들의 합은 2의 거듭제곱이다.[8]
- 0번째 항에서 1번째를 빼고 다시 2번째를 더하고 3번째를 빼고... 이 과정을 계속하면 0이 나온다. 즉 짝수 번째 항의 합은 홀수 번째 항의 합과 같다.[9]
- [math(n)]번째 행에서 오른쪽부터 [math(r)]번째 항에 [math({10}^{r})]을 곱한 값을 모두 더하면 [math({11}^{n})]이 된다(이항정리로 증명이 가능하다).[10][11]
- [math(n)]행의 수에 차례로 열번호를 곱한 후 다 더하면 [math(n\cdot2^{n-1})]이다.[12]
- v자로 더하면 그 아래에 있는 숫자와 같다.[13]
- [math(n)]행의 수를 모두 제곱하여 더하면 [math(2n-1)]행의 가운데 수가 나온다.
- 어떤 수 주위의 꽃잎처럼 생긴 한 바퀴 돌려 감싸는 6개의 숫자를 번갈아 가며 1칸씩 건너뛴 세 수의 곱은 같다.[14]
- 수를 정점으로 잡고 이웃한 수를 간선으로 서로 이었을 때, 맨 위의 정점에서 특정 정점까지 최단 거리로 갈 수 있는 경우의 수가 바로 그 정점에 나타난다.
4. 파스칼이 처음 발견했는가
파스칼의 삼각형은 파스칼(1623~1662)이 최초로 발견한 것은 아니다. 동양에선 그보다 훨씬 전부터 알려져 있었다. 중국에서는 송나라의 양휘(?1238~?1298)가 2의 6제곱까지, 원나라의 주세걸(1270~1330)이 2의 8제곱까지의 이항계수를 삼각형 모양으로 배열한 그림을 소개하였다. 또한 서양에서도 16~17세기의 많은 수학자들의 저서에 나타난다.파스칼은 스피노자와 함께 서양 근대 철학의 문을 연 프랑스의 철학자이자 확률론을 창시한 수학자이다. 파스칼의 삼각형은 그가 확률 연구 도중 발견한 것이며 이후 파스칼은 이 삼각형의 여러 가지 성질을 발견한 뒤 수삼각형론에 발표했는데, 이런 업적으로 그의 이름이 붙여진 것으로, 발견한 방법론을 어디에 써먹을지 적절한 곳에 적절하게 집어넣는 것 또한 학계에서의 덕목인 것이다.
5. 관련 문서
[1]
행렬이랑 헷갈릴 수 있는데, 세계적으로는
조합을 표현할 때 괄호를 더 많이 쓴다.
[2]
이렇게 하는 이유는 [math(n)]번째 줄의 [math(r)]번째 항의 숫자를 [math(\binom{n}{r})]로 놓기 위해서이다.
[3]
사실 이게 파스칼의 삼각형의 정의이다.
[4]
이 둘을 제외할 때 8번 이상 등장하는 수가 존재하는 지 조차 미해결 문제이다. 1은 무수히 많이 등장하는 수이며, 심지어 9번 이상 등장하는 수는 1을 제외하면 존재하지 않을 것으로 추정되고 있다.
[예시]
5번째 줄:2×5-1=9
[6]
하키스틱 모양처럼 생겨서 하키스틱 패턴이라고 부른다.
[7]
이를 쉽게 보기 위해서는 칸이 참조 링크의 것처럼 칸이 육각형으로 되어있어야 편하다
[8]
[math(\displaystyle \sum_{r=1}^{n}\binom{n}{r}=\sum_{r=1}^{n}\binom{n}{r}1^{n-r}1^{r}=(1+1)^{n}=2^{n})]
[9]
[math(\displaystyle \sum_{r=1}^{n}\binom{n}{r}1^{n-r}(-1)^{r}=(1-1)^{n}=0)]
[10]
[math(\displaystyle \sum_{r=1}^{n}\binom{n}{r}10^{r}=\sum_{r=1}^{n}\binom{n}{r}10^{r}1^{n-r}=(10+1)^n=11^n)]
[11]
이를 이용하여 [math(11^{n})]을 쉽게 계산할 수 있다. 예를 들어 [math(11^{4})]의 경우 파스칼 삼각형의 4번째 줄에 있는 1,4,6,4,1을 그대로 붙여 만든 14641이 된다.
[12]
[math(\displaystyle \frac{d}{dx}x^{n}=\sum_{r=1}^{n}\binom{n}{r}1^{n-r}\frac{d}{dx}(x-1)^{r}=\sum_{r=1}^{n}(r-1)\binom{n}{r}1^{n-r}(x-1)^{r-1}=n\cdot x^{n-1})]에서 [math(x=2)] 대입
[13]
예를 들어 1+3+6+6+3+1=20
[14]
예를 들어 3 주위의 수를 곱하여 2×1×6=1×3×4라는 등식을 얻을 수 있다.