[모듈식 수학 (하)] 3. 경우의 수 (12) 조합의 정의와 조합의 수

조합의 정의와 조합의 수

'조합이란 OOO이다' 라고 정의되지는 않습니다. 'n개에서 r개를 택하는 조합' 으로 정의됩니다. n개에서 r개를 택하는 조합은 n개에서 r개를 순서 상관없이 택하는 것을 말합니다. 예를들어 a,b,c 세개에서 2개를 택하는 조합은 아래와 같습니다.

a,b

a,c

b,c

n개에서 r개를 택하는 조합은 n개에서 r개를 택하는 순열에서 순서를 제거한 것이라고 이해할 수도 있습니다.

n개에서 r개를 택하는 조합의 개수를 말합니다. 예를들어 a,b,c 세개에서 2개를 택하는 조합의 수는 3입니다. n개에서 r개를 택하는 조합의 수를 구해봅시다. 순열에서 순서를 제거하는 방식으로 조합의 수를 유도하겠습니다.

a,b,c 에서 두개를 택하는 순열은 아래와 같습니다.

a,b

b,c

a,c

c,a

b,c

c,b

a,b 와 b,a 는 순서를 생각하지 않는다면 같은 경우입니다. a,c 와 c,a 도 b,c 와 c,b도 마찬가지입니다. 따라서 위 순열의 수는 조합의 수에 비해 2배 많습니다. 여기서 2배는 택하는 개수를 나열하는 2!을 의미합니다.

a,b,c,d,e 에서 3개를 택하는 순열을 생각해봅시다. 아래 여섯 경우가 모두 다르게 세어집니다.

a,b,c

a,c,b

b,a,c

b,c,a

c,a,b

c,b,a

조합에서는 위 여섯경우가 같습니다. 순열의 수가 조합의 수에 비해 6배 많게 세어진 것이고, 이는 택한 개수를 나열하는 3!입니다.

일반화시켜봅시다. n개에서 r개를 택하는 순열의 수는 아래와 같습니다.

$_{n}P_{r}=\frac{n!}{(n-r)!}$

위 순열은 n개에서 r개를 택하는 조합에 비해 $r!$배 만큼 많게 세어진 것입니다. 따라서 n개에서 r개를 택하는 조합의 수는 아래와 같습니다.

$_{n}C_{r}=\frac{_{n}P_{r}}{r!}=\frac{n!}{(n-r)! \ r!}$