[include(틀:이산수학·수리논리학)] [목차] Pascal's triangle == 개요 == [[파일:external/upload.wikimedia.org/1280px-Pascal%27s_triangle_5.svg.png|width=30%]] [[이항정리|이항계수]]를 삼각형 모양으로 나열한 것. [[블레즈 파스칼]]이 '''13살''' 때 발견하여 이항계수를 구할 때 써먹었다. 삼각형을 그리는 규칙은 다음과 같다. 1. 숫자가 들어갈 칸을 첫 번째 줄에는 1개, 두 번째 줄에는 2개, 세 번째 줄에는 3개 이런 식으로 한 줄씩 내려가면 한 칸씩 늘어나게 정삼각형 모양으로 만든다. 1. 첫 번째 줄과 두 번째 줄의 3칸에는 1을 쓴다. 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})][* [[행렬]]이랑 헷갈릴 수 있는데, 세계적으로는 [[조합]]을 표현할 때 괄호를 더 많이 쓴다.] == 파스칼 항등식의 증명 == === 조합론적 증명 === [math(n)]개의 물체에서 [math(r)]개를 고른다하자. 먼저 [math(n)]개중 1개를 고정시킨다. 그럼 구하고자하는 [[경우의 수]]는 그 1개가 포함되는 경우와 포함되지 않는 경우 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})]. === 대수적 증명 === [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})] == 여러가지 성질 == [include(틀:상세 내용, 문서명=이항계수)] 맨 처음 줄을 0번째 줄이라고 정의한다. 1. 같은 줄의 연속된 두 수를 더한 값은 아랫줄의 더한 두 수 사이에 있다.[* 사실 이게 파스칼의 삼각형의 정의이다.] 1. [math({(a+b)}^{n})]을 전개한 각 항의 계수는 숫자들이 나온 순서대로다. 1. 짝수행은 항의 개수가 짝수개이고, 좌우대칭이며 홀수행은 항의 개수가 홀수개이고, 가운데 숫자를 중심으로 좌우대칭이다. 1. 파스칼 삼각형에서 '2'는 딱 한 번 나온다. 1. 파스칼의 삼각형에서 2,4,6번 등장하는 수는 무수히 많다. 반면 8번 이상 등장하는 수는 1, 3003외에 알려진 바가 없다.[* 이 둘을 제외할 때 8번 이상 등장하는 수가 존재하는 지 조차 미해결 문제이다.] 1. [math(p)]가 소수이면 [math(p)]행의 수는 양 끝의 1을 제외하고 [math(p)]의 배수이다. 1. [math(n)]번째 줄까지의 1의 개수는 [math(2n+1)]개이다.[* 5번째 줄:2×5+1=11] 1. 홀수만 음영 처리하면 [[시어핀스키 삼각형]]이다. 1. 모서리의 1부터 대각선 방향으로 쭉 더한 값은 다음 줄의 같은 방향 숫자 옆에 있다 (하키스틱 모양처럼 생겨서 하키스틱 패턴이라고 부른다). 1. 특정한 사선 방향(45도 이하)으로 더하면 [[피보나치 수열|피보나치 수]]가 나온다. (이를 쉽게 보기 위해서는 칸이 참조 링크의 것처럼 칸이 육각형으로 되어있어야 편하다) 1. [math(n)]번째 행의 수들의 합은 [math({2}^{n})]과 같다. 즉 각 행의 수들의 합은 2의 거듭제곱이다.[* [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})]] 1. 첫 번째 항에서 두 번째를 빼고 다시 세 번째를 더하고 네 번째를 빼고... 이 과정을 계속하면 0이 나온다. 즉 짝수 번째 항의 합은 홀수 번째 항의 합과 같다. [* [math(\displaystyle \sum_{r=1}^{n}\binom{n}{r}1^{n-r}(-1)^{r}=(1-1)^{n}=0)]] 1. [math(n)]번째 행에서 오른쪽부터 [math(r)]번째 항에 [math({10}^{r-1})]을 곱한 값을 모두 더하면 [math({11}^{n})]이 된다(이항정리로 증명이 가능하다)[* [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)]][* 이를 이용하여 [math(11^{n})]을 쉽게 계산할 수 있다. 예를 들어 [math(11^{4})]의 경우 파스칼 삼각형의 4번째 줄에 있는 1,4,6,4,1을 그대로 붙여 만든 14641이 된다.] 1. [math(n)]행의 수에 차례로 열번호에서 1을 뺀 값을 곱한 후 다 더하면 [math(n\cdot2^{n-1})]이다. [* [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)] 대입] 1. v자로 더하면 그 아래에 있는 숫자와 같다.[* 예를 들어 1+3+6+6+3+1=20] 1. [math(n)]행의 수를 모두 제곱하여 더하면 [math(2n-1)]행의 가운데 수가 나온다. 1. 어떤 수 주위의 6개의 숫자를 번갈아 가며 3개씩 곱한 값은 같다.[* 예를 들어 3 주위의 수를 곱하여 2x1x6=1x3x4라는 등식을 얻을 수 있다.] [[http://insigsaem.tistory.com/1|참조]] == 파스칼이 처음 발견했는가 == 파스칼의 삼각형은 파스칼(1623~1662)이 최초로 발견한 것은 아니다. 동양에선 그보다 훨씬 전부터 알려져 있었다. 중국에서는 송나라의 [[양휘]](?1238~?1298)가 2의 6제곱까지, 원나라의 [[주세걸]](1270~1330)이 2의 8제곱까지의 이항계수를 삼각형 모양으로 배열한 그림을 소개하였다. 또한 서양에서도 16~17세기의 많은 수학자들의 저서에 나타난다. 뿐만 아니라 조선의 수학자 [[홍정하]]는 파스칼 삼각형을 단순히 발견한 것을 넘어 시대를 뛰어넘는 통찰을 한 것으로 알려져 있다. 현대 조합론의 측면에서 보아도 홍정하의 통찰은 가히 천재적이며 '''이산수학이 어느 나라보다도 발달했던 조선의 수학적 성과'''를 엿볼 수 있다. 여담으로, 미적분학은 영국 등지에서 발달하였으나 미적분학과 대등한 위치에 있는 수학분야인 [[이산수학]]은 동양, 특히 조선에서 발달하였다. 미적분학은 증기기관, 열기관 등에 산업적으로 응용되어 산업혁명이 일어나기까지 100여 년의 시간이 걸렸지만 영국의 경우 정부 차원에서 연구 지원을 이어갈 수 있었기에 산업혁명의 발생지가 될 수 있었지만, 조선은 학문의 산업적 발전이 식민지배 등으로 퇴보하였으며 그러한 학문적 성과도 현재에 이르러서도 과소평가되고 있는 실정이다. 이산수학은 인공지능의 핵심 이론적 기반으로서 4차 산업혁명 시대 그 산업적 활용이 비약적으로 진행되고 있는 수학 분야이다. 파스칼은 스피노자와 함께 서양 근대 철학의 문을 연 프랑스의 철학자이자 확률론을 창시한 수학자이다. 파스칼의 삼각형은 그가 확률 연구 도중 발견한 것이며 이후 파스칼은 이 삼각형의 여러 가지 성질을 발견한 뒤 수삼각형론에 발표했는데, 이런 업적으로 그의 이름이 붙여진 것으로, 발견한 방법론을 어디에 써먹을지 '''적절한 곳에 적절하게 집어넣는 것''' 또한 학계에서의 덕목인 것이다. == 관련 항목 == * [[조합]] * [[이항정리]] * [[프랙탈 이론]] [[분류:이산수학]]