서로 다른 $n$개에서 순서를 무시하고 $r$개를 뽑는 것을 조합이라 하고, 그 가짓수를 $_nC_r$ 또는 $\binom{n}{r}$로 쓴다:
$$_nC_r = \frac{_nP_r}{r!} = \frac{n!}{r!\,(n-r)!}$$
순열에서 순서 정보를 지운 것이다. $r$개를 뽑아 나열하는 $_nP_r$가지 중, 같은 구성원의 나열이 $r!$가지씩 겹치므로 $r!$로 나눈다. "대표 3명 뽑기"처럼 뽑힌 사람이 누구인지만 중요하고 자리 구분이 없는 상황이 조합이다. "순서가 중요한가?"라는 질문 하나가 순열과 조합을 가른다.
조합에서 가장 미심쩍은 부분은 "왜 하필 $r!$로 나누는가"다. 나눗셈이 갑자기 튀어나온 것처럼 느껴지는데, 실제로 세어 보면 자연스럽다. A, B, C 세 명 중 $2$명을 뽑는다고 하자. 순서까지 따지는 순열로 세면 AB, BA, AC, CA, BC, CB로 $6$가지다. 그런데 "대표 $2$명"으로 보면 AB와 BA는 같은 팀이다. 이렇게 같은 조합 하나가 순열에서는 $2$명을 줄 세우는 $2! = 2$가지로 부풀어 있다. 그래서 순열의 수를 $2!$로 나누면 부풀린 만큼을 정확히 걷어내 조합의 수($3$가지)가 된다.
실전에서 헷갈리는 건 "이 문제가 순서를 따지는가"를 판단하는 순간이다. 팁은 뽑은 대상들에 서로 다른 이름표(자리·역할·등수)가 붙는지 보는 것이다. 금·은·동메달이나 회장·부회장처럼 이름표가 있으면 순서를 따지는 순열, "당첨된 번호들"이나 "대표단"처럼 뽑힌 것들이 서로 대등하면 순서를 안 따지는 조합이다. 같은 숫자로 시작해도 이 판단 하나로 답이 몇 배씩 달라지니, 계산보다 이 구분을 먼저 확실히 하자.
조합의 공식과 두 성질은 모두 순열에서 "순서 정보를 지운다"는 한 가지 조작에서 나온다.
① 순열을 먼저 세고 부풀린 만큼 되돌린다. $r$개를 뽑아 나열하는 방법은 $_nP_r$가지다. 이 목록에서 구성원이 같은 것끼리 묶으면, 한 묶음 안에는 그 $r$개를 줄 세운 $r!$가지가 들어 있다. 그러므로
$$_nP_r = {_nC_r} \times r! \quad \Longrightarrow \quad _nC_r = \frac{_nP_r}{r!} = \frac{n!}{r!\,(n-r)!}$$
② 왜 나눗셈이 허용되나. 나눗셈이 성립하려면 모든 묶음의 크기가 똑같이 $r!$이어야 한다. 실제로 뽑힌 $r$개는 서로 다른 것들이므로, 어떤 조합이든 나열 방법이 예외 없이 $r!$가지다. 이 균등성이 ①의 나눗셈을 정당화한다(뽑는 대상 중에 같은 것이 섞여 있으면 이 논리가 깨지고, 그때는 같은 것이 있는 순열로 따로 세야 한다).
③ 대칭성. $_nC_r = \dfrac{n!}{r!\,(n-r)!}$에서 $r$과 $n-r$을 맞바꿔도 식이 그대로이므로 $_nC_r = {_nC_{n-r}}$이다. 식을 보지 않고도 알 수 있다 — 뽑을 $r$개를 정하는 일은 버릴 $n-r$개를 정하는 일과 일대일로 대응한다.
④ 파스칼의 법칙. 원소 하나(예: $a$)를 정해 두고, $r$개를 뽑는 모든 방법을 둘로 가른다.
두 부류는 겹치지 않고 빠짐도 없으므로 합의 법칙으로 더하면 $_nC_r = {_{n-1}C_{r-1}} + {_{n-1}C_r}$이다. 파스칼의 삼각형에서 바로 위 두 수를 더해 아래 수를 얻는 규칙이 이 식이다.
⑤ 양 끝값. $_nC_0$은 아무것도 뽑지 않는 방법이니 $1$가지($0! = 1$ 약속과 맞물린다), $_nC_n$도 전부 뽑는 한 가지뿐이다. 삼각형의 양 끝이 늘 $1$인 이유다.
'파스칼의 삼각형'은 파스칼보다 수백 년 앞선다. 중국에서는 13세기 양휘가 그 이전 가헌의 결과를 전하며 이 삼각형을 기록했고, 페르시아에서도 알카라지와 오마르 하이얌이 거듭제곱의 전개 계수로 같은 배열을 다뤘다. 인도 문헌에도 시의 운율을 세는 맥락에서 비슷한 표가 남아 있다. 여러 문명이 독립적으로 같은 표에 도달한 셈이다.
블레즈 파스칼의 몫은 표를 만든 것이 아니라 성질을 증명한 것이다. 그는 『산술 삼각형론』(1654년 집필)에서 위 ④의 덧셈 규칙을 비롯한 성질들을 정리하고, 자연수에 대한 추론을 단계적으로 밀고 가는 논법(오늘의 수학적 귀납법에 해당하는 초기 형태)을 사용했다. 이 연구가 페르마와 주고받은 도박 문제 서신과 같은 해에 이루어졌다는 점이 중요하다 — 조합의 셈이 그때 확률 계산의 도구로 자리 잡았기 때문이다.
이후 조합은 이항계수라는 이름으로 이항정리와 한 몸이 되었고, 오늘날에는 표본을 고르는 통계, 암호와 알고리즘의 경우 수 분석처럼 "고르는 방법이 몇 가지인가"를 묻는 모든 곳에서 쓰인다.