여기서는 기초 조합론 수준의 이항정리를 간단히 살펴본다. 일반화된 이항정리와 관련된 글은 "일반화된 이항정리의 두 가지 증명"이라는 제목의 포스트(바로가기)를 참조하라.
식 \((a+b)^{n}\)을 전개했을 때, \(a^{i}b^{j}\)의 계수는 무엇일까? 식 \((a+b)^{n}\)을 \[ \underbrace{(a+b)(a+b)(a+b)(a+b)\cdots(a+b)}_{\text{\(n\)개의 \((a+b)\)의 곱}} \] 으로 나타내어, \(n\)개의 인수 중 \(i\)개의 인수에서 \(a\)를 택하고 나머지 \(j\)개의 인수에서 \(b\)를 택하여 곱한 것으로 항 \(a^{i}b^{j}\)가 만들어진다는 것을 알 수 있다. 따라서 \((a+b)^{n}\)를 전개하여 얻는 항 \(a^{i}b^{j}\)에서 항상 \(i+j=n\)이며, 전개하여 얻은 식을 정리했을 때의 \(a^{i}b^{j}\)의 계수 \(c_{ij}\)는 \(c_{ij}=\binom{n}{i}\)로 주어짐을 알 수 있다. 물론 \(c_{ij}=\binom{n}{j}\)도 성립한다. \(i+j=n\)이므로 이는 그냥 \(\binom{n}{i}=\binom{n}{n-i}\)라고만 써도 된다.
관찰 양의 정수 \(n\)에 대하여 \[ (a+b)^{n}=\sum_{r=0}^{n}\binom{n}{r}a^{r}b^{n-r} \] 이 성립한다.
이 결과를 이항정리(Binomial Theorem)라 부르며 이 정리 때문에 \(\binom{n}{r}\)를 이항계수(binomial coefficient)라 부르곤 한다.
이항정리에서 \(a=b=1\)로 두면 등식 \[ \sum_{r=0}^{n}\binom{n}{r}=2^{n} \] 를 얻는다. 또한 이항정리에서 \(a=-1, b=1\)로 두면 등식 \[ \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots=\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\cdots=2^{n-1} \] 를 얻는다.
이항계수를 포함한 항등식은 말그대로 수천가지가 있다. 딱 하나의 등식만 더 살펴볼텐데, 이 등식은 앞서 살펴 보았던 최단 경로의 개수를 세는 문제(바로가기)를 이용하여 증명할 수 있다. \[ \binom{n}{0}^{\!\!2}+\binom{n}{1}^{\!\!2}+\binom{n}{2}^{\!\!2}+\cdots+\binom{n}{n}^{\!\!2}=\binom{2n}{n} \] 또한, \(m\)명의 남자에서 \(k\)명을 택하고 \(w\)명의 여자에서 \(n-k\)명을 택하는 경우의 수를 이용하여 등식 \[\sum_{k=0}^{m}\binom{m}{k}\binom{w}{n-k}=\binom{m+w}{n}\]을 얻는데, 여기서 \(m=w=n\)인 경우를 생각해도 위의 등식을 바로 얻을 수 있다.