조합, 순열 (combination, permutation)

 

조합(conbination)과 순열(permutation) 둘 다 n 개 중에서 r 개를 선택하여 나오는 수를 계산하는 방법이다

순서를 상관없으면 조합이고, 순서를 고려하면 순열이다

 

1. 순열 (nPr)

n개 중에서 r개를 순서가 있도록 고르는 경우의 수

 

예를 들어, 친구 5명(A, B, C, D, E) 중에서 3명을 뽑아서 1등, 2등, 3등을 뽑는 상황일 때.

즉, 순서가 중요한 경우입니다.

 

1. 첫 번째 자리에 올 수 있는 사람은?

A, B, C, D, E → 총 5명 중에서 누구든 올 수 있음 → 5가지  

 

2. 두 번째 자리는?

첫 번째에서 1명 이미 선택했으니 남은 사람은 4명 → 4가지 

 

3. 세 번째 자리는?

이미 2명 골랐으니 남은 사람은 3명 → 3가지

 

5 x 4 x 3 = 60

 

즉 5명 중에서 3명을 뽑아 순서대로 나열하는 방법은 60가지 입니다 

 

공식으로 나타내면 

 

2. 조합 (nCr)

n개 중에서 r개를 순서 없이 고르는 경우의 수

 

 

예를들면 

3명 중 2명을 뽑아 같이 커피 마시기
→ {A, B}랑 {B, A}는 같은 조합

 

나올 수 있는 조합은 다음과 같습니다

(A, B), (B, A),
(A, C), (C, A),
(B, C), (C, B)

 

하지만 순서 없이 뽑는 경우니까,

(A, B)와 (B, A)는 같은 조합이에요.

(A, C)와 (C, A)도 같은 조합

(B, C)와 (C, B)도 같은 조합

따라서 중복이 2배로 세어지고 있어요

 

중복 개수는? 

각 조합마다 내부 순서가 바뀌는 경우가 2! = 2가지 (뽑은 2명 순서 바꾸는 방법)

그래서, 순열에서 세었던 경우의 수는