1. 개요
binomial theorem ・ 二項定理
[math((a+b)^{n})]([math(n)]은 음이 아닌 정수)의 꼴을 전개할 때 쓰이는 정리이다. 이항정리의 '이항'은 '두 개의 항(二項)'이라는 뜻이며, '항을 옮긴다'(移項)는 뜻이 아니다.
이것의 증명에는 파스칼의 정리를 이용하는 방법과 테일러 급수를 이용하거나, 경우의 수를 이용하는 방법이 있다. 이 문서에서는 마지막 방법을 쓴다.
이 문서에서 조합은 [math({}_{n}mathrm{C}_{r})] 대신 국제적으로 많이 사용되는 [math(binom{n}{r} )]로 표기했다.
[math((a+b)^{n})]([math(n)]은 음이 아닌 정수)의 꼴을 전개할 때 쓰이는 정리이다. 이항정리의 '이항'은 '두 개의 항(二項)'이라는 뜻이며, '항을 옮긴다'(移項)는 뜻이 아니다.
이것의 증명에는 파스칼의 정리를 이용하는 방법과 테일러 급수를 이용하거나, 경우의 수를 이용하는 방법이 있다. 이 문서에서는 마지막 방법을 쓴다.
이 문서에서 조합은 [math({}_{n}mathrm{C}_{r})] 대신 국제적으로 많이 사용되는 [math(binom{n}{r} )]로 표기했다.
1.1. 이항계수
이항계수(binomial coefficient)란, [math((a+b)^{n})]의 꼴의 다항식을 전개했을 때, [math(a^{r}b^{n-r})]([math(0 leq r leq n)]인 정수)의 계수를 의미하며, 다음과 같다.
[math(displaystyle binom{n}{r}=frac{n!}{r!(n-r)!} )]
이것의 증명은 다음을 이용하면 된다.
[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)]개 배열하는 경우의 수와 같다.[1] 따라서
[math(displaystyle frac{n!}{r!(n-r)!} )]
이고, 이것은 곧 조합의 정의와 같으므로 [math(a^{r}b^{n-r})]의 계수는 다음과 같다.
[math(displaystyle binom{n}{r} )]
[math(displaystyle binom{n}{r}=frac{n!}{r!(n-r)!} )]
이것의 증명은 다음을 이용하면 된다.
[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)]개 배열하는 경우의 수와 같다.[1] 따라서
[math(displaystyle frac{n!}{r!(n-r)!} )]
이고, 이것은 곧 조합의 정의와 같으므로 [math(a^{r}b^{n-r})]의 계수는 다음과 같다.
[math(displaystyle binom{n}{r} )]
1.2. 이항정리
따라서 [math((a+b)^{n})]의 꼴의 다항식을 전개하면 다음과 같은데, 이를 이항정리라 한다.
[math(displaystyle (a+b)^{n}=sum_{r=0}^{n} binom{n}{r} a^{r}b^{n-r} )]
[math(displaystyle (a+b)^{n}=sum_{r=0}^{n} binom{n}{r} a^{r}b^{n-r} )]
2. 이항계수의 성질
아래는 고교과정 수준에서 이항정리를 이용해 얻을 수 있는 이항계수의 성질들이다.[2] 등의 다양한 이항계수 항등식들이 빠져 있다.] 일종의 조합론에서 쓰이는 생성함수 테크닉에 가깝지만, 교과과정에서는 당연히 '생성함수'라는 말을 언급하진 않는다.
아래의 문단의 결과를 모두 정리하면 다음과 같다.
아래의 문단의 결과를 모두 정리하면 다음과 같다.
- [math(displaystyle sum_{r=0}^nbinom{n}{r}=2^n)]
- [math(displaystyle sum_{r=0}^nleft(-1right)^rbinom{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}^nrbinom{n}{r}=n2^{n-1})]
- [math(displaystyle sum_{r=0}^nr^2binom{n}{r}=nleft(n+1right)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)]
2.1. 성질 1
다항식 [math((x+1)^{n})]을 이항정리로 나타내면
[math(displaystyle (x+1)^{n}=sum_{r=0}^{n} binom{n}{r} x^{r} )]
이것은 항등식이므로 [math(x)]에 무엇을 대입하여도 성립한다. [math(x=1)]을 대입하면,
[math(displaystyle 2^{n}=sum_{r=0}^{n} binom{n}{r} qquad cdots ; text{(a)} )]
이번에는 [math(x=-1)]을 대입하면,
[math(displaystyle 0=sum_{r=0}^{n} binom{n}{r}(-1)^{r} qquad cdots ; text{(b)} )]
[math( (text{(a)}+text{(b)})/2 )]를 하면, 홀수 번째 항의 합이 된다.
[math(displaystyle 2^{n-1}= binom{n}{0}+binom{n}{2}+binom{n}{4}+cdots)]
[math( (text{(a)}-text{(b)})/2 )]를 하면, 짝수 번째 항의 합이 된다.
[math(displaystyle 2^{n-1}= binom{n}{1}+binom{n}{3}+binom{n}{5}+cdots)]
[math(displaystyle (x+1)^{n}=sum_{r=0}^{n} binom{n}{r} x^{r} )]
이것은 항등식이므로 [math(x)]에 무엇을 대입하여도 성립한다. [math(x=1)]을 대입하면,
[math(displaystyle 2^{n}=sum_{r=0}^{n} binom{n}{r} qquad cdots ; text{(a)} )]
이번에는 [math(x=-1)]을 대입하면,
[math(displaystyle 0=sum_{r=0}^{n} binom{n}{r}(-1)^{r} qquad cdots ; text{(b)} )]
[math( (text{(a)}+text{(b)})/2 )]를 하면, 홀수 번째 항의 합이 된다.
[math(displaystyle 2^{n-1}= binom{n}{0}+binom{n}{2}+binom{n}{4}+cdots)]
[math( (text{(a)}-text{(b)})/2 )]를 하면, 짝수 번째 항의 합이 된다.
[math(displaystyle 2^{n-1}= binom{n}{1}+binom{n}{3}+binom{n}{5}+cdots)]
2.2. 성질 2
이번에는 다항식 [math((x+1)^{2n})]을 보자.
[math(displaystyle (x+1)^{2n}=(x+1)^{n}(x+1)^{n})]
양변의 [math(n)]차항의 계수를 비교하면,
[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( becausebinom{n}{n-r}=binom{n}{r} right)end{aligned})]
[math(displaystyle (x+1)^{2n}=(x+1)^{n}(x+1)^{n})]
양변의 [math(n)]차항의 계수를 비교하면,
[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( becausebinom{n}{n-r}=binom{n}{r} right)end{aligned})]
2.3. 성질 3
[math(displaystyle binom{n}{r}=binom{n-1}{r-1}+binom{n-1}{r} )]
위의 파스칼의 정리를 사용하여도 여러 성질이 유도된다.
[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} )]
을 증명하면 아래와 같다.
[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} )]
비슷한 방법으로 다음을 증명할 수 있다.
[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( becausedisplaystyle binom{n}{0}=binom{n+1}{0} right) \ \ thereforedisplaystyle sum_{k=0}^{n} binom{n+k}{r}&=binom{n+r+1}{r} end{aligned} )]
2.4. 성질 4
2.5. 성질 5
이번에는 [math((1+x)^{n})]을 미분해 보자.
[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)]을 대입하면
[math(displaystyle sum_{r=0}^{n} r binom{n}{r}=2^{n-1}n )]
한편 [math( text{(c)})]에 [math(x=-1)]을 대입하면
[math(displaystyle sum_{r=0}^{n} r binom{n}{r} (-1)^{r-1}=0 )]
[math( text{(c)})]를 한 번 더 미분하여 [math(x=1)]을 대입하면
[math(displaystyle sum_{r=0}^{n} r^{2} binom{n}{r}=2^{n-2}n(n+1) )]
[math(displaystyle (x+1)^{n}=sum_{r=0}^{n} binom{n}{r} x^{r} )]
을 적분하여 [math(x=1)]을 대입하면
[math(displaystyle sum_{r=0}^{n} dfrac 1 {r+1} binom{n}{r} x^{r+1} = dfrac 1 {n+1} (x+1)^{n+1})]
[math(displaystyle sum_{r=0}^{n} dfrac 1 {r+1} binom{n}{r} = dfrac 1 {n+1} 2^{n+1})]
[math(x=-1)]을 대입하면
[math(displaystyle sum_{r=0}^{n} (-1)^{r+1} dfrac 1 {r+1} binom{n}{r} = 0)]
한편,
[math(displaystyle (x+1)^{n}=sum_{r=0}^{n} binom{n}{r} x^{r} )]
식에 허수단위 [math(displaystyle i)]를 대입하면
[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})]
위 결과는 아래와 같이 정리할 수 있다.
[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)]의 실수 부분, 허수 부분이다.
[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)]을 대입하면
[math(displaystyle sum_{r=0}^{n} r binom{n}{r}=2^{n-1}n )]
한편 [math( text{(c)})]에 [math(x=-1)]을 대입하면
[math(displaystyle sum_{r=0}^{n} r binom{n}{r} (-1)^{r-1}=0 )]
[math( text{(c)})]를 한 번 더 미분하여 [math(x=1)]을 대입하면
[math(displaystyle sum_{r=0}^{n} r^{2} binom{n}{r}=2^{n-2}n(n+1) )]
[math(displaystyle (x+1)^{n}=sum_{r=0}^{n} binom{n}{r} x^{r} )]
을 적분하여 [math(x=1)]을 대입하면
[math(displaystyle sum_{r=0}^{n} dfrac 1 {r+1} binom{n}{r} x^{r+1} = dfrac 1 {n+1} (x+1)^{n+1})]
[math(displaystyle sum_{r=0}^{n} dfrac 1 {r+1} binom{n}{r} = dfrac 1 {n+1} 2^{n+1})]
[math(x=-1)]을 대입하면
[math(displaystyle sum_{r=0}^{n} (-1)^{r+1} dfrac 1 {r+1} binom{n}{r} = 0)]
한편,
[math(displaystyle (x+1)^{n}=sum_{r=0}^{n} binom{n}{r} x^{r} )]
식에 허수단위 [math(displaystyle i)]를 대입하면
[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})]
위 결과는 아래와 같이 정리할 수 있다.
[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)]의 실수 부분, 허수 부분이다.
3. 다항정리
이항정리는 항이 2개일 때 사용한다면, 다항정리는 항이 3개 이상일 때 사용한다. 다음과 같은 꼴의 다항식을 고려하자.
[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})]을 중복을 허락하여 일렬로 배열하는 경우의 수와 같으므로 그 계수는 다음과 같다.
[math(displaystyle frac{n!}{n_{1}! n_{2}! n_{3}! cdot cdots cdot n_{n}!} )]
따라서 다항정리는 다음과 같다.
[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(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})]을 중복을 허락하여 일렬로 배열하는 경우의 수와 같으므로 그 계수는 다음과 같다.
[math(displaystyle frac{n!}{n_{1}! n_{2}! n_{3}! cdot cdots cdot n_{n}!} )]
따라서 다항정리는 다음과 같다.
[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})]
4. 일반화된 이항계수와 뉴턴의 이항정리
고교과정을 넘어서면, [math(binom{n}{r})] 중 [math(n)]이 정수가 아닐 때도 정의되기 때문에 이항정리를 일반화할 수 있다. 다만, 여전히 [math(r)]이 음이 아닌 정수이어야 한다. 따라서 다음의 조합의 정의에 따라
[math(displaystyle binom{n}{r}=frac{n(n-1)(n-2)cdot cdots cdot (n-r+1)}{r!} )]
[math(n=b/a)]일 때의 이항계수는
[math(displaystyle binom{b/a}{r}=frac{b!_{a}}{r!a^{r}(b-ar)!_{a}} )]
로 일반화된다. 여기서 [math(N!_{p})]는 [math(p)]중 계승으로 정의되고,
[math(displaystyle N!_{p} equiv prod_{m=0}^{lfloorleft(N-1right)/prfloor} left(N-mpright) )]
혹은
[math(displaystyle N!_{p} equiv prod^{forall{g}equiv Npmod{p}} g )][3]는 법 [math(p)]에 대해서 [math(N)] 이하의 0을 포함하는 모든 양의 정수 중 [math(N)]과 합동인 정수들의 곱]
으로 정의된다.
뉴턴은 이를 이용해서 이항정리의 일반화된 버전을 증명하였는데, 실수 혹은 복소수 [math(z)]에 대하여 다음의 전개식
[math(displaystyle displaystyle (z+1)^n = sum_{r=0}^{infty} binom{n}{r} z^r )]
이 성립한다는 것이 그것이다. 증명은 테일러 정리를 사용하면 바로 나오게 된다.[4]
사실 이 이항정리 자체보다는 더 큰 의미를 갖는 것은 이항계수 성질의 확장이다. 파스칼 항등식, 하키스틱 성질 등등 이항계수에서 성립하는 성질들 대부분은 (확장할 수 있으면) 일반화된 이항계수에서 무조건 성립한다. 어찌 보면 당연한 게 이항계수도 어쨌든 [math(n)]에 대한 다항식이므로, 다항식 등식이 양의 정수값에 대해 같은 값을 가진다면 항등식이 되는 게 맞다. 하지만 실제로 [math(n)]에 음의 정수나 유리수 등을 넣어서, 카탈란 수나 중복조합 등등을 유의미하게 계산해내고, 이들의 성질을 자연수에서 성립하는 이항계수 성질의 유추로 증명하는 건 단순히 조합만으로는 납득하기 힘든 강력한 도구가 되곤 한다.
만약 [math(n)], [math(r)]이 모두 정수가 아닐 경우[5], [math(r)]은 0보다 커야 한다.] 베타 함수로 이항계수를 정의해야 한다.
[math(displaystyle binom{n}{r}=frac{n(n-1)(n-2)cdot cdots cdot (n-r+1)}{r!} )]
[math(n=b/a)]일 때의 이항계수는
[math(displaystyle binom{b/a}{r}=frac{b!_{a}}{r!a^{r}(b-ar)!_{a}} )]
로 일반화된다. 여기서 [math(N!_{p})]는 [math(p)]중 계승으로 정의되고,
[math(displaystyle N!_{p} equiv prod_{m=0}^{lfloorleft(N-1right)/prfloor} left(N-mpright) )]
혹은
[math(displaystyle N!_{p} equiv prod^{forall{g}equiv Npmod{p}} g )][3]는 법 [math(p)]에 대해서 [math(N)] 이하의 0을 포함하는 모든 양의 정수 중 [math(N)]과 합동인 정수들의 곱]
으로 정의된다.
뉴턴은 이를 이용해서 이항정리의 일반화된 버전을 증명하였는데, 실수 혹은 복소수 [math(z)]에 대하여 다음의 전개식
[math(displaystyle displaystyle (z+1)^n = sum_{r=0}^{infty} binom{n}{r} z^r )]
이 성립한다는 것이 그것이다. 증명은 테일러 정리를 사용하면 바로 나오게 된다.[4]
사실 이 이항정리 자체보다는 더 큰 의미를 갖는 것은 이항계수 성질의 확장이다. 파스칼 항등식, 하키스틱 성질 등등 이항계수에서 성립하는 성질들 대부분은 (확장할 수 있으면) 일반화된 이항계수에서 무조건 성립한다. 어찌 보면 당연한 게 이항계수도 어쨌든 [math(n)]에 대한 다항식이므로, 다항식 등식이 양의 정수값에 대해 같은 값을 가진다면 항등식이 되는 게 맞다. 하지만 실제로 [math(n)]에 음의 정수나 유리수 등을 넣어서, 카탈란 수나 중복조합 등등을 유의미하게 계산해내고, 이들의 성질을 자연수에서 성립하는 이항계수 성질의 유추로 증명하는 건 단순히 조합만으로는 납득하기 힘든 강력한 도구가 되곤 한다.
만약 [math(n)], [math(r)]이 모두 정수가 아닐 경우[5], [math(r)]은 0보다 커야 한다.] 베타 함수로 이항계수를 정의해야 한다.