순열과 조합 시각화

공통수학1 · 경우의 수 — 서로 다른 것에서 몇 개를 뽑을 때, 순서를 따지면 순열(P), 순서를 안 따지면 조합(C). 이 둘의 차이를 나무 그림으로 눈으로 확인한다.

공 여러 개에서 몇 개를 뽑는 상황을 생각해 보자. "1등, 2등을 뽑는다"처럼 자리(순서)가 있으면 AB와 BA는 다른 결과다. 반면 "대표 2명을 뽑는다"처럼 자리가 없으면 {A, B}와 {B, A}는 똑같다. 앞의 경우의 수가 순열, 뒤가 조합이고, 조합은 항상 순열보다 작거나 같다.

1. 직접 해보기

공의 개수 n 과 뽑을 개수 r 을 조절하고, 순열/조합 모드를 바꿔 보자. 아래 나무는 첫 자리에 올 공 → 둘째 자리에 올 공 → … 을 가지치기로 나열한 것이다.

2. 공을 직접 뽑아보기

공을 r 개 클릭해서 한 경우를 직접 만들어 보자. 그 선택이 위 나무의 전체 나열에서 몇 번째 경우인지 알려준다. (순열 모드에서는 클릭한 순서가 자리 순서가 된다.)

3. 팩토리얼과 공식

팩토리얼 n! 은 서로 다른 n 개를 한 줄로 세우는 방법의 수다. 첫 자리에 올 것 n가지, 다음 자리 (n−1)가지, … 이므로

순열 nPr

n 개에서 r 개를 뽑아 순서대로 자리에 놓는 방법의 수. 첫 자리 n가지, 둘째 자리 (n−1)가지, … r 번째 자리 (n−r+1)가지:

조합 nCr

조합은 순서를 무시한다. 순열에서는 뽑은 r 개를 줄 세우는 방법 r! 가지를 모두 다른 경우로 세었다. 조합에서는 그것들이 전부 같은 한 경우이므로 r! 로 나눠 중복을 지운다:

4. 파스칼 삼각형 (nCr 표)

각 칸은 nCr 값이고, nCr = (n−1)C(r−1) + (n−1)Cr — 바로 위 두 칸의 합이다. 현재 슬라이더의 (n, r) 칸을 초록색으로 표시한다.

각 행의 양 끝은 nC0 = nCn = 1, 그리고 nCr = nC(n−r) 이라 좌우 대칭이다.

5. 한 줄 요약