조합 (Combination, 이항계수)

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

$$\left(\begin{array}{c}n\\ k\end{array}\right){=}_n{C}_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개를 뽑는 경우
$$\left(\begin{array}{c}5\\ 2\end{array}\right)=\frac{5!}{2!(5-2)!}=\frac{5\cdot 4}{2}=10$$
모든 경우의 조합을 나타내면
$$1\{\begin{array}{l}2\\ 3\\ 4\\ 5\end{array},2\{\begin{array}{l}3\\ 4\\ 5\end{array},3\{\begin{array}{l}4\\ 5\end{array},4\{\begin{array}{l}5\end{array}$$

[예 2] 이항계수의 항등식
$$\left(\begin{array}{c}n\\ k\end{array}\right)+\left(\begin{array}{c}n\\ k-1\end{array}\right)=\left(\begin{array}{c}n+1\\ k\end{array}\right)$$

<증명>

$$\begin{array}{rl}\left(\begin{array}{c}n\\ k\end{array}\right)+\left(\begin{array}{c}n\\ k-1\end{array}\right)& =\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)!}=\left(\begin{array}{c}n+1\\ k\end{array}\right)\end{array}$$

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