조합 (Combination, 이항계수)

n개의 원소를 가지는 집합에서 순서에 상관없이 k개의 부분집합을 고르는 조합의 경우의 수

\[\begin{pmatrix}n\\k\end{pmatrix}=_nC_k=C_{n,k}=C(n,k)=\frac{P(n,k)}{k!(n-k)!}=\frac{n!}{k!(n-k)!}\]

여기서 P(n,k)는 n개 중 k개를 뽑는 순열

[예 1] 5개 중에서 2개를 뽑는 경우
\[\begin{pmatrix}5\\2\end{pmatrix}=\frac{5!}{2!(5-2)!}={5\cdot4\over2}=10\]
모든 경우의 조합을 나타내면
\[1\begin{cases}2\\3\\4\\5\end{cases},\,2\begin{cases}3\\4\\5\end{cases},\,3\begin{cases}4\\5\end{cases},\,4\begin{cases}5\end{cases}\]

[예 2] 이항계수의 항등식
\[\begin{pmatrix}n\\k\end{pmatrix}+\begin{pmatrix}n\\k-1\end{pmatrix}=\begin{pmatrix}n+1\\k\end{pmatrix}\]

<증명>

\[\begin{split}\begin{pmatrix}n\\k\end{pmatrix}+\begin{pmatrix}n\\k-1\end{pmatrix}&=\frac{n!}{k!(n-k)!}+\frac{n!}{(k-1)!(n-k+1)!}\\&=\frac{n!(n+1)}{r!(n-k+1)!}=\frac{(n+1)!}{k!(n+1-k)!}=\begin{pmatrix}n+1\\k\end{pmatrix}\end{split}\]

[예 3] 1~45 숫자 중에서 6개 숫자를 뽑는 로또복권의 모든 경우의 수
\[\begin{pmatrix}45\\6\end{pmatrix}=\frac{45!}{6!(45-6)!}=8,145,060\]