| 이산수학 Discrete Mathematics | ||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" | 이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론(수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열(뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의(점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수(/공식) · 순열(완전 순열 · 염주 순열) · 치환 · 분할(분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기(해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리(파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 (예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
1. 개요
二項定理 / binomial theorem이항정리란, [math((a+b)^n)](단, [math(n)]은 음이 아닌 정수)의 꼴을 전개할 때 쓰이는 정리이다. 이항정리의 '이항'은 '두 개의 항(二項)'이라는 뜻이며, '항을 옮긴다'(移項)는 뜻이 아니다.[1]
이것의 증명에는 파스칼의 정리를 이용하는 방법과, 테일러 급수를 이용하거나 경우의 수를 이용하는 방법이 있다. 이 문서에서는 마지막 방법을 쓴다.
이항정리를 더욱 확장하면 다항정리가 되며, 이항정리와 다항정리는 모두 곱미분의 일반화인 라이프니츠 법칙과 형태가 매우 유사하다.
이 문서에서 조합의 기호는 국내 고교 교육과정에서 사용하는 [math({}_n{\rm C}_r)] 대신에 국제적으로 많이 사용하는 [math(\binom nr)]로 표기했다.
1.1. 이항계수
二項係數 / binomial coefficient[math((a+b)^n)] 꼴의 다항식을 전개했을 때 [math(a^rb^{n-r})] (단, [math(n)]과 [math(r)]은 [math(0\leq r\leq n)]인 정수)의 계수를 의미하며, 다음과 같다.
[math(\begin{aligned} \dbinom nr \!&= \dfrac{n!}{r!\,(n-r)!} \\ &= \dfrac{n(n-1)(n-2)\cdots(n-r+2)(n-r+1)}{r!} \\ &= \dfrac{n(n-1)(n-2)\cdots(r+2)(r+1)}{(n-r)!} \end{aligned} )] |
[math(
(a+b)^n = \underbrace{(a+b)(a+b)\cdots(a+b)}_{n\text{개의 항}}
)]
[math(a^rb^{n-r})]의 계수는 곧 [math(r)]개의 [math(a)]와 [math((n-r))]개의 [math(b)] 이렇게 총 [math(n)]개의 문자를 배열하는 경우의 수와 같다. 이것은 곧 같은 것이 있는 순열이므로
[math(
\dfrac{n!}{r!\,(n-r)!}
)]
이고, 이것은 조합의 정의와 같으므로 [math(a^rb^{n-r})]의 계수는 다음과 같다.
[math(
\dbinom nr
)]
1.2. 이항정리
따라서 [math((a+b)^n)]의 꼴의 다항식을 전개하면 다음과 같은데, 이를 이항정리라 한다.[math(\displaystyle
(a+b)^n = \sum_{r=0}^n \!\binom nr a^{n-r}b^r
)]
2. 이항계수의 성질
아래는 고교과정 수준에서 이항정리를 이용해 얻을 수 있는 이항계수의 성질들이다.[2] 일종의 조합론에서 쓰이는 생성함수 테크닉에 가깝지만, 교과과정에서는 당연히 '생성함수'라는 말을 언급하진 않는다.아래의 문단들의 결과를 모두 정리하면 다음과 같다.
- [math(\displaystyle \sum_{r=0}^n \binom nr = 2^n)]
- [math(\displaystyle \sum_{r=0}^n (-1)^r \binom nr = 0)]
- [math(\displaystyle \binom n0 +\binom n2 +\binom n4 +\cdots = 2^{n-1})]
- [math(\displaystyle \binom n1 +\binom n3 +\binom n5 +\cdots = 2^{n-1})]
- [math(\displaystyle \binom{2n}n = \sum_{r=0}^n \binom nr^{\!2})]
- [math(\displaystyle \sum_{k=0}^n \binom kr = \binom{n+1}{r+1})]
- [math(\displaystyle \sum_{k=0}^r \binom{n+k}k = \binom{n+r+1}r)]
- [math(\displaystyle \binom n0 +\binom{n-1}1 +\binom{n-2}2 +\cdots +\binom1{n-1} +\binom0{n} = F_n)] ([math(F_n)]은 피보나치 수열)
- [math(\displaystyle \sum_{r=0}^n r \binom nr = n \cdot 2^{n-1})]
- [math(\displaystyle \sum_{r=0}^n r^2 \binom nr = n(n+1)2^{n-2})]
- [math(\displaystyle \sum_{r=0}^n \frac1{r+1} \binom nr = \frac1{n+1} \,(2^{n+1}-1))]
- [math(\displaystyle \sum_{r=0}^n (-1)^{r+1} \frac1{r+1} \binom nr = 0)]
2.1. 성질 1
다항식 [math((x+1)^n)]을 이항정리로 나타내면[math(\displaystyle (x+1)^n=\sum_{r=0}^n \binom nr x^{r} )]
이것은 [math(x)]에 관한 항등식이므로 [math(x)]에 무엇을 대입하여도 성립한다. [math(x=1)]을 대입하면,
[math(\displaystyle 2^{n}=\sum_{r=0}^n \binom nr \qquad \cdots \; \text{(a)} )]
이번에는 [math(x=-1)]을 대입하면,
[math(\displaystyle 0=\sum_{r=0}^n \binom nr(-1)^{r} \qquad \cdots \; \text{(b)} )]
[math( (\text{(a)}+\text{(b)})/2 )]를 하면, 홀수 번째 항의 합이 된다.
[math(\displaystyle 2^{n-1}= \binom n0+\binom n2+\binom n4+\cdots)]
[math( (\text{(a)}-\text{(b)})/2 )]를 하면, 짝수 번째 항의 합이 된다.
[math(\displaystyle 2^{n-1}= \binom n1+\binom n3+\binom n5+\cdots)]
곧, 홀수 번째 항의 합과 짝수 번째 항의 합은 [math(2^{n-1})]으로 같으며, 이에 따라 전체 항의 합은 [math(2^n)]이다.
2.1.1. 참고: 부분집합의 개수
원소가 [math(n)]개인 집합의 부분집합의 개수를 세어 위 성질을 확인할 수도 있다. 전체집합[math(S=\{s_1,\,s_2,\,\cdots,\,s_n\})]
의 임의의 부분집합의 원소의 개수를 [math(r)]라 하면 [math(0\leq r\leq n)]이고, 원소의 개수에 따른 부분집합의 개수는 전체집합 [math(S)]의 [math(n)]개의 원소 중 [math(r)]개를 뽑는 경우의 수이므로 [math(\binom nr)]이다. 따라서 부분집합의 개수는 다음과 같다.
[math(\displaystyle\binom n0+\binom n1+\cdots+\binom nn=\displaystyle\sum_{r=0}^n\binom nr)]
그런데 다른 방법으로 부분집합의 개수를 구할 수도 있다. 부분집합을 만들 때는 전체집합의 각 원소마다 해당 원소를 부분집합에 포함시킬지 말지의 두 가지 경우가 있다. 다시 말해서 부분집합에 [math(s_1)]을 포함시킬 수도 있고, 그렇지 않을 수도 있으며 이러한 논리는 [math(s_n)]까지 총 [math(n)]번 적용된다는 것이다. 그래서 모든 원소를 포함시키지 않으면 공집합이 되고, 포함시키면 전체집합이 되는 식이다. 결국 부분집합의 개수는 경우의 수의 곱의 법칙에 따라 [math(2^n)]이 된다. 이 결과는 위에서 알아본 다음 성질을 암시한다.
[math(\displaystyle 2^{n}=\sum_{r=0}^n \binom nr)]
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 n0\binom n{n}+\binom n1\binom n{n-1}+\cdots+\binom n{n}\binom n0\\&={\binom n0}^{2}+{\binom n1}^{2}+{\binom n2}^{2}+\cdots+{\binom n{n}}^{2}\\&=\sum_{r=0}^n {\binom nr}^{2} \quad \left( \because\binom n{n-r}=\binom nr \right)\end{aligned})]
2.3. 성질 3
[math(\displaystyle \binom nr=\binom{n-1}{r-1}+\binom{n-1}{r} )]
위의 파스칼의 정리를 사용하여도 여러 성질이 유도된다.
[math(\displaystyle \sum_{k=0}^n \binom kr=\binom0{r}+\binom1{r}+\binom{2}{r}+\cdots+\binom nr=\binom{n+1}{r+1} )]
을 증명하면 아래와 같다.
[math(\displaystyle \displaystyle \begin{aligned} &\underbrace{\binom0{r+1}+\binom0{r}}+\binom1{r}+\binom{2}{r}+\cdots+\binom nr
\\&=\,\,\,\underbrace{\binom1{r+1}+\binom1{r}}+\binom{2}{r}+\cdots+\binom nr
\\&=\,\,\,\quad \,\,\,\, \underbrace{\binom{2}{r+1}+\binom{2}{r}}_{ \binom{3}{r+1}}+\cdots+\binom nr
\\&=\cdots
\\&= \underbrace{\binom n{r+1}+\binom nr}
\\&= \,\,\,\quad \,\binom{n+1}{r+1} \end{aligned} )]
비슷한 방법으로 다음을 증명할 수 있다.
[math(\displaystyle \begin{aligned} \binom n0+\binom n1+\binom n2+\cdots+\binom nr &=\binom{n+1}{0}+\binom n1+\binom n2+\cdots+\binom nr \\ &=\binom{n+r+1}r \quad \left( \because\displaystyle \binom n0=\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
[math(\displaystyle F_{n} = \binom n0+\binom{n-1}1+\binom{n-2}2+\cdots+\binom1{n-1}+\binom0{n} )]
위와 같이 정의되는 수열 [math(F_{n})]은 피보나치 수열이다. [math(F_{0}=F_{1}=1)]이고, 파스칼의 정리에 의하여 다음이 성립한다.
[math(F_{n}=F_{n-1}+F_{n-2})]
2.5. 성질 5
이번에는 [math((1+x)^{n})]을 미분해 보자.[math(\displaystyle \sum_{r=0}^n r \binom nr {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 nr=n\cdot2^{n-1} )]
한편 [math( \text{(c)})]에 [math(x=-1)]을 대입하면
[math(\displaystyle \sum_{r=0}^n r \binom nr (-1)^{r-1}=0 )]
[math( \text{(c)})]를 한 번 더 미분하여 [math(x=1)]을 대입하면
[math(\displaystyle \sum_{r=0}^n r^{2} \binom nr=n(n+1)2^{n-2} )]
[math(\displaystyle (x+1)^n=\sum_{r=0}^n \binom nr x^{r} )]
을 적분하여 [math(x=1)]을 대입하면
[math(\displaystyle \sum_{r=0}^n \dfrac1{r+1} \binom nr x^{r+1} = \dfrac1{n+1} (x+1)^{n+1})]
[math(\displaystyle \sum_{r=0}^n \dfrac1{r+1} \binom nr = \dfrac1{n+1} 2^{n+1})]
[math(x=-1)]을 대입하면
[math(\displaystyle \sum_{r=0}^n (-1)^{r+1} \dfrac1{r+1} \binom nr = 0)]
한편,
[math(\displaystyle (x+1)^n=\sum_{r=0}^n \binom nr x^{r} )]
식에 허수단위 [math(\displaystyle i)]를 대입하면
[math(\displaystyle \begin{aligned} (i+1)^{n}&=\sum_{r=0}^n \binom nr i^{r}\\& = \left \{ \binom n0 - \binom n2 + \binom n4 - \cdots \right \} +\left \{ \binom n1 - \binom n3 + \binom n5 - \cdots \right \}i \end{aligned})]
위 결과는 아래와 같이 정리할 수 있다.
[math(\displaystyle \begin{aligned} \Re((i+1)^{n})&= \binom n0 - \binom n2 + \binom n4 - \binom n{6} + \cdots\\&=\sum_{r=0}^{-\lceil-n/2\rceil}(-1)^r\binom n{2r} \\ \Im((i+1)^{n})&=\binom n1 - \binom n3 + \binom n5 - \binom n{7} + \cdots\\&=\sum_{r=0}^{\lceil n/2\rceil}(-1)^r\binom n{2r+1}\end{aligned})]
이때, [math(\Re(z))], [math(\Im(z))]는 각각 복소수 [math(z)]의 실수 부분, 허수 부분이다.
다만, 〈교육부 고시 제2015-74호 [별책 8] 수학과 교육과정〉 p. 97에서 '허수단위 [math(i)]가 포함된 이항정리에 관한 문제는 다루지 않는다.'라고 명시되어 있으므로 고등학교 시험에서 이를 물을 수 없다.
2.6. 이항계수의 역수의 합
[math(a_n=\displaystyle\sum_{k=0}^n {\displaystyle \binom nk}^{-1})]
이라 하면 수열 [math(\{a_n\})]은 이항계수의 역수의 합이다. [math(a_1)]부터 차례로 계산해 보면 다음과 같다.
[math(\begin{aligned}a_1&=\dfrac11+\dfrac11=2\\ a_2&=\dfrac11+\dfrac12+\dfrac11=\dfrac52\\ a_3&=\dfrac11+\dfrac13+\dfrac13+\dfrac11=\dfrac83\\ a_4&=\dfrac11+\dfrac14+\dfrac16+\dfrac14+\dfrac16=\dfrac83\\ a_5&=\dfrac11+\dfrac15+\dfrac1{10}+\dfrac1{10}+\dfrac15+\dfrac11=\dfrac{13}5\\ a_6&=\dfrac11+\dfrac16+\dfrac1{15}+\dfrac1{20}+\dfrac1{15}+\dfrac16+\dfrac11=\dfrac{151}{60}\\ \vdots \,\,&=\,\, \vdots\end{aligned})]
위와 같이 [math(n=3)] 또는 [math(n=4)]일 때 최댓값 [math(8/3)]을 가지며, 그 이후로는 값이 계속 감소하여 [math(2)]에 수렴한다. 즉, [math(\displaystyle\lim_{n\to\infty}a_n=2)]이다.
[math(\{a_n\})]의 점화식은 다음과 같다.
[math(a_n=\dfrac{n+1}{2n}a_{n-1}+1\quad(n\geq2))]
[math(\{a_n\})]의 일반항은 다음과 같다.
[math(a_n=\dfrac{n+1}{2^{n+1}}\displaystyle\sum_{k=1}^n\frac{2^k}k)]
- 일반항·극한 증명 [펼치기·접기]
- ----
우선 [math(\binom nk=\dfrac n{n-k}\binom{n-1}k)]에서[math(\dfrac1{\binom nk}=\dfrac{n-k}n\dfrac1{\binom{n-1}k}\;\cdots\,(1))]
이고 [math(\binom n{k+1}=\dfrac n{k+1}\binom{n-1}k)]에서[math(\dfrac1{\binom n{k+1}}=\dfrac{k+1}n\dfrac1{\binom{n-1}k}\;\cdots\,(2))]
[math((1))]과 [math((2))]를 변끼리 합하여 [math(k=0)]부터 [math(n-1)]까지의 합을 구하면[math(\begin{aligned}\dfrac1{\binom nk}+\dfrac1{\binom n{k+1}}&=\dfrac{n+1}n\dfrac1{\binom{n-1}k}\\\rightarrow\displaystyle\sum_{k=0}^{n-1}\left[\dfrac1{\binom nk}+\dfrac1{\binom n{k+1}}\right]&=\dfrac{n+1}n\sum_{k=0}^{n-1}\dfrac1{\binom{n-1}k}\end{aligned})]
[math(1/\binom n0+1/\binom nn=2)]이므로 좌변과 우변에 각각 [math(1/\binom n0+1/\binom nn)]과 [math(2)]를 더하면[math(2\displaystyle\sum_{k=0}^n\dfrac1{\binom nk}=2+\dfrac{n+1}n\sum_{k=0}^{n-1}\dfrac1{\binom{n-1}k})]
양변에 [math(2^n/(n+1))]을 곱하면[math(\dfrac{2^{n+1}}{n+1}\displaystyle\sum_{k=0}^n\dfrac1{\binom nk}=\dfrac{2^{n+1}}{n+1}+\dfrac{2^n}n\sum_{k=0}^{n-1}\dfrac1{\binom{n-1}k}\;\cdots\,(3))]
여기에서 수열 [math(\{a_n\})]을[math(a_n=\dfrac{2^{n+1}}{n+1}\displaystyle\sum_{k=0}^n\dfrac1{\binom nk}\;\cdots\,(4))]
으로 정의하면 [math((3))]을 다음과 같이 수열의 귀납적 정의로 쓸 수 있다.[math(\begin{aligned}a_n&=\dfrac{2^{n+1}}{n+1}+a_{n-1}\\&\equiv f(n)+a_{n-1}\end{aligned})]
이를 통하여 [math(\{a_n\})]의 일반항을 구하자. 우선 [math(a_1)]의 값은[math(a_1=\dfrac{2^{1+1}}{1+1}\displaystyle\sum_{k=0}^1\dfrac1{\binom 1k}=4)]
이므로 다음이 성립한다.[math( \begin{aligned}
\cancel{a_2}&=f(2)+a_1 \\
\cancel{a_3}&=f(3)+\cancel{a_2} \\&\quad \; \; \vdots \\\cancel{a_{n-1}}&=f(n-1)+\cancel{a_{n-2}} \\
+\qquad a_n&=f(n)+\cancel{a_{n-1}} \\
\hline
\therefore a_n&=a_1+\displaystyle\sum_{k=2}^nf(k)\\&=4+\sum_{k=3}^nf(k-1)\;\cdots\,(5)\end{aligned})]
이때 [math(f(1-1))]과 [math(f(2-1))]의 합은[math(\begin{aligned}f(1-1)+f(2-1)&=f(0)+f(1)\\&=\dfrac{2^{0+1}}{0+1}+\dfrac{2^{1+1}}{1+1}=4\end{aligned})]
이므로 [math((5))]는 다음과 같다.[math(\begin{aligned}\dfrac1{\binom nk}&=4+\displaystyle\sum_{k=3}^nf(k-1)\\&=f(1-1)+f(2-1)+\sum_{k=3}^nf(k-1)\\&=\sum_{k=1}^nf(k-1)=\sum_{k=1}^n\dfrac{2^k}k\end{aligned})]
[math((3))]의 양변에 [math((n+1)/2^{n+1})]을 곱하면 이항계수의 역수의 합의 일반항이 도출된다.[math(\displaystyle\sum_{k=0}^n\dfrac1{\binom nk}=\dfrac{n+1}{2^{n+1}}\displaystyle\sum_{k=1}^n\frac{2^k}k)]
이제 [math(\displaystyle\lim_{n\to\infty}a_n)]의 값을 구하자. [math(2\leq k\leq n-2)]이면 [math(\binom nk\geq\binom n2)]이므로 [math(n\geq 4)]에 대하여
따라서 [math(n\geq 4)]에 대하여[math(\begin{aligned}\displaystyle\sum_{k=0}^n\dfrac1{\binom nk}&=\dfrac1{\binom n0}+\dfrac1{\binom n1}+\dfrac1{\binom n{n-1}}+\dfrac1{\binom nn}+\sum_{k=2}^{n-2}\dfrac1{\binom nk}\\&\leq2+\dfrac2n+\dfrac{n-3}{\binom n2}\\&\leq2+\dfrac2n+\dfrac2n=2+\dfrac4n\end{aligned})] [math(2+\dfrac2n\leq\displaystyle\sum_{k=0}^n\dfrac1{\binom nk}\leq2+\dfrac4n)]
이므로 조임 정리에 의하여 극한값은 다음과 같다.[math(\displaystyle\lim_{n\to\infty}a_n=\lim_{n\to\infty}\left(2+\dfrac2n\right)=\lim_{n\to\infty}\left(2+\dfrac4n\right)=2)]
극한값에 대한 다양한 증명들은 Calculate sums of inverses of binomial coefficients를 참고하자.
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})]
다만, 〈교육부 고시 제2015-74호 [별책 8] 수학과 교육과정〉 p. 97에서 '항이 세 개 이상인 다항정리에 관한 문제는 다루지 않는다.'라고 명시되어 있으므로 고등학교 시험에서 이를 물을 수 없다.
4. 일반화된 이항계수와 뉴턴의 이항정리
고교과정을 넘어서면 [math(n)]이 정수가 아닌 경우에 대해서도 [math(\dbinom nr)]을 정의할 수 있다. 우선 [math(n\in\;)][math(Z^{0+})], [math(k\in\Z^{0+})], [math(0\le k\le n)]에 대해 정의된 다음의 이항계수의 정의식을 보자.[math(\begin{aligned} \dbinom nk \!&= \dfrac{n!}{k!\,(n-k)!} \\ &= \dfrac{n(n-1)(n-2)\cdots(n-k+2)(n-k+1)}{k!} \end{aligned} )] |
[math(\begin{aligned} \dbinom nk \!= \dfrac{n^{\underline k}}{k!} = \dfrac{n(n-1)(n-2)\cdots(n-k+2)(n-k+1)}{k!} \end{aligned} )] |
[math(\begin{aligned} \dbinom nk \!= \dfrac{n^{\underline k}}{k!} = \dfrac{\Gamma(n+1)}{\Gamma(k+1)\,\Gamma(n-k+1)} \end{aligned} )] |
[math(\begin{aligned} \dbinom nk \!&= \dfrac{\Gamma(n+1)}{\Gamma(k+1)\,\Gamma(n-k+1)} \\ &= \dfrac{\Gamma(n+1)}{\Beta(k+1, n-k+1) \cdot \Gamma(n+2)} \\ &= \dfrac1{(n+1) \cdot \Beta(k+1, n-k+1)} \end{aligned} )] |
위의 확장된 정의들을 사용하면 분수 표기에 대한 이항계수를 계산할 수 있다. [math(n=\dfrac ba)]일 때의 이항계수는 다음과 같다. (단, [math(k)]와 [math(a)]는 자연수, [math(b)]는 정수)
[math(\displaystyle \begin{aligned}
\binom{b/a}k = \frac{b!_a}{k! \cdot a^k (b-ka)!_a}
\end{aligned} )]
|
[math(\displaystyle \begin{aligned}
N!_p &\equiv \prod_{m=0}^{\lfloor(N-1)/p\rfloor} (N-mp) \\
&\equiv \prod^{\forall g \equiv N (\operatorname{mod}p)} g
\end{aligned} )][3]
로 정의된다.
한편, 뉴턴은 확장된 정의를 이용해서 이항정리의 일반화된 버전을 증명하였는데, 바로 실수 혹은 복소수 [math(z)]에 대하여 전개식
[math(\displaystyle
(z+1)^n = \sum_{r=0}^\infty \!\binom nr z^r
)]
이 성립한다는 것이다. 증명은 테일러 정리를 사용하면 바로 나오게 된다.[4]
사실, 이 이항정리 자체보다 더 큰 의미를 갖는 것은 이항계수의 성질의 확장이다. 파스칼 항등식, 하키스틱 성질 등 이항계수에서 성립하는 성질들 대부분은 (확장할 수 있으면) 일반화된 이항계수에서 무조건 성립한다. 어찌 보면 당연한 게, 이항계수도 어쨌든 [math(n)]에 대한 다항식이므로, 다항식 등식이 양의 정수값에 대해 같은 값을 가진다면 항등식이 되는 게 맞기 때문이다. 하지만 실제로 [math(n)]에 음의 정수나 유리수 등을 넣어서 카탈랑 수나 중복조합 등을 유의미하게 계산해내고, 이들의 성질을 자연수에서 성립하는 이항계수의 성질의 유추로 증명하는 건 단순히 조합만으로는 납득하기 힘든 강력한 도구가 되곤 한다.
5. 아벨의 이항정리
- 다음 식을 아벨의 이항정리라고 부른다. (단, [math(n)]은 [math(0)] 이상의 정수, [math(a)]는 [math(0)]이 아닌 실수, [math(b)]와 [math(c)]는 임의의 실수)
&\sum_{k=0}^n \frac a{a+bk} \frac{(a+bk)^k}{k!} \frac{(c-bk)^{n-k}}{(n-k)!} \\
= \,&\frac a{n!} \sum_{k=0}^n \!\binom nk (a+bk)^{k-1} (c-bk)^{n-k} \\
= \,&\frac{(a+c)^n}{n!}
\end{aligned} )]}}}||
증명의 출처: https://www.combinatorics.org/ojs/index.php/eljc/article/view/v17i1n24
증명에 사용하기 위해 참고식 2개를 먼저 소개한다.
- 참고식 [math(A)]
{{{#!wiki style="text-align:center"
[math(\displaystyle \begin{aligned}
(c-bk)^{n-k} &= ((a+c)-(a+bk))^{n-k} \\
&= \sum_{m=0}^{n-k} \!\binom{n-k}m (-1)^m (a+bk)^m (a+c)^{n-k-m} \\
&= \sum_{m=k}^n \!\binom{n-k}{m-k} (-1)^{m-k} (a+bk)^{m-k} (a+c)^{n-m} \qquad \cdots \,(A)
\end{aligned} )]}}}
- 참고식 [math(B)]
자연수 [math(m)]에 대해 일반항이 [math(a_i = (a+bi)^{m-1})]인 수열 [math(\{a_i\})]를 생각하자. 그러면 [math(a_i)]는 [math((m-1))]차 다항식이고, 계차수열의 성질에 의해 제[math(p)]계 계차수열 [math(\{a_{p,i}\})]는 다음을 만족한다. - [math(1 \le p \le m-1)]이면 [math(a_{p,i})]는 [math((m-1-p))]차 다항식이고, [math(p>m-1)]이면 [math(a_{p,i}=0)]이다.
- [math(\displaystyle a_{p,i} = \sum_{k=0}^p (-1)^{p-k} \binom pk a_{i+k} = \sum_{k=0}^p (-1)^{p-k} \binom pk (a+b(i+k))^{m-1})]이다.
따라서 i.과 ii.에 의해 [math(\displaystyle a_{m,i} = 0 = \sum_{k=0}^m (-1)^{m-k} \binom mk (a+b(i+k))^{m-1})]이다. 여기에 [math(i=0)]을 대입하면 다음 식을 얻을 수 있다.
{{{#!wiki style="text-align:center"
[math(\displaystyle \begin{aligned}
\sum_{k=0}^m (-1)^{m-k} \binom mk (a+bk)^{m-1} = 0 \qquad \cdots \,(B)
\end{aligned} )]}}}
이제 위의 참고식들을 사용하여 정리를 증명해보자. 증명 과정 중 참고식을 사용한 경우, 등호 위에다가 해당 참고식의 알파벳을 적을 것이다. (예: [math(\overset{A}=)])
우선 [math(S)]를 다음과 같이 정의하자.
[math(\displaystyle \begin{aligned}
S = \sum_{k=0}^n \frac a{a+bk} \frac{(a+bk)^k}{k!} \frac{(c-bk)^{n-k}}{(n-k)!}
\end{aligned} )]
정리의 첫째 등호는 쉽게 증명 가능하다.
[math(\displaystyle \begin{aligned}
S &= \sum_{k=0}^n \frac a{a+bk} \frac{(a+bk)^k}{k!} \frac{(c-bk)^{n-k}}{(n-k)!} \\
&= \sum_{k=0}^n \frac a{n!} \frac{n!}{k!\,(n-k)!} (a+bk)^{k-1} (c-bk)^{n-k} \\
&= \frac a{n!} \sum_{k=0}^n \!\binom nk (a+bk)^{k-1} (c-bk)^{n-k} \qquad \blacksquare
\end{aligned} )]
여기에 참고식 [math(A)]를 사용하자.
[math(\displaystyle \begin{aligned}
S &= \frac a{n!} \sum_{k=0}^n \!\binom nk (a+bk)^{k-1} (c-bk)^{n-k} \\
&\overset{A}= \frac a{n!} \sum_{k=0}^n \!\binom nk (a+bk)^{k-1} \sum_{m=k}^n \!\binom{n-k}{m-k} (-1)^{m-k} (a+bk)^{m-k} (a+c)^{n-m} \\
&= \frac a{n!} \sum_{k=0}^n \sum_{m=k}^n (-1)^{m-k} \binom nk \!\binom{n-k}{m-k} (a+bk)^{m-1} (a+c)^{n-m} \\
\end{aligned} )]
여기서
[math(\displaystyle \begin{aligned}
\binom nk \!\binom{n-k}{m-k} \!&= \frac{n!}{k! \,(n-k)!} \times \frac{(n-k)!}{(m-k)! \,(n-m)!} \\
&= \frac{n!}{k! \,(m-k)! \,(n-m)!} \times \frac{m!}{m!} \\
&= \frac{n!}{m!\,(n-m)!} \frac{m!}{k!\,(m-k)!} \\
&= \!\binom nm \!\binom mk
\end{aligned} )]
이므로
[math(\displaystyle \begin{aligned}
S &= \frac a{n!} \sum_{k=0}^n \sum_{m=k}^n (-1)^{m-k} \binom nk \!\binom{n-k}{m-k} (a+bk)^{m-1} (a+c)^{n-m} \\
&= \frac a{n!} \sum_{k=0}^n \sum_{m=k}^n (-1)^{m-k} \binom nm \!\binom mk (a+bk)^{m-1} (a+c)^{n-m} \\
\end{aligned} )]
이고, 이중 시그마 [math(\displaystyle \sum_{k=0}^n \sum_{m=k}^n)]의 순서를 바꾸면 [math(\displaystyle \sum_{m=0}^n \sum_{k=0}^m)]이 되므로 [math(S)]는 다음과 같다.
[math(\displaystyle \begin{aligned}
S &= \frac a{n!} \sum_{m=0}^n \sum_{k=0}^m (-1)^{m-k} \binom nm \!\binom mk (a+bk)^{m-1} (a+c)^{n-m} \\
&= \frac a{n!} \sum_{m=0}^n \!\binom nm (a+c)^{n-m} \sum_{k=0}^m (-1)^{m-k} \binom mk (a+bk)^{m-1}
\end{aligned} )]
[math(S)]를 [math(m=0)]인 경우와 [math(m\ge1)]인 경우로 분리하면 둘째 등호도 증명을 완료할 수 있다.
[math(\displaystyle \begin{aligned}
S &= \frac a{n!} \binom n0 (a+c)^n (-1)^0 \binom00 a^{-1} +\frac a{n!} \sum_{m=1}^n \!\binom nm (a+c)^{n-m} \sum_{k=0}^m (-1)^{m-k} \binom mk (a+bk)^{m-1} \\
&\overset{B}= \frac a{n!} (a+c)^n a^{-1} +\frac a{n!} \sum_{m=1}^n \!\binom nm (a+c)^{n-m} \cdot 0 \\
&= \frac{(a+c)^n}{n!} \qquad \blacksquare
\end{aligned} )]
}}}||
- 다음과 같이 변형된 형태가 존재한다. (단, [math(n)]은 [math(0)] 이상의 정수, [math(b)]와 [math(c)]는 임의의 실수)
\sum_{k=1}^n \!\binom nk (bk)^{k-1} (c-bk)^{n-k} = nc^{n-1}
\end{aligned} )]}}}||
위에서 증명한 식 [math(\displaystyle \frac{(a+c)^n}{n!} = \frac a{n!} \sum_{k=0}^n \!\binom nk (a+bk)^{k-1} (c-bk)^{n-k})]으로부터
[math(\displaystyle \begin{aligned}
\frac{(a+c)^n}a &= \sum_{k=0}^n \!\binom nk (a+bk)^{k-1} (c-bk)^{n-k} \\
&= \!\binom n0 a^{-1} c^n +\sum_{k=1}^n \!\binom nk (a+bk)^{k-1} (c-bk)^{n-k} \\
&= \frac{c^n}a +\sum_{k=1}^n \!\binom nk (a+bk)^{k-1} (c-bk)^{n-k} \\
\Rightarrow \quad \sum_{k=1}^n \!\binom nk (a+bk)^{k-1} (c-bk)^{n-k} &= \frac{(a+c)^n-c^n}a = \frac1a \Biggl( \sum_{i=0}^n \!\binom ni a^i c^{n-i} -c^n \Biggr) \\
&= \frac1a \sum_{i=1}^n \!\binom ni a^i c^{n-i} = \sum_{i=1}^n \!\binom ni a^{i-1} c^{n-i} \\
&= nc^{n-1} +\sum_{i=2}^n \!\binom ni a^{i-1} c^{n-i}
\end{aligned} )]
여기에 [math(a=0)]을 대입하면 증명이 완료된다.
[math(\displaystyle \begin{aligned}
\sum_{k=1}^n \!\binom nk (bk)^{k-1} (c-bk)^{n-k} &= nc^{n-1}
\end{aligned} )]
}}}||
6. 1학년의 꿈
7. 관련 문서
[1] 이항정리를 배우기 이전까지 접하는 이항은 사실상 移項밖에 없어서, 이항정리도 二項이 아니라 移項으로 잘못 알고 넘어가는 경우가 보인다.[2] 따라서 Vandermonde convolution [math(\displaystyle \binom{n+m}r = \sum \binom nk \binom m{r-k} )] 등의 다양한 이항계수 항등식들이 빠져 있다.[3] [math(g)]는 법 [math(p)]에 대해서 [math(N)] 이하의 0을 포함하는 모든 양의 정수 중 [math(N)]과 합동인 정수들의 곱[4] 다만, 그 전에 실수 혹은 복소수 지수가 무엇인지에 대한 엄밀한 정의가 필요하긴 하다.