📂보조정리

조합론에서의 조합의 정의와 이항정리 증명

정의

1. 유한집합의 부분집합을 조합^combination이라 한다.
2. 기수가 $n$ 인 집합에서 기수가 $k$ 인 부분집합의 수를 $\binom{n}{k}$ 혹은 $_{n}C_{k}$ 과 같이 나타내고, 이항계수^{binomial coefficient}라 부른다. $$\binom{n}{k} = _{n}C_{k} = \frac{ n! }{ k! (n-k)! }$$

정리

이항정리^{binomial theorem}

$$(x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{k} y^{n-k}$$

이항계수 합 공식

$$2^{n} = \sum_{k=0}^{n} \binom{n}{k}$$

이항계수 뺄셈 공식

$$\binom{n}{k} \left( {\frac{ n }{ k }} \right)^{-1} = \binom{n-1}{k-1}$$

설명

참고로 위에서 이항정리를 제외하고 나머지 공식들의 이름들은 정말로 쓰이는 명칭들이 아니라 그냥 편하게 부르기 위해 임의로 붙인 것임에 주의하라.

이항정리는 조합론에서 가장 유명하고 중요한 정리로써 분야를 가리지 않고 널리 응용된다.

증명

이항정리 외의 증명은 각 공식마다의 문서에서 따로 다룬다.

---

$(x+y)^{n}$ 을 전개할 때 $x^{k} y^{n-k}$ 의 계수는 $$(x+y)^{n} = (x+y)(x+y)(x+y) \cdots (x+y)$$ 의 각 $(x+y)$ 중에서 $x$를 $n$개, $y$를 $n-r$개 선택하는 것과 같다. 따라서 조합의 수 $_n C _r$ 이 $x^{k} y^{n-k}$ 의 계수가 되므로 다음이 성립한다. $$(x+y)^{n} = \sum_{k=0}^{n} {_n C _k} x^{k} y^{n-k}$$

■