이항정리

문서의 이전 버전(r13)을 보고 있습니다.

역사 raw
대문 랜덤 문서 최근 토론
분류
1. 개요
1.1. 이항계수1.2. 이항정리
2. 이항계수의 성질
2.1. 성질 12.2. 성질 22.3. 성질 32.4. 성질 42.5. 성질 5
3. 다항정리4. 일반화된 이항계수와 뉴턴의 이항정리5. 1학년의 꿈6. 관련 문서

1. 개요[편집]

binomial theorem ・ 二項定理

(a+b)n(a+b)^{n}(nn은 음이 아닌 정수)의 꼴을 전개할 때 쓰이는 정리이다. 이항정리의 '이항'은 '두 개의 항(二項)'이라는 뜻이며, '항을 옮긴다'(移項)는 뜻이 아니다.

이것의 증명에는 파스칼의 정리를 이용하는 방법과 테일러 급수를 이용하거나, 경우의 수를 이용하는 방법이 있다. 이 문서에서는 마지막 방법을 쓴다.

이 문서에서 조합은 nCr{}_{n}\mathrm{C}_{r} 대신 국제적으로 많이 사용되는 (nr)\binom{n}{r} 로 표기했다.

1.1. 이항계수[편집]

이항계수(binomial coefficient)란, (a+b)n(a+b)^{n}의 꼴의 다항식을 전개했을 때, arbn−ra^{r}b^{n-r}(0≤r≤n0 \leq r \leq n인 정수)의 계수를 의미하며, 다음과 같다.

(nr)=n!r!(n−r)!\displaystyle \binom{n}{r}=\frac{n!}{r!(n-r)!}

이것의 증명은 다음을 이용하면 된다.

(a+b)n=(a+b)(a+b)⋅⋯⋅(a+b)⏟n arguments\displaystyle (a+b)^{n}=\underbrace{(a+b)(a+b)\cdot \cdots \cdot (a+b)}_{n \text{ arguments}}

arbn−ra^{r}b^{n-r}의 계수는 곧 aa, bb를 중복을 허락하고, 두 문자를 일렬로 nn개 배열하는 경우의 수와 같다.[1] 따라서

n!r!(n−r)!\displaystyle \frac{n!}{r!(n-r)!}

이고, 이것은 곧 조합의 정의와 같으므로 arbn−ra^{r}b^{n-r}의 계수는 다음과 같다.

(nr)\displaystyle \binom{n}{r}

1.2. 이항정리[편집]

따라서 (a+b)n(a+b)^{n}의 꼴의 다항식을 전개하면 다음과 같은데, 이를 이항정리라 한다.

(a+b)n=∑r=0n(nr)arbn−r\displaystyle (a+b)^{n}=\sum_{r=0}^{n} \binom{n}{r} a^{r}b^{n-r}

2. 이항계수의 성질[편집]

아래는 고교과정 수준에서 이항정리를 이용해 얻을 수 있는 이항계수의 성질들이다.[2] 일종의 조합론에서 쓰이는 생성함수 테크닉에 가깝지만, 교과과정에서는 당연히 '생성함수'라는 말을 언급하진 않는다.

아래의 문단의 결과를 모두 정리하면 다음과 같다.
  • ∑r=0n(nr)=2n\displaystyle \sum_{r=0}^n\binom{n}{r}=2^n
  • ∑r=0n(−1)r(nr)=0\displaystyle \sum_{r=0}^n\left(-1\right)^r\binom{n}{r}=0
  • (n0)+(n2)+(n4)+⋯=2n−1\displaystyle \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots=2^{n-1}
  • (n1)+(n3)+(n5)+⋯=2n−1\displaystyle \binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\cdots=2^{n-1}
  • (2nn)=∑r=0n(nr)2\displaystyle \binom{2n}{n}=\sum_{r=0}^{n}\binom{n}{r}^2
  • ∑k=0n(kr)=(n+1r+1)\displaystyle \sum_{k=0}^{n}\binom{k}{r}=\binom{n+1}{r+1}
  • ∑k=0r(n+kk)=(n+r+1r)\displaystyle \sum_{k=0}^{r}\binom{n+k}{k}=\binom{n+r+1}{r}
  • (n0)+(n−11)+(n−22)+⋯+(1n−1)+(0n)=Fn\displaystyle \binom{n}{0}+\binom{n-1}{1}+\binom{n-2}{2}+\cdots+\binom{1}{n-1}+\binom{0}{n}= F_n은 피보나치 수열을 이룬다.
  • ∑r=0nr(nr)=n2n−1\displaystyle \sum_{r=0}^nr\binom{n}{r}=n2^{n-1}
  • ∑r=0nr2(nr)=n(n+1)2n−2\displaystyle \sum_{r=0}^nr^2\binom{n}{r}=n\left(n+1\right)2^{n-2}
  • ∑r=0n1r+1(nr)=1n+12n+1\displaystyle \sum_{r=0}^{n} \dfrac 1 {r+1} \binom{n}{r} = \dfrac 1 {n+1} 2^{n+1}
  • ∑r=0n(−1)r+11r+1(nr)=0\displaystyle \sum_{r=0}^{n} (-1)^{r+1} \dfrac 1 {r+1} \binom{n}{r} = 0

