파스칼의 삼각형

파스칼의 삼각형 속의 숫자들은 바로 윗 줄에 인접하는 두 숫자의 합으로 정의된다.

파스칼의 삼각형(Pascal's triangle)은 수학에서 이항계수를 삼각형 모양으로 배열한 것이다. 이것은 블레즈 파스칼의 이름을 따 명명되었지만, 그가 처음 발견한 것은 아니고 수세기 전에 인도,^[1] 페르시아,^[2] 중국, 독일, 이탈리아 등에서 이미 연구된 바가 있다.^[3]

간단히 말하자면, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다.

1. 첫 번째 줄에는 1을 쓴다.
2. 그 다음 줄을 만들 때 바로 위의 왼쪽 숫자와 오른쪽 숫자를 더한다(오른쪽 그림 참고). 예를 들어, 네 번째 줄의 숫자 1과 3을 더하여 다섯 번째 줄의 4가 만들어진다.

파스칼의 법칙을 이용해 이 규칙을 아래와 같이 수학적으로 표현할 수 있다. n 번째 줄의 k 번째 값을 ${\displaystyle a_{nk}}$라고 할 때,

${\displaystyle a_{n1}=1}$

${\displaystyle a_{nn}=1}$

${\displaystyle a_{nk}=a_{{n-1}{k-1}}+a_{{n-1}{k}}}$ ${\displaystyle (n,k>=0)}$

으로 정의된다. 이때,

${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}}$

조합 배열의 예

처음2줄

가장자리의 수는 없는 부분이 '0' 이라고 생각해서 1을 더하고 나온 값인 1을 그대로 내려온다.

${\displaystyle \ \ \ \ \ \ \ 1}$

${\displaystyle \ 1\ \ \ \ \ \ \ \ \ \ 1}$

파스칼의 삼각형의 3열의 모든 숫자는 자신의 상위 열의 2개 숫자를 더해서 만든다.

가장자리의 수는 계속해서 0과 1을 더한다고 생각하고 1을 그대로 내린다.

${\displaystyle \ \ \ \ \ \ \ \ \ 1}$

${\displaystyle \ \ \ \ \ 1\ \ \ \ \ \ 1}$

${\displaystyle \ 1\ \ \ \ \ \ 2\ \ \ \ \ \ 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

파스칼의 삼각형의 응용

파스칼의 삼각형은 이항정리에서 계수들의 값을 계산하는 데에 사용된다. 예를 들어서

${\displaystyle (x+1)^{2}=1\cdot x^{2}+2\cdot x+1}$

라는 식에서, 각 계수의 값인 1, 2, 1은 파스칼의 삼각형의 3번째 줄에 대응된다.

일반적으로,

${\displaystyle (x+y)^{n}=a_{0}x^{n}y^{0}+a_{1}x^{n-1}y^{1}+a_{2}x^{n-2}y^{2}+\cdots +a_{n-2}x^{2}y^{n-2}+a_{n-1}x^{1}y^{n-1}+a_{n}x^{0}y^{n}}$

와 같은 전개식에서, ${\displaystyle a_{i}={n+1 \choose k}}$ 가 성립한다. 즉, ${\displaystyle a_{i}}$는 파스칼의 삼각형의${\displaystyle (n+1)}$번째 행(row)의 ${\displaystyle (k)}$ 번째 열(column) 값과 순차적으로 대응된다.

소스코드

파이썬

def pTriangle(n):
    p = []
    
    for row in range(n):
        tmp = [1] * (row + 1)
        for col in range(1, row):
            tmp[col] = p[row-1][col-1] + p[row-1][col]
        p.append(tmp)

    return p

스칼라

//파스칼 삼각형 소스코드
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면체로 부른다. 더 높은 차원의 유사체를 일반적으로 총칭하여 "파스칼의 단체"라고 말한다.

각주

1. Maurice Winternitz, History of Indian Literature, Vol. III
2. Coolidge, J. L. (1949), “The story of the binomial theorem”, 《The American Mathematical Monthly》 56 (3): 147–157, doi:10.2307/2305028, JSTOR 2305028, MR 0028222 .
3. Peter Fox (1998). 《Cambridge University Library: the great collections》. Cambridge University Press. 13쪽. ISBN 978-0-521-62647-7. 

같이 보기

• 피라미드
• 사면체
• 단체(單體)
• 곱셈 공식