#정의

서로 다른 $n$개의 원소 중에서 $k$개의 원소를 고르는 방법의 수를 세어 봅시다(이를 $n$개에서 $k$개를 고르는 조합의 수라고 하며 $C_n^k$로 표기합니다).

#첫 번째 방법

마찬가지로 첫 번째 자리에는 $n$개의 원소 중 아무것이나 놓을 수 있고, 두 번째 자리에는 남은 $n - 1$개 중 아무것이나 놓을 수 있으며, $k$번째 자리에는 $n - k + 1$가지 선택지가 남습니다. 즉, 전체 경우의 수는 $n\cdot(n-1)\cdot\ldots\cdot(n-k+1)=\frac{n!}{(n-k)!}$가 됩니다. 이렇게 하여 우리가 센 것은 $k$개 원소로 이루어진 순서가 있는 집합의 개수라는 점에 주목하십시오. $n$개 중에서 $k$개의 원소를 고르는 방법의 수를 얻으려면 결과를 $k!$로 나누어야 합니다. 앞서 확인했듯이 $k$개의 원소를 순서대로 배열하는 방법이 바로 그만큼 있기 때문입니다. 결과적으로 $C_n^k=\frac{n!}{k!(n-k)!}$를 얻습니다.

#두 번째 방법

$0 < k < n$에 대해 $C_n^k$를 계산하는 또 다른 방법이 있습니다. 첫 번째 원소를 살펴봅시다. 첫 번째 원소가 집합에 포함된다면, 남은 $n-1$개 중에서 $k-1$개를 골라야 합니다. 그렇지 않다면 남은 $n-1$개 중에서 $k$개를 골라야 합니다. 따라서 $C_n^k=C_{n-1}^{k}+C_{n-1}^{k-1}$입니다. 이렇게 하면 어떤 $n$까지의 모든 $C_n^k$를 $O(n^2)$에 구할 수 있습니다.

#파스칼의 삼각형

따라서 $C_n^k$는 변에는 1이 놓이고 나머지 수는 위의 두 수의 합과 같은 무한 삼각형의 형태로 쉽게 나타낼 수 있습니다. $C_n^k$가 $n$번 행의 $k$번째 수라는 것은 쉽게 알 수 있습니다. 이것을 파스칼의 삼각형이라고 합니다.