2.1. 성질 1[편집]

다항식 (x+1)n(x+1)^{n}을 이항정리로 나타내면

(x+1)n=∑r=0n(nr)xr\displaystyle (x+1)^{n}=\sum_{r=0}^{n} \binom{n}{r} x^{r}

이것은 항등식이므로 xx에 무엇을 대입하여도 성립한다. x=1x=1을 대입하면,

2n=∑r=0n(nr)⋯  (a)\displaystyle 2^{n}=\sum_{r=0}^{n} \binom{n}{r} \qquad \cdots \; \text{(a)}

이번에는 x=−1x=-1을 대입하면,

0=∑r=0n(nr)(−1)r⋯  (b)\displaystyle 0=\sum_{r=0}^{n} \binom{n}{r}(-1)^{r} \qquad \cdots \; \text{(b)}

((a)+(b))/2 (\text{(a)}+\text{(b)})/2 를 하면, 홀수 번째 항의 합이 된다.

2n−1=(n0)+(n2)+(n4)+⋯\displaystyle 2^{n-1}= \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots

((a)−(b))/2 (\text{(a)}-\text{(b)})/2 를 하면, 짝수 번째 항의 합이 된다.

2n−1=(n1)+(n3)+(n5)+⋯\displaystyle 2^{n-1}= \binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\cdots

2.2. 성질 2[편집]

이번에는 다항식 (x+1)2n(x+1)^{2n}을 보자.

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

양변의 nn차항의 계수를 비교하면,

(2nn)=(n0)(nn)+(n1)(nn−1)+⋯+(nn)(n0)=(n0)2+(n1)2+(n2)2+⋯+(nn)2=∑r=0n(nr)2(∵(nn−r)=(nr))\begin{aligned}\displaystyle \binom{2n}{n}&=\binom{n}{0}\binom{n}{n}+\binom{n}{1}\binom{n}{n-1}+\cdots+\binom{n}{n}\binom{n}{0}\\&={\binom{n}{0}}^{2}+{\binom{n}{1}}^{2}+{\binom{n}{2}}^{2}+\cdots+{\binom{n}{n}}^{2}\\&=\sum_{r=0}^{n} {\binom{n}{r}}^{2} \quad \left( \because\binom{n}{n-r}=\binom{n}{r} \right)\end{aligned}

2.3. 성질 3[편집]

(nr)=(n−1r−1)+(n−1r)\displaystyle \binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}

위의 파스칼의 정리를 사용하여도 여러 성질이 유도된다.


∑k=0n(kr)=(0r)+(1r)+(2r)+⋯+(nr)=(n+1r+1)\displaystyle \sum_{k=0}^{n} \binom{k}{r}=\binom{0}{r}+\binom{1}{r}+\binom{2}{r}+\cdots+\binom{n}{r}=\binom{n+1}{r+1}

을 증명하면 아래와 같다.

(0r+1)+(0r)⏟+(1r)+(2r)+⋯+(nr)=   (1r+1)+(1r)⏟+(2r)+⋯+(nr)=       (2r+1)+(2r)⏟(3r+1)+⋯+(nr)=⋯=(nr+1)+(nr)⏟=    (n+1r+1)\displaystyle \displaystyle \begin{aligned} &\underbrace{\binom{0}{r+1}+\binom{0}{r}}+\binom{1}{r}+\binom{2}{r}+\cdots+\binom{n}{r} \\&=\,\,\,\underbrace{\binom{1}{r+1}+\binom{1}{r}}+\binom{2}{r}+\cdots+\binom{n}{r} \\&=\,\,\,\quad \,\,\,\, \underbrace{\binom{2}{r+1}+\binom{2}{r}}_{ \binom{3}{r+1}}+\cdots+\binom{n}{r} \\&=\cdots \\&= \underbrace{\binom{n}{r+1}+\binom{n}{r}} \\&= \,\,\,\quad \,\binom{n+1}{r+1} \end{aligned}


비슷한 방법으로 다음을 증명할 수 있다.

(n0)+(n1)+(n2)+⋯+(nr)=(n+10)+(n1)+(n2)+⋯+(nr)=(n+r+1r)(∵(n0)=(n+10))∴∑k=0n(n+kr)=(n+r+1r)\displaystyle \begin{aligned} \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{r} &=\binom{n+1}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{r} \\ &=\binom{n+r+1}{r} \quad \left( \because\displaystyle \binom{n}{0}=\binom{n+1}{0} \right) \\ \\ \therefore\displaystyle \sum_{k=0}^{n} \binom{n+k}{r}&=\binom{n+r+1}{r} \end{aligned}

