2010년 10월 17일 일요일

이항 정리(二項定理, Binomial Theorem)

[경고] 아래 글을 읽지 않고 "이항 정리"를 보면 바보로 느껴질 수 있습니다.


[그림 1] 이항 정리의 기하학적 의미(출처: wikipedia.org)

조합(組合, combination)을 활용할 수 있는 재미난 예는 이항 정리(二項定理, binomial theorem)이다. 한글로 보면 이항이 무엇인지 분명하지 않지만 한자(二項)를 보면 항이 두 개라는 뜻이다. 이항 정리는 두 항의 합[= $x+y$]에 대한 거듭제곱을 전개하여 단항식의 합으로 정리한 식을 의미한다.

[이항 정리]

                          (1)

[증명]
조합의 의미를 이용하면 식 (1)은 쉽게 증명할 수 있다. 서로 다른 항이 $n$개 들어있는 식[∵ $(x+y)^n$은 식 $(x+y)$가 $n$번 곱해진 식이므로]에서 변수 $x$를 $k$개 뽑아서 순서를 고려하지 않고 모은 경우의 수는 조합 ${}_nC_k$가 되므로[혹은 각각 $k$개와 $n-k$개인 구별되지 않는 변수 $x$와 $y$를 순서대로 나열하는 경우의 수는 중복을 제거해서 $n! \mathop{/}[k! (n-k)!]$이 되므로], 식 (1)이 성립한다. 더 쉽게 $(x+y)^n$을 구별되게 $(x_1 + y_1)(x_2 + y_2) \cdots (x_n + y_n)$으로 놓고, $x_1, x_2, \cdots, x_n$ 중에서 $k$를 뽑는 경우의 수는 당연히 ${}_nC_k$가 된다. 왜냐하면 분배 법칙으로 만드는 여러 $x_i$의 곱은 중복될 수 없는 같은 연산 결과이기 때문이다. 예를 들면, $x_i x_j$ 곱이 있는 상태에서 $x_j x_i$는 나올 수 없고[이미 분배해서 한 번 더 곱을 만들 수 없어서], $x_i x_j x_k$는 $x_j x_k x_i$, $x_k x_i x_j$ 등과 동일한 분배 항이다.
______________________________

식 (1)에 등장하는 조합 ${}_nC_k$는 이항 정리의 이항 계수(binomial coefficient)이며, ${}_nC_k$ = ${}_nC_{n-k}$가 성립해서 전개식의 좌우에 배치된 이항 계수는 서로 대칭이다. 이항 정리는 예전부터 잘 알려진 개념이지만, 파스칼Blaise Pascal(1623–1662)산술 삼각형 논고에서 조합과 파스칼의 삼각형을 이용해 이항 정리를 수학적으로 새롭게 제시했다[2]. 식 (1)의 이항 정리를 이용하면 모든 경우에 대한 멱함수(冪函數, power) 미분 공식을 유도할 수 있다.

[멱함수(power) $x^n$의 미분]

                          (2)

여기서 $n$은 0을 포함한 자연수(natural number)이다.

[증명]
식 (1)에서 $y$ = $\Delta x$라 두고 $\Delta x \to 0$으로 가는 극한(limit)을 취하면 식 (2)가 증명된다.
______________________________

[음의 지수를 가진 $x^{-n}$의 미분]

                          (3)

여기서 $n$은 자연수(自然數, natural number)이다.

[증명]

              (4)
______________________________

식 (2)와 (4)를 종합하면 모든 정수 $n$에 대해 멱함수 $x^n$이 만족하는 미분 공식을 유도할 수 있다.

[유리수 지수를 가진 $x^{n/m}$의 미분]

                          (5)

여기서 $n, m$은 정수(整數, integer)이다.

[증명]

                          (6)
______________________________

식 (5)를 통해 멱함수의 미분 공식이 모든 유리수(有理數, rational number)로 확대된다.

[실수 지수를 가진 $x^r$의 미분]

                          (7)

여기서 $r$은 실수(實數, real number)이다.

[증명]
실수에 포함되는 무리수(無理數, irrational number)는 유리수의 극한으로 표현될 수 있으므로 정수 $n, m$의 자리수를 계속 늘려가면 식 (5)의 결과는 식 (7)에 한없이 가까이 갈 수 있다. 예를 들면, 무리수 $\sqrt{2}$ = 1.4142135623731...는 1, 14/10, 141/100, 1414/1000, 14142/10000, 등으로 오차를 한없이 줄이면서 지속적으로 유리수 근사를 할 수 있다. 하지만 유리수 근사를 할 수 있다고 해서 무리수를 유리수로 표현할 수는 없다.
______________________________

