확률과 통계/1. 경우의 수 Show by bigpicture 2019. 8. 10. [확률과통계]-[1.경우의 수]-[②이항정리]-[(13)파스칼의 삼각형] 파스칼의 삼각형 지난 강의에서 유도한 이항계수는 아래와 같습니다. 이항계수들을 아래와 같이 나열해 봅시다. 위에 보시는 삼각형을 파스칼의 삼각형이라고 합니다. 파스칼의 삼각형의 몇가지 특징을 살펴봅시다. 1) 먼저 각 줄은 n에 1부터 하나씩 늘려간 이항계수들입니다. 2) 파스칼의 삼각형에서 연속한 두 항을 더하면, 그 두항의 가운데 아랫항과 같습니다. 일반화 시키면 아래 등식입니다. 위 성질은 조합을 공부할 때도 나왔던 내용입니다. 3) 파스칼의 삼각형에서 각 행의 수를 더하면 2의 제곱수가 됩니다. 1번성질을 이용하면 됩니다. 이항계수의 합은 a와 b에 1을 넣으면 구해지는 값입니다. 따라서 2의 제곱수가 됩니다. 4) 하키스틱 패턴 모서리에 있는 값으로 출발하여 대각선 방향으로 더한 값이, 꺾여서 있는 값과 동일합니다. 하키채 모양이어서 하키스틱패턴이라고 부릅니다.
DongJoon 2018-07-24 프랙털 시뮬레이션 파스칼의 삼각형은 수학에서 이항계수(서로 다른 몇 개의 물건 중에서 순서없이 물건을 선택할 수 있는 경우의 수)를 삼각형 모양의 기하학적 형태로 배열한 것입니다. 위쪽의 양쪽 사선 방향에서 내려받은 숫자를 서로 더하면 파스칼의 삼각형이 만들어 집니다. 파스칼의 삼각형 특징시에르핀스키 삼각형 Sierpinski Curve2의 배수에 해당되는 숫자를 다른 색으로 칠해보면, 같은 모양이 되풀이 되는 것을 알 수 있습니다. 모양을 자세히 보면 부분과 전체가 서로 닮아 있습니다. 부분들의 모습이 되풀이 되어 전체모습이 된다는 것은 프랙탈의 기본 원리에 해당됩니다. 안녕하세요. 이번에는 조합을 이용한 점화식과, 그 점화식을 응용하여 만들어진 파스칼의 삼각형에 대해 알아보겠습니다. 지난번에 조합 공식을 알아봤는데요, 이 조합도 순열처럼 점화식 표현이 가능하지 않을까요? 그렇습니다. nCr을 생각해 보겠습니다. n개의 서로 다른 공들이 1번부터 n번까지 쭈욱 나열되어 있다고 합시다. 여기서 우리는 다음 두 가지 경우를 생각해 볼 수 있습니다. 이 공들 중 r개를 택하는데, 1) 1번 공이 택해지는 경우 이 경우는, 1번 공을 제외한 나머지 n-1개의 공 중에서 r-1개를 택하면 됩니다. 즉 (n-1)C(r-1) 입니다. 2) 1번 공이 택해지지 않는 경우 이 경우, 1번을 제외한 n-1개에서 r개를 택해야 합니다. 즉 (n-1)Cr 입니다. 1)과 2)를 더하면 전체 경우인 nCr이 된다는 사실은 자명합니다.(그렇죠?) 즉 nCr = (n-1)C(r-1) + (n-1)Cr 입니다! 여기에 몇 가지 조건을 추가하면 모든 nCr들을 귀납적인 방법으로 구해나갈 수 있습니다. 그 조건은, nC0=1, nCn=1 이라는 조건입니다. 그러면 조합은 다음과 같이 표현됩니다. nC0=nCn=1, nCr=(n-1)C(r-1)+(n-1)Cr 자, 그런데 이 식을 잘 보세요. 혹시 알아차리신 분이 있을까요? 파스칼의 삼각형을 그려나가는 방법과 매우 유사하지 않나요? 파스칼의 삼각형은 다음과 같이 그립니다. 1) 위에서 n번째 줄에는 n개의 수가 쓰여진다. 2) n개의 수 중 처음과 마지막은 1이다. 3) n개의 수 중 r번째 수에는 바로 위 n-1번째 줄의 r-1번째 수와 r번째 수를 더한 값을 쓴다. 이제 보이시나요? 분명히, 분명히 둘은 매우 유사합니다!! 아니, 어쩌면 유사한 것에서 그치지 않고 혹시 파스칼의 삼각형이 '조합'을 의미하는 것은 아닐까요? 네, 그렇습니다. 실제로 파스칼의 삼각형은 다음입니다. 그런데 이를 다음과 같이 쓸 수 있습니다. 놀랍도록 정확히 일치합니다! 이것이 사실 바로 파스칼 삼각형의 비밀입니다! 파스칼의 삼각형은 결국 조합으로 이루어졌고, n번째 줄의 r번째 수는 (n-1)C(r-1) 인 것입니다! 무슨 의미일까요? 파스칼의 삼각형에 대해 연구하면 조합에 대해 잘 알 수 있게 되고, 또 조합에 대해 연구하면 파스칼의 삼각형을 더욱 잘 이해할 수 있게 되는 것입니다! 이것이 바로 파스칼의 업적입니다. 파스칼의 삼각형은 조합을 가시화하여 조합을 연구할 수 있게 만들어 준 것이죠. 그 이유가, 파스칼의 삼각형이 위대한 진짜 이유이며, 사실 파스칼의 삼각형에 나오는 여러 성질들(이항계수의 일치이거나, 각 항의 합은 2^n 꼴이라는)은 모두 조합을 이용해서 증명이 되고 또 파스칼의 삼각형은 조합이 가진 성질을 추측하게 도와주는 좋은 도구로 쓰이기도 합니다. 그러면 다음 포스팅에서 계속해서 순열과 조합에 대해 알아보도록 하겠습니다. 파스칼의 삼각형 속의 숫자들은 바로 윗 줄에 인접하는 두 숫자의 합으로 정의된다. 파스칼의 삼각형(Pascal's triangle)은 수학에서 이항계수를 삼각형 모양으로 배열한 것이다. 이것은 블레즈 파스칼의 이름을 따 명명되었지만, 그가 처음 발견한 것은 아니고 수세기 전에 인도,[1] 페르시아,[2] 중국, 독일, 이탈리아 등에서 이미 연구된 바가 있다.[3] 간단히 말하자면, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다.
파스칼의 법칙을 이용해 이 규칙을 아래와 같이 수학적으로 표현할 수 있다. n 번째 줄의 k 번째 값을 라고 할 때, 으로 정의된다. 이때, 조합 배열의 예[편집]처음2줄[편집]가장자리의 수는 없는 부분이 '0' 이라고 생각해서 1을 더하고 나온 값인 1을 그대로 내려온다. 파스칼의 삼각형의 3열의 모든 숫자는 자신의 상위 열의 2개 숫자를 더해서 만든다. 가장자리의 수는 계속해서 0과 1을 더한다고 생각하고 1을 그대로 내린다. 파스칼 삼각형의 6열. 네 번째 줄의 1과 3을 더해 다섯 번째 줄의 4를 만든다. 네 번째 줄의 3과 3을 더해 다섯 번째 줄의 6을 만든다. 11줄[편집]19줄[편집]1 -> n=0 일때 1 1 -> n=1 일때 1 2 1 -> n=2 일때 1 3 3 1 . 1 4 6 4 1 . 1 5 10 10 5 1 . 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1 1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1 1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1 1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1 파스칼의 삼각형의 응용[편집]파스칼의 삼각형은 이항정리에서 계수들의 값을 계산하는 데에 사용된다. 예를 들어서 라는 식에서, 각 계수의 값인 1, 2, 1은 파스칼의 삼각형의 3번째 줄에 대응된다. 일반적으로, 와 같은 전개식에서, 가 성립한다. 즉, 는 파스칼의 삼각형의번째 행(row)의 번째 열(column) 값과 순차적으로 대응된다. 소스코드[편집]스칼라[편집]//파스칼 삼각형 소스코드 var height:Int = 0 def pTriangle(given:Array[Int], stop:Int):Unit = { println(given.deep.toString) height = height + 1 if (height < stop) { val next = Array.ofDim[Int](given.length + 1) for (i <- 0 until next.length) { if (i == 0 || i == next.length-1) next(i) = 1 else next(i) = given(i-1) + given(i) } pTriangle(next, stop) } else { height = 0 } } C# public class PascalsTriangle { static void PascalTriangle(int n) { for (int line = 1; line <= n; line++) { int c = 1; for (int i = 1; i <= line; i++) { Console.WriteLine(c); c = c * (line - i) / i; } Console.WriteLine("\n"); } } public static int Main(int input) { PascalTriangle(input); return input; } } 일반화[편집]파스칼의 삼각형은 더 높은 차원으로 확장하여 일반화할 수 있다. 3차원 형태는 파스칼의 피라미드 또는 파스칼의 4면체로 부른다. 더 높은 차원의 유사체를 일반적으로 총칭하여 "파스칼의 단체"라고 말한다. 같이 보기[편집]
|