2.4. 성질 4[편집]


Fn=(n0)+(n−11)+(n−22)+⋯+(1n−1)+(0n)\displaystyle F_{n} = \binom{n}{0}+\binom{n-1}{1}+\binom{n-2}{2}+\cdots+\binom{1}{n-1}+\binom{0}{n}

위와 같이 정의되는 수열 FnF_{n}은 피보나치 수열이다. F0=F1=1F_{0}=F_{1}=1이고, 파스칼의 정리에 의하여 다음이 성립한다.

Fn=Fn−1+Fn−2F_{n}=F_{n-1}+F_{n-2}

2.5. 성질 5[편집]

이번에는 (1+x)n(1+x)^{n}을 미분해 보자.

∑r=0nr(nr)xr−1=n(1+x)n−1⋯(c)\displaystyle \sum_{r=0}^{n} r \binom{n}{r} {x}^{r-1}=n(1+x)^{n-1} \qquad \cdots \text{(c)}


(c) \text{(c)}에 x=1x=1을 대입하면

∑r=0nr(nr)=2n−1n\displaystyle \sum_{r=0}^{n} r \binom{n}{r}=2^{n-1}n


한편 (c) \text{(c)}에 x=−1x=-1을 대입하면

∑r=0nr(nr)(−1)r−1=0\displaystyle \sum_{r=0}^{n} r \binom{n}{r} (-1)^{r-1}=0


(c) \text{(c)}를 한 번 더 미분하여 x=1x=1을 대입하면

∑r=0nr2(nr)=2n−2n(n+1)\displaystyle \sum_{r=0}^{n} r^{2} \binom{n}{r}=2^{n-2}n(n+1)



(x+1)n=∑r=0n(nr)xr\displaystyle (x+1)^{n}=\sum_{r=0}^{n} \binom{n}{r} x^{r}

을 적분하여 x=1x=1을 대입하면


∑r=0n1r+1(nr)xr+1=1n+1(x+1)n+1\displaystyle \sum_{r=0}^{n} \dfrac 1 {r+1} \binom{n}{r} x^{r+1} = \dfrac 1 {n+1} (x+1)^{n+1}


∑r=0n1r+1(nr)=1n+12n+1\displaystyle \sum_{r=0}^{n} \dfrac 1 {r+1} \binom{n}{r} = \dfrac 1 {n+1} 2^{n+1}


x=−1x=-1을 대입하면

∑r=0n(−1)r+11r+1(nr)=0\displaystyle \sum_{r=0}^{n} (-1)^{r+1} \dfrac 1 {r+1} \binom{n}{r} = 0


한편,

(x+1)n=∑r=0n(nr)xr\displaystyle (x+1)^{n}=\sum_{r=0}^{n} \binom{n}{r} x^{r}

식에 허수단위 i\displaystyle i를 대입하면

(i+1)n=∑r=0n(nr)ir={(n0)−(n2)+(n4)−⋯ }+i{(n1)−(n3)+(n5)−⋯ }\displaystyle \begin{aligned} (i+1)^{n}&=\sum_{r=0}^{n} \binom{n}{r} i^{r}\\& = \left \{ \binom{n}{0} - \binom{n}{2} + \binom{n}{4} - \cdots \right \} + i \left \{ \binom{n}{1} - \binom{n}{3} + \binom{n}{5} - \cdots \right \} \end{aligned}

위 결과는 아래와 같이 정리할 수 있다.

ℜ((i+1)n)=(n0)−(n2)+(n4)−(n6)+⋯ℑ((i+1)n)=(n1)−(n3)+(n5)−(n7)+⋯\displaystyle \begin{aligned} \Re((i+1)^{n})&= \binom{n}{0} - \binom{n}{2} + \binom{n}{4} - \binom{n}{6} + \cdots \\ \Im((i+1)^{n})&=\binom{n}{1} - \binom{n}{3} + \binom{n}{5} - \binom{n}{7} + \cdots \end{aligned}

이때, ℜ(z)\Re(z), ℑ(z)\Im(z)은 각각 복소수 zz의 실수 부분, 허수 부분이다.

3. 다항정리[편집]

이항정리는 항이 2개일 때 사용한다면, 다항정리는 항이 3개 이상일 때 사용한다. 다음과 같은 꼴의 다항식을 고려하자.

(x1+x2+x3+⋯+xm)n\displaystyle (x_{1}+x_{2}+x_{3}+\cdots+x_{m})^{n}