식 (7)은 미분학 시간에서 거의 처음에 배우는 미분 공식이지만 증명 자체는 매우 난해하다. 수업 시간에는 그냥 넘어가지만 꼼꼼하게 고민하면 배울 부분이 많다. 식 (7) 증명에 사용한 논리인 유리수의 자리수를 계속 늘리면 무리수가 될 수 있다는 성질은 뉴턴이 식 (7)을 증명할 때 이미 사용했다[1]. 뉴턴이 제안한 미분 공식 (7)은 분명 틀리지 않았기 때문이다. 하지만 유리수 자리수를 늘려가면 정말 무리수를 표현할 수 있을까? 무리수와 유리수는 사실 동일한 특성을 가진 수일까? 무리수를 유리수의 극한으로 표현할 수 있다는 설명을 수학적으로 잘 이해하려면 실수의 완비성(完備性, completeness)을 꼭 고민해야 한다. 데데킨트의 절단(Dedekind cut)을 이용하면 유리수는 아무리 자리수를 늘려가도 무리수가 될 수는 없다. 하지만 식 (7)의 증명에 사용한 논리처럼 유리수의 자리수를 늘려서 극한처럼 활용하면, 무리수와 무리수에 접근하는 유리수의 차이를 계속 줄일 수 있다.
식 (7)을 이용하면 뉴턴의 이항 정리(Newton's binomial theorem) 혹은 일반화 이항 정리(generalized binomial theorem)를 쉽게 증명할 수 있다[4]. 1665년뉴턴 22세, 조선 현종 시절 대학교 4학년이던 뉴턴Isaac Newton(1643–1727)이 미적분학을 만들면서 뉴턴의 이항 정리도 함께 발견했다.

[뉴턴의 이항 정리]

             (8)

[증명]
식 (7)에서 유도한 멱함수의 미분 공식을 테일러 급수(級數, Taylor series)에 적용하여 $(1+x)^r$에 대한 멱급수(power series)를 생성한다.
______________________________

식 (8)에 등장하는 $(r)_k$는 포흐하머 기호(Pochhammer symbol) 혹은 하강 계승(falling factorial)이라 부른다. 하강 계승과 비슷하게 상승 계승(rising factorial)도 만든다.

                  (9a)

                  (9b)

여기서 $(x)_0$ = $1$로 정의한다. 항들의 간격까지 조정하는 포흐하머 기호의 일반화(generalization of Pochhammer symbol)도 가능하다.

                  (10)

여기서 $(x)_{0,h}$ = $1$, $(x)_n$ = $(x)_{n,-1}$, $x^{(n)}$ = $(x)_{n,1}$이다. 식 (10)에 있는 간격 $h$의 부호에 따라 상승이나 하강 계승이 될 수 있어서 식 (10)은 포흐하머 기호의 일반화가 분명하다. 최근에는 식 (10)을 포흐하머 $k$-기호(Pochhammer $k$-symbol)로 부르기도 한다.
뉴턴의 이항 정리에서 지수 $r$이 $0$ 혹은 자연수가 아니라면, 식 (8)은 급수의 항이 끝없이 계속 나타나는 무한 급수가 된다. 특히 일반화 이항 정리에 나오는 이항 계수를 가지고 전개한 식 (8)과 같은 무한 급수는 이항 급수(二項級數, binomial series)라고 이름 붙인다. 이 이항 급수는 $x$에 따라 발산하기도 하고 수렴하기도 한다. 식 (8)이 수렴하는 경우는 비율 판정(ratio test)을 이용하여 계산할 수 있다.

                          (11)

따라서 식 (8)이 무한 급수인 경우 수렴 구간은 $|x| < 1$이다.
지수 $r$이 $0$ 혹은 자연수인 경우는 조합과 순열(permutation)의 관계로 포흐하머 기호를 편하게 다룰 수 있다.

                (12)

식 (1)은 다소 복잡하기 때문에, 편하게 쓸 때는 $y$ = $1$을 대입해 다음처럼 더 간략화한다.

                          (13)

조합 관점으로 이항 정리를 확장해서 다항 정리(多項定理, multinomial theorem)도 쉽게 획득할 수 있다.

[다항 정리]

             (14)

[증명]
변수 $x_1, x_2, \cdots, x_m$를 $k_1, k_2, \cdots, k_m$개를 뽑는 경우의 수를 고려한다. 전체를 뽑아서 한 줄로 세우는 경우는 $n!$이지만, 동일한 $x_r$은 여러 번 뽑히더라도 구별이 되지 않기 때문에 $r!$로 다시 나누어야 한다. 따라서 계승 $r!$로 나누는 과정을 $k_1, k_2, \cdots, k_m$에 대해 반복하면 식 (14)가 얻어진다. 
______________________________

식 (14)에서 항 $x_1^{k_1}x_2^{k_2} \cdots x_m^{k_m}$ 앞에 있는 계수는 다항 계수(multinomial coefficient)라 부른다. 거듭제곱을 $n$ = $2$로 한정하면, 다항 계수는 바로 이항 계수가 된다.
식 (1)과 (13)을 중심으로 여러 연산을 잘 적용하면 아래처럼 다양한 조합 공식을 만들어낼 수 있다.


   1. 기본(basics)   

[그림 1.1] 파스칼의 삼각형(출처: wikipedia.org)

[파스칼의 삼각형(Pascal's triangle)]

                          (1.1)

[증명]
식 (12)의 조합 정의를 통해 증명할 수 있다.

   (1.2)
______________________________

파스칼의 삼각형에 수학자 파스칼Blaise Pascal(1623–1662)의 이름이 있지만, 식 (1.1)은 고대부터 잘 알려진 공식이었다. 하지만 파스칼이 1654년파스칼 31세, 조선 효종 시절에 완성하고 1655년에 출판한 유명한 산술 삼각형 논고(論考, treaties)[2]에 파스칼의 삼각형이 나오기 때문에, 식 (1.1)을 파스칼의 삼각형이라 부른다. 파스칼이 출판한 논고는 예전부터 있던 공식을 정리한 수준이 아니었다. 짧지만 심오한 이 논고에서 파스칼은 이항 정리(binomial theorem), 조합(combination), 확률(probability), 기대값(expectation or expected value) 등을 수학적으로 깔끔하게 논증하고 증명했다. 1654년에 겪은 마차 사고로 인해 파스칼이 자신의 인생을 하느님[파스칼의 종교는 천주교]에게 바치지 않았다면, 뉴턴Isaac Newton(1643–1727) 이전에 살았던 파스칼이 손쉽게 미적분학(calculus)을 발견했을 것이다. 

[조합의 합]

                          (1.3)

[증명]
식 (13)에서 $x$ = $1$을 대입하면 식 (1.3)이 증명된다.
______________________________

식의 좌변과 우변에 서로 다른 의미를 부여해서 조합적으로 증명하는 이중 셈(double counting) 개념을 써도 식 (1.3)이 만들어진다. 모임이 0명부터 $n$명까지 허용된다면, 서로 다른 전체 모임의 수는 $2^n$이다. 왜냐하면 어떤 한 사람은 모임에 들어갈 수 있고 혹은 들어가지 않을 수 있고[선택지는 2개], 모든 사람들은 모임 참여를 독립적으로 판단하기 때문에 $2 \times 2 \times \cdots \times 2$ = $2^n$이다. 다른 관점으로 전체 $n$명으로 $k$명을 가진 모임 개수는 ${}_nC_k$이며, 실현 가능한 전체 모임 수는 $k$를 0에서 $n$까지 허용해서 모두 더하면 된다. 이중 셈 기법에서 이 두 경우는 같아야 하므로 식 (1.3)이 성립한다.

[자연수와 조합 곱의 합]

                          (1.4)

[증명]
식 (13)을 $x$에 대해 미분한 후 $x$ = $1$을 대입해서 유도한다.
______________________________

[자연수 제곱과 조합 곱의 합]

                          (1.5)

[증명]
먼저 식 (13)을 $x$에 대해 두 번 미분한다.

                          (1.6)

식 (1.6)에 $x$ = $1$을 대입하고 식 (1.4)의 결과를 다시 대입하면 식 (1.5)가 얻어진다.
______________________________

[파스칼의 항등식(Pascal's identity)]

                  (1.7)

여기서 $S_p(n)$은 다음과 같은 $p$차 거듭제곱의 합(sum of powers)이다.

                  (1.8)

[증명]
파스칼 항등식의 증명을 식 (1.7)의 우변부터 시작한다. 아래와 같이 두 거듭제곱의 차이를 합한 후, 식 (1)에 있는 이항 정리를 $(k+1)^{p+1}$에 대입한다.

                  (1.9)
______________________________

파스칼의 항등식[2], [3]은 거듭제곱의 합을 구할 때 편리하게 사용할 수 있다.

[방데르몽드의 항등식(Vandermonde's identity)]

                  (1.10)

[증명]
식 (1.3)처럼 이중 셈(double counting) 개념을 써서 쉽게 증명한다. 남자 $m$명, 여자 $n$명인 집단에서 $r$명으로 구성한 서로 다른 모임을 만드는 가지수는 ${}_{m+n}C_r$이다. 또 다른 측면으로 남자에서 $k$명, 여자에서 $r-k$명을 뽑아서 만드는 모임의 개수는 ${}_{m}C_k \cdot {}_{n}C_{r-k}$이다. 이때 $k$는 사람수라서 0명부터 $r$명까지 가능하다. 모든 가능한 $k$를 다 더한 값은 식 (1.10)의 우변이다. 이는 좌변과 같아야 하므로 증명이 완성된다. 
______________________________

1772년방데르몽드 37세, 조선 영조 시절에 방데르몽드의 항등식을 만든 방데르몽드Alexandre-Théophile Vandermonde(1735–1796)방데르몽드 행렬(Vandermonde matrix)로도 유명하다.


   2. 특정값(specific value)과 극한(limit)   

[제곱근의 역수]

                       (2.1)

여기서 $(\cdot)!!$은 이중 계승(double factorial)이다.

[증명]
식 (8)에 나온 계수에 $r$ = $-1/2$를 대입해서 정리한다.

                  (2.2)
______________________________

무한 곱(infinite product)을 쓰면 $k$가 커질 때 접근하는 식 (2.1)의 점근적 특성도 쉽게 구해진다.

                  (2.3)

식 (2.3)을 식 (8)에 넣어서 제곱근 역수를 근사적으로 계산하는 급수를 만들 수도 있다.

                  (2.4)

여기서 $|x| < 1$을 만족한다.


[참고문헌]
[1] 윌리엄 던햄, 미적분학 갤러리: 뉴턴에서 르베그까지 위대한 수학자들이 들려주는 미적분 이야기, 한승, 2011.
[2] B. Pascal, Traité du triangle arithmétique (Treatise on Arithmetical Triangle), 1654.
[3] K. MacMillan and J. Sondow, "Proofs of power sum and binomial coefficient congruences via Pascal's identity," The American Mathematical Monthly, vol. 118, no. 6, pp. 549–551, 2011.
[4] 고영미, 이상욱, "뉴턴의 일반화된 이항정리의 기원", 한국수학사학회지, 제27권, 제2호, pp. 127–138, 2014년 4월.

[다음 읽을거리]
1. 아름다운 숫자, 오일러 수
2. 조화 급수와 오일러–마스케로니 상수
3. 베르누이 수

댓글 6개 :

  1. 이항정리 증명부분 이해가 안되요 어찌이래 단단한지 ..

    답글삭제
    답글
    1. 아래 조합 부분을 다시 한 번 보세요. 계속 도전하면 이해할 수 있습니다.

      http://ghebook.blogspot.com/2010/10/permutation-combination.html

      삭제
  2. 아 이해한것같아요.
    아래 유투브 보고
    요즘 참 공부하기 좋은 것같네요 YouTube에서 이 동영상을 확인하세요.

    http://youtu.be/qV3SHOzQE5A

    답글삭제
    답글
    1. 거북님 말고 저처럼 이해 안되는 분들 참고하시라고...

      삭제
  3. 아 거북님 이항정리만 특별한 유용성이 있나요. 혹시 삼항,사항 ... 육항정리 등 확장 일반화는 안되나요.. 주사위를 반복해서 던질경우 육항정리가 도움이 될것 같은데요.

    답글삭제
    답글
    1. 이항정리의 일반화는 위키피디아에도 자세히 설명 되어있으니 그 쪽을 살펴보시는게 어떤가요? 그리고 주사위를 반복해서 던질 경우에 대해서는 독립시행의 확률로 충분히 해결할 수 있기에 굳이 이항정리의 일반화를 이용하여 접근할 필요가 없어보입니다.

      삭제

욕설이나 스팸글은 삭제될 수 있습니다. [전파거북이]는 선플운동의 아름다운 인터넷을 지지합니다.