이항계수 (Binomial Coefficient) $\binom{n}{k}$는 음이 아닌 정수 $n$과, $n$보다 작은 음이 아닌 정수 $k$에 대하여 팩토리얼 을 이용해 다음과 같이 정의합니다.
$$ \binom{n}{k} = \frac{n!}{k! (n - k)!} $$조합론적으로는 $n$개 중 $k$개를 뽑는 경우의 수와 동일하고, $(a + b)^{n}$의 전개식에서 $a^{k} b^{n - k}$의 계수, $a^{n - k} b^{k}$의 계수와 동일합니다. 이는 이항정리 의 결과입니다.
0. 기본 전제 / $\binom{n}{k} = \frac{n!}{k! (n - k)!}$
$$
\begin{align}
\binom{n}{k} &= \frac{n!}{k! (n - k)!}\\
\binom{n}{k + 1} &= \frac{n!}{(k + 1)! (n - k - 1)!}\\
\binom{n + 1}{k + 1} &= \frac{(n + 1)!}{(k + 1)! (n - k)!}
\end{align}
$$
$$
\begin{align}
\binom{n}{k} + \binom{n}{k + 1}
&= \frac{n!}{k! (n - k)!} + \frac{n!}{(k + 1)! (n - k - 1)!}\\
&= \frac{n! \color{red}{\times (k + 1)}}{\left(k! \color{red}{\times (k + 1)} \right) (n - k)!} + \frac{n! \color{red}{\times (n - k)}}{(k + 1)! \left( (n - k - 1)! \color{red}{\times (n - k)} \right)}\\
&= \frac{n! (k + 1)}{(k + 1)! (n - k)!} + \frac{n! (n - k)}{(k + 1)! (n - k)! }\\
&= \frac{n! (k + 1) + n! (n - k)}{(k + 1)! (n - k)!}\\
&= \frac{n! (k + 1 + n - k)}{(k + 1)! (n - k)!}\\
&= \frac{n! (n + 1)}{(k + 1)! (n - k)!}\\
&= \frac{(n + 1)!}{(k + 1)! (n - k)!}\\
&= \binom{n + 1}{k + 1}
\end{align}
$$
1. $\binom{n}{k} + \binom{n}{k + 1} = \binom{n + 1}{k + 1}$
이항계수 성질 1 증명
3. $\sum\limits_{j = 0}^{k} \binom{m}{j} \binom{n}{k - j} = \binom{m + n}{k}$ ( 주세걸-방데르몽드 항등식 )
4. $\sum\limits_{k = 0}^{\lfloor \frac{n}{2} \rfloor} \binom{n - k}{k} = F_{n + 1}$ ($\lfloor x \rfloor$는 최대 정수 함수 , $F_{n}$은 피보나치 수열 )
이항계수를 실수 전체로 일반화 한 경우로 베타함수 라는 개념도 존재합니다.
이항계수를 구하는 방법에는 여러가지가 존재합니다.
크게는 그냥 팩토리얼 값을 이용해 일일이 구하는 방법과, 파스칼의 삼각형 (1번 특징) 을 이용한 메모이제이션을 사용하는 방법과, 정수론을 이용하여 이항계수를 어떤 수 $p$로 나눈 나머지를 찾는 일입니다. (이 경우에는 모듈러 곱셈 역원 이라는 개념도 사용합니다.)