[include(틀:이산수학)] [목차] Pascal's triangle == 개요 == [[파일:external/upload.wikimedia.org/1280px-Pascal%27s_triangle_5.svg.png|width=30%&bgcolor=#fff]] [[이항정리|이항계수]]를 삼각형 모양으로 나열한 것. [[블레즈 파스칼]]이 '''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개를 고정, 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})]. === 대수적 증명 === [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번째 줄, 각 줄의 맨 왼쪽 항을 0번째 항이라고 정의한다.[* 이렇게 하는 이유는 [math(n)]번째 줄의 [math(r)]번째 항의 숫자를 [math(\binom{n}{r})]로 놓기 위해서이다.] 1. 같은 줄의 연속된 두 수를 더한 값은 아랫줄의 더한 두 수 사이에 있다.[* 사실 이게 파스칼의 삼각형의 정의이다.] 1. [math({(a+b)}^{n})]을 전개한 각 항의 계수는 숫자들이 나온 순서대로다. 1. 짝수행은 항의 개수가 짝수개이고, 가운데의 두 숫자의 경계선을 중심으로 좌우대칭이며 홀수행은 항의 개수가 홀수개이고, 가운데 숫자를 중심으로 좌우대칭이다. 1. 파스칼 삼각형에서 딱 '한 번' 나오는 정수는 2가 유일하다. 1. 파스칼의 삼각형에서 2, 4, 6번 등장하는 수는 무수히 많다는 것이 증명되었으며 3, 5, 7번 등장하는 수는 각각 몇 개인지 알려지지 않았다. 반면 8번 이상 등장하는 수는 1, 3003외에 알려진 바가 없다.[* 이 둘을 제외할 때 8번 이상 등장하는 수가 존재하는 지 조차 미해결 문제이다. 1은 무수히 많이 등장하는 수이며, 심지어 9번 이상 등장하는 수는 1을 제외하면 존재하지 않을 것으로 추정되고 있다.] 1. [math(p)]가 소수인 경우 [math(p)]번째 행에 놓여있는 수는 양 끝의 1을 제외하고 전부 [math(p)]의 배수이다. 1. [math(n)]번째 줄까지의 1의 개수는 [math(2n-1)]개이다.[*예시 5번째 줄:2×5-1=9] 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번째 항에서 1번째를 빼고 다시 2번째를 더하고 3번째를 빼고... 이 과정을 계속하면 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})]을 곱한 값을 모두 더하면 [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)]행의 수에 차례로 열번호를 곱한 후 다 더하면 [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개의 숫자를 번갈아 가며 1칸씩 건너뛴 세 수의 곱은 같다.[* 예를 들어 3 주위의 수를 곱하여 2×1×6=1×3×4라는 등식을 얻을 수 있다.] 1. 맨 왼쪽이나 맨 오른쪽에서 3번째 줄에 있는 수는 첫째항이 1이고 공차가 1인 [[등차수열]]의 합으로 나타내어진다. 1. 같은 줄에 있는 모든 수를 더하면 2의 거듭제곱이 된다[* n번째 줄에 있는 모든 수의 합은 2^(n-1)이 된다] == 파스칼이 처음 발견했는가 == 파스칼의 삼각형은 파스칼(1623~1662)이 최초로 발견한 것은 아니다. 동양에선 그보다 훨씬 전부터 알려져 있었다. 중국에서는 송나라의 [[양휘]](?1238~?1298)가 2의 6제곱까지, 원나라의 [[주세걸]](1270~1330)이 2의 8제곱까지의 이항계수를 삼각형 모양으로 배열한 그림을 소개하였다. 또한 서양에서도 16~17세기의 많은 수학자들의 저서에 나타난다. 파스칼은 스피노자와 함께 서양 근대 철학의 문을 연 프랑스의 철학자이자 확률론을 창시한 수학자이다. 파스칼의 삼각형은 그가 확률 연구 도중 발견한 것이며 이후 파스칼은 이 삼각형의 여러 가지 성질을 발견한 뒤 수삼각형론에 발표했는데, 이런 업적으로 그의 이름이 붙여진 것으로, 발견한 방법론을 어디에 써먹을지 '''적절한 곳에 적절하게 집어넣는 것''' 또한 학계에서의 덕목인 것이다. == 관련 문서 == * [[조합]] * [[이항정리]] * [[프랙털 이론]] [[분류:이산수학]][[분류:삼각형]][[분류:블레즈 파스칼]]