[Algorithm] 순열과 조합

수학적 개념

경우의 수를 세우는 방법 중 가장 기본이 되는 것은 순열과 조합이다.
가장 기본이 되는 것은 순열이다.

 

순열

수학에서, 순열 또는 치환은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 

개념

1, 2, 3 로 4자리의 수를 만들수 있는 자연수는 몇개 일까?
3! 이다 
3! = 3*2*1 = 6 

 

설명

어떻게 6개가 나오는지 아래와 같이 분석해 보았다.

 

1. 첫번째로 1을 선택하는 경우.
1 2 3
1 3 2

2. 첫번째로 2를 선택하는 경우  
2 1 3
2 3 1

3. 세번째로 3을 선택하는 경우
3 1 2
3 2 1

아래 Tree로 표현을 해보았다.

순열공식

만일 3개중 2개를 선택해서 만드는 경우의 수는
3!/2! 이다.

이를 일반화 하면 해당 공식이 나온다.
nPr = n!/(n-r)! 이다

 

조합

위공식에서 순서를 없애면 조합이 된다.

설명

1, 2, 3, 에서 2개를 뽑은경우

1, 2
2, 1
2, 3
3, 2
3, 1
1, 3

위에서 순서를 없애면 
1, 2
1, 3
2, 3 

3개가 나오게 된다.
그래서 아래와 같은 공식을 도출할수 있다.

nCr = nPr/r! =n!/r!(n-r)! 가 된다.