[include(틀:이산수학·수리논리학)] [include(틀:대수학)] [목차] == 개요 == {{{+1 binomial theorem ・ [[二]][[項]][[定]][[理]]}}} [math((a+b)^{n})]([math(n)]은 음이 아닌 정수)의 꼴을 전개할 때 쓰이는 정리이다. 이항정리의 '이항'은 '두 개의 항(二項)'이라는 뜻이며, '항을 옮긴다'([[移]]項)는 뜻이 아니다. 이것의 증명에는 [[파스칼의 삼각형|파스칼의 정리]]를 이용하는 방법과 [[테일러 급수]]를 이용하거나, [[경우의 수]]를 이용하는 방법이 있다. 이 문서에서는 마지막 방법을 쓴다. 이 문서에서 [[조합]]은 [math({}_{n}\mathrm{C}_{r})] 대신 국제적으로 많이 사용되는 [math(\binom{n}{r} )]로 표기했다. === 이항계수 === '''이항계수(binomial coefficient)'''란, [math((a+b)^{n})]의 꼴의 다항식을 전개했을 때, [math(a^{r}b^{n-r})]([math(0 \leq r \leq n)]인 정수)의 계수를 의미하며, 다음과 같다. {{{#!wiki style="text-align: center" [br][math(\displaystyle \binom{n}{r}=\frac{n!}{r!(n-r)!} )]}}} 이것의 증명은 다음을 이용하면 된다. {{{#!wiki style="text-align: center" [br][math(\displaystyle (a+b)^{n}=\underbrace{(a+b)(a+b)\cdot \cdots \cdot (a+b)}_{n \text{ arguments}} )]}}} [math(a^{r}b^{n-r})]의 계수는 곧 [math(a)], [math(b)]를 중복을 허락하고, 두 문자를 일렬로 [math(n)]개 배열하는 경우의 수와 같다.[* 한국의 교육과정의 용어를 빌려 말하면, 곧 이것은 같은 것이 있는 순열의 경우와 동치이다.] 따라서 {{{#!wiki style="text-align: center" [br][math(\displaystyle \frac{n!}{r!(n-r)!} )]}}} 이고, 이것은 곧 [[조합]]의 정의와 같으므로 [math(a^{r}b^{n-r})]의 계수는 다음과 같다. {{{#!wiki style="text-align: center" [br][math(\displaystyle \binom{n}{r} )]}}} === 이항정리 === 따라서 [math((a+b)^{n})]의 꼴의 다항식을 전개하면 다음과 같은데, 이를 '''이항정리'''라 한다. {{{#!wiki style="text-align: center" [br][math(\displaystyle (a+b)^{n}=\sum_{r=0}^{n} \binom{n}{r} a^{r}b^{n-r} )]}}} == 이항계수의 성질 == 아래는 고교과정 수준에서 이항정리를 이용해 얻을 수 있는 이항계수의 성질들이다.[* 따라서 Vandermonde convolution [math( \displaystyle \binom{n+m}{r} = \sum \binom{n}{k} \binom{m}{r-k} )] 등의 다양한 이항계수 항등식들이 빠져 있다.] 일종의 조합론에서 쓰이는 생성함수 테크닉에 가깝지만, 교과과정에서는 당연히 '생성함수'라는 말을 언급하진 않는다. 아래의 문단의 결과를 모두 정리하면 다음과 같다. * [math(\displaystyle \sum_{r=0}^n\binom{n}{r}=2^n)] * [math(\displaystyle \sum_{r=0}^n\left(-1\right)^r\binom{n}{r}=0)] * [math(\displaystyle \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots=2^{n-1})] * [math(\displaystyle \binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\cdots=2^{n-1})] * [math(\displaystyle \binom{2n}{n}=\sum_{r=0}^{n}\binom{n}{r}^2)] * [math(\displaystyle \sum_{k=0}^{n}\binom{k}{r}=\binom{n+1}{r+1})] * [math(\displaystyle \sum_{k=0}^{r}\binom{n+k}{k}=\binom{n+r+1}{r})] * [math(\displaystyle \binom{n}{0}+\binom{n-1}{1}+\binom{n-2}{2}+\cdots+\binom{1}{n-1}+\binom{0}{n}= F_n)]은 [[피보나치 수열]]을 이룬다. * [math(\displaystyle \sum_{r=0}^nr\binom{n}{r}=n2^{n-1})] * [math(\displaystyle \sum_{r=0}^nr^2\binom{n}{r}=n\left(n+1\right)2^{n-2})] * [math(\displaystyle \sum_{r=0}^{n} \dfrac 1 {r+1} \binom{n}{r} = \dfrac 1 {n+1} 2^{n+1})] * [math(\displaystyle \sum_{r=0}^{n} (-1)^{r+1} \dfrac 1 {r+1} \binom{n}{r} = 0)] === 성질 1 === 다항식 [math((x+1)^{n})]을 이항정리로 나타내면 {{{#!wiki style="text-align: center" [br][math(\displaystyle (x+1)^{n}=\sum_{r=0}^{n} \binom{n}{r} x^{r} )]}}} 이것은 [[항등식]]이므로 [math(x)]에 무엇을 대입하여도 성립한다. [math(x=1)]을 대입하면, {{{#!wiki style="text-align: center" [br][math(\displaystyle 2^{n}=\sum_{r=0}^{n} \binom{n}{r} \qquad \cdots \; \text{(a)} )]}}} 이번에는 [math(x=-1)]을 대입하면, {{{#!wiki style="text-align: center" [br][math(\displaystyle 0=\sum_{r=0}^{n} \binom{n}{r}(-1)^{r} \qquad \cdots \; \text{(b)} )]}}} [math( (\text{(a)}+\text{(b)})/2 )]를 하면, 홀수 번째 항의 합이 된다. {{{#!wiki style="text-align: center" [br][math(\displaystyle 2^{n-1}= \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots)]}}} [math( (\text{(a)}-\text{(b)})/2 )]를 하면, 짝수 번째 항의 합이 된다. {{{#!wiki style="text-align: center" [br][math(\displaystyle 2^{n-1}= \binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\cdots)]}}} === 성질 2 === 이번에는 다항식 [math((x+1)^{2n})]을 보자. {{{#!wiki style="text-align: center" [br][math(\displaystyle (x+1)^{2n}=(x+1)^{n}(x+1)^{n})]}}} 양변의 [math(n)]차항의 계수를 비교하면, {{{#!wiki style="text-align: center" [br][math(\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})]}}} === 성질 3 === {{{#!wiki style="text-align: center" [math(\displaystyle \binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r} )] }}} 위의 [[파스칼의 삼각형|파스칼의 정리]]를 사용하여도 여러 성질이 유도된다. {{{#!wiki style="text-align: center" [br][math(\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} )] }}} 을 증명하면 아래와 같다. {{{#!wiki style="text-align: center" [br][math(\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} )] }}} 비슷한 방법으로 다음을 증명할 수 있다. {{{#!wiki style="text-align: center" [br][math(\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} )] }}} === 성질 4 === {{{#!wiki style="text-align: center" [br][math(\displaystyle F_{n} = \binom{n}{0}+\binom{n-1}{1}+\binom{n-2}{2}+\cdots+\binom{1}{n-1}+\binom{0}{n} )] }}} 위와 같이 정의되는 수열 [math(F_{n})]은 [[피보나치 수열]]이다. [math(F_{0}=F_{1}=1)]이고, [[파스칼의 삼각형|파스칼의 정리]]에 의하여 다음이 성립한다. {{{#!wiki style="text-align: center" [br][math(F_{n}=F_{n-1}+F_{n-2})]}}} === 성질 5 === 이번에는 [math((1+x)^{n})]을 미분해 보자. {{{#!wiki style="text-align: center" [br][math(\displaystyle \sum_{r=0}^{n} r \binom{n}{r} {x}^{r-1}=n(1+x)^{n-1} \qquad \cdots \text{(c)} )]}}} [math( \text{(c)})]에 [math(x=1)]을 대입하면 {{{#!wiki style="text-align: center" [br][math(\displaystyle \sum_{r=0}^{n} r \binom{n}{r}=2^{n-1}n )] }}} 한편 [math( \text{(c)})]에 [math(x=-1)]을 대입하면 {{{#!wiki style="text-align: center" [br][math(\displaystyle \sum_{r=0}^{n} r \binom{n}{r} (-1)^{r-1}=0 )] }}} [math( \text{(c)})]를 한 번 더 미분하여 [math(x=1)]을 대입하면 {{{#!wiki style="text-align: center" [br][math(\displaystyle \sum_{r=0}^{n} r^{2} \binom{n}{r}=2^{n-2}n(n+1) )] }}} {{{#!wiki style="text-align: center" [br][math(\displaystyle (x+1)^{n}=\sum_{r=0}^{n} \binom{n}{r} x^{r} )]}}} 을 적분하여 [math(x=1)]을 대입하면 {{{#!wiki style="text-align: center" [br][math(\displaystyle \sum_{r=0}^{n} \dfrac 1 {r+1} \binom{n}{r} x^{r+1} = \dfrac 1 {n+1} (x+1)^{n+1})]}}} {{{#!wiki style="text-align: center" [br][math(\displaystyle \sum_{r=0}^{n} \dfrac 1 {r+1} \binom{n}{r} = \dfrac 1 {n+1} 2^{n+1})]}}} [math(x=-1)]을 대입하면 {{{#!wiki style="text-align: center" [br][math(\displaystyle \sum_{r=0}^{n} (-1)^{r+1} \dfrac 1 {r+1} \binom{n}{r} = 0)]}}} 한편, {{{#!wiki style="text-align: center" [br][math(\displaystyle (x+1)^{n}=\sum_{r=0}^{n} \binom{n}{r} x^{r} )]}}} 식에 허수단위 [math(\displaystyle i)]를 대입하면 {{{#!wiki style="text-align: center" [br][math(\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})] }}} 위 결과는 아래와 같이 정리할 수 있다. {{{#!wiki style="text-align: center" [br][math(\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})] }}} 이때, [math(\Re(z))], [math(\Im(z))]은 각각 복소수 [math(z)]의 실수 부분, 허수 부분이다. == 다항정리 == 이항정리는 항이 2개일 때 사용한다면, 다항정리는 항이 3개 이상일 때 사용한다. 다음과 같은 꼴의 다항식을 고려하자. {{{#!wiki style="text-align: center" [br][math(\displaystyle (x_{1}+x_{2}+x_{3}+\cdots+x_{m})^{n} )] }}} [math(x_{1}^{n_{1}}x_{2}^{n_{2}} \cdot \cdots \cdot x_{m}^{n_{n}})] (단, [math(\sum_{k=1}^{n}n_{k}=n)])의 계수를 구하고 싶다면, 이항정리 때의 논법과 유사하게 [math(x_{1} \sim x_{n})]을 중복을 허락하여 일렬로 배열하는 경우의 수와 같으므로 그 계수는 다음과 같다. {{{#!wiki style="text-align: center" [br][math(\displaystyle \frac{n!}{n_{1}! n_{2}! n_{3}! \cdot \cdots \cdot n_{n}!} )] }}} 따라서 다항정리는 다음과 같다. {{{#!wiki style="text-align: center" [br][math(\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})] }}} == 일반화된 이항계수와 뉴턴의 이항정리 == 고교과정을 넘어서면, [math(\binom{n}{r})] 중 [math(n)]이 정수가 아닐 때도 정의되기 때문에 이항정리를 일반화할 수 있다. 다만, 여전히 [math(r)]이 음이 아닌 정수이어야 한다. 따라서 다음의 조합의 정의에 따라 {{{#!wiki style="text-align: center" [br][math(\displaystyle \binom{n}{r}=\frac{n(n-1)(n-2)\cdot \cdots \cdot (n-r+1)}{r!} )] }}} [math(n=b/a)]일 때의 이항계수는 {{{#!wiki style="text-align: center" [br][math(\displaystyle \binom{b/a}{r}=\frac{b!_{a}}{r!a^{r}(b-ar)!_{a}} )] }}} 로 일반화된다. 여기서 [math(N!_{p})]는 [math(p)]중 계승으로 정의되고, {{{#!wiki style="text-align: center" [br][math(\displaystyle N!_{p} \equiv \prod_{m=0}^{\lfloor\left(N-1\right)/p\rfloor} \left(N-mp\right) )] }}} 혹은 {{{#!wiki style="text-align: center" [br][math(\displaystyle N!_{p} \equiv \prod^{\forall{g}\equiv N\pmod{p}} g )][* [math(g)]는 법 [math(p)]에 대해서 [math(N)] 이하의 0을 포함하는 모든 양의 정수 중 [math(N)]과 합동인 정수들의 곱] }}} 으로 정의된다. [[뉴턴]]은 이를 이용해서 이항정리의 일반화된 버전을 증명하였는데, [[실수]] 혹은 [[복소수]] [math(z)]에 대하여 다음의 전개식 {{{#!wiki style="text-align: center" [br][math(\displaystyle \displaystyle (z+1)^n = \sum_{r=0}^{\infty} \binom{n}{r} z^r )] }}} 이 성립한다는 것이 그것이다. 증명은 [[테일러 정리]]를 사용하면 바로 나오게 된다.[* 다만, 그 전에 실수 혹은 복소수 지수가 무엇인지 엄밀한 정의가 필요하긴 하다.] 사실 이 이항정리 자체보다는 더 큰 의미를 갖는 것은 이항계수 성질의 확장이다. 파스칼 항등식, 하키스틱 성질 등등 이항계수에서 성립하는 성질들 대부분은 (확장할 수 있으면) 일반화된 이항계수에서 무조건 성립한다. 어찌 보면 당연한 게 이항계수도 어쨌든 [math(n)]에 대한 [[다항식]]이므로, [[다항식]] 등식이 양의 정수값에 대해 같은 값을 가진다면 [[항등식]]이 되는 게 맞다. 하지만 실제로 [math(n)]에 음의 정수나 유리수 등을 넣어서, [[카탈란 수]]나 중복조합 등등을 유의미하게 계산해내고, 이들의 성질을 자연수에서 성립하는 이항계수 성질의 유추로 증명하는 건 단순히 조합만으로는 납득하기 힘든 강력한 도구가 되곤 한다. 만약 [math(n)], [math(r)]이 모두 정수가 아닐 경우[* 물론 [math(n)], [math(r)]은 0보다 커야 한다.] [[베타 함수]]로 이항계수를 정의해야 한다. == [[1학년의 꿈]] == [include(틀:상세 내용, 문서명=1학년의 꿈)] == 관련 문서 == * [[경우의 수]] * [[순열]] * [[조합]] * [[파스칼의 삼각형]] * [[베타 함수]] [[분류:이산수학]][[분류:해석학(수학)]][[분류:대수학]][[분류:수학 용어]][[분류:한자어]][[분류:나무위키 수학 프로젝트]]