x1n1x2n2⋅⋯⋅xmnnx_{1}^{n_{1}}x_{2}^{n_{2}} \cdot \cdots \cdot x_{m}^{n_{n}} (단, ∑k=1nnk=n\sum_{k=1}^{n}n_{k}=n)의 계수를 구하고 싶다면, 이항정리 때의 논법과 유사하게 x1∼xnx_{1} \sim x_{n}을 중복을 허락하여 일렬로 배열하는 경우의 수와 같으므로 그 계수는 다음과 같다.

n!n1!n2!n3!⋅⋯⋅nn!\displaystyle \frac{n!}{n_{1}! n_{2}! n_{3}! \cdot \cdots \cdot n_{n}!}

따라서 다항정리는 다음과 같다.

(x1+x2+x3+⋯+xm)n=∑n!n1!n2!n3!⋅⋯⋅nm!x1n1x2n2⋅⋯⋅xmnm\displaystyle \begin{aligned} &(x_{1}+x_{2}+x_{3}+\cdots+x_{m})^{n} \\ &=\sum \frac{n!}{n_{1}! n_{2}! n_{3}! \cdot \cdots \cdot n_{m}!} x_{1}^{n_{1}}x_{2}^{n_{2}} \cdot \cdots \cdot x_{m}^{n_{m}} \end{aligned}

4. 일반화된 이항계수와 뉴턴의 이항정리[편집]

고교과정을 넘어서면, (nr)\binom{n}{r} 중 nn이 정수가 아닐 때도 정의되기 때문에 이항정리를 일반화할 수 있다. 다만, 여전히 rr이 음이 아닌 정수이어야 한다. 따라서 다음의 조합의 정의에 따라

(nr)=n(n−1)(n−2)⋅⋯⋅(n−r+1)r!\displaystyle \binom{n}{r}=\frac{n(n-1)(n-2)\cdot \cdots \cdot (n-r+1)}{r!}

n=b/an=b/a일 때의 이항계수는

(b/ar)=b!ar!ar(b−ar)!a\displaystyle \binom{b/a}{r}=\frac{b!_{a}}{r!a^{r}(b-ar)!_{a}}

로 일반화된다. 여기서 N!pN!_{p}는 pp중 계승으로 정의되고,

N!p≡∏m=0⌊(N−1)/p⌋(N−mp)\displaystyle N!_{p} \equiv \prod_{m=0}^{\lfloor\left(N-1\right)/p\rfloor} \left(N-mp\right)

혹은

N!p≡∏∀g≡N(modp)g\displaystyle N!_{p} \equiv \prod^{\forall{g}\equiv N\pmod{p}} g [3]

으로 정의된다.

뉴턴은 이를 이용해서 이항정리의 일반화된 버전을 증명하였는데, 실수 혹은 복소수 zz에 대하여 다음의 전개식

(z+1)n=∑r=0∞(nr)zr\displaystyle \displaystyle (z+1)^n = \sum_{r=0}^{\infty} \binom{n}{r} z^r

이 성립한다는 것이 그것이다. 증명은 테일러 정리를 사용하면 바로 나오게 된다.[4]

사실 이 이항정리 자체보다는 더 큰 의미를 갖는 것은 이항계수 성질의 확장이다. 파스칼 항등식, 하키스틱 성질 등등 이항계수에서 성립하는 성질들 대부분은 (확장할 수 있으면) 일반화된 이항계수에서 무조건 성립한다. 어찌 보면 당연한 게 이항계수도 어쨌든 nn에 대한 다항식이므로, 다항식 등식이 양의 정수값에 대해 같은 값을 가진다면 항등식이 되는 게 맞다. 하지만 실제로 nn에 음의 정수나 유리수 등을 넣어서, 카탈란 수나 중복조합 등등을 유의미하게 계산해내고, 이들의 성질을 자연수에서 성립하는 이항계수 성질의 유추로 증명하는 건 단순히 조합만으로는 납득하기 힘든 강력한 도구가 되곤 한다.

만약 nn, rr이 모두 정수가 아닐 경우[5] 베타 함수로 이항계수를 정의해야 한다.

5. 1학년의 꿈[편집]

6. 관련 문서[편집]


[1] 한국의 교육과정의 용어를 빌려 말하면, 곧 이것은 같은 것이 있는 순열의 경우와 동치이다.[2] 따라서 Vandermonde convolution (n+mr)=∑(nk)(mr−k) \displaystyle \binom{n+m}{r} = \sum \binom{n}{k} \binom{m}{r-k} 등의 다양한 이항계수 항등식들이 빠져 있다.[3] gg는 법 pp에 대해서 NN 이하의 0을 포함하는 모든 양의 정수 중 NN과 합동인 정수들의 곱[4] 다만, 그 전에 실수 혹은 복소수 지수가 무엇인지 엄밀한 정의가 필요하긴 하다.[5] 물론 nn, rr은 0보다 커야 한다.