순열, 조합, 중복순열, 중복조합 - 개념

 기본적으로 위 4개 개념은 다음과 같은 명제에서 시작한다.

서로 다른 공 n개가 든 상자에서 r개를 뽑는 경우의 수

 이제 어떻게 뽑느냐가 결정을 하는데, 뽑는 순서를 고려한다면 순열, 그렇지 않다면 조합이다. 또한, 중복을 허용하는 것과 그렇지 않은 것으로 나눈다. 그래서 2 * 2, 총 4개의 개념이 있는 것이다. 이 때, 중복을 허용한다는 것은 공을 뽑고, 다시 복원한다고 생각하면 될 것이다.

순열 - "중복을 허용하지 않고", "뽑는 순서를 고려함"
조합 - "중복을 허용하지 않고", "뽑는 순서를 고려하지 않음"
중복순열 - "중복을 허용하고",  "뽑는 순서를 고려함"
중복조합 - "중복을 허용하고",  "뽑는 순서를 고려하지 않음"

 

 

 

순열

개념

 서로 다른 n개의 원소에서 r개를 뽑을 때, "중복을 허용하지 않고", "뽑는 순서를 고려하는" 것이 순열이다.

 이어서 순열 공식을 정리해 보자. 총 r개의 공을 뽑아 줄세운다고 생각할 수 있다.

 첫 번째 자리는 n개의 원소가 올 수 있다 - 경우의 수 n
 두 번째 자리는 첫 번째 자리에서 뽑은 원소를 제하고 n-1개의 원소가 올 수 있다 - 경우의 수 n-1
 세 번째 자리는 첫 번째, 두 번째 자리에서 뽑은 원소를 제하고 n-2개의 원소가 올 수 있다 - 경우의 수 n-2
 ...
 r번째 자리는 n-r+1개의 원소가 올 수 있다 - 경우의 수 n-r+1

 이렇게 되어서, 순열 공식은 다음과 같다.

$_nP_r\ =\ \frac{n!}{\left(n-r\right)!}\left(0\ \le \ r\ \le \ n.\ 단,\ 0!\ =\ 1\right)$

 

 

예시

 [1, 2, 3, 4] 서로 다른 4개의 원소에서 중복을 허용하지 않고 뽑는 순서를 고려해 3개를 뽑는 경우

1 2 3 
1 2 4 
1 3 2 
1 3 4 
1 4 2 
1 4 3 
2 1 3 
2 1 4 
2 3 1 
2 3 4 
2 4 1 
2 4 3 
3 1 2 
3 1 4 
3 2 1 
3 2 4 
3 4 1 
3 4 2 
4 1 2 
4 1 3 
4 2 1 
4 2 3 
4 3 1 
4 3 2 

 

 

 

조합

개념

 서로 다른 n개의 원소에서 r개를 뽑을 때, "중복을 허용하지 않고", "뽑는 순서를 고려하지 않는" 것이 조합이다.

 이어서 조합 공식을 정리해 보자. 이 경우는 순열 공식에서 r!를 나눈 값이라고 생각할 수 있다.

$_nC_r\ =\ \frac{_nP_r}{r!}\ =\ \frac{n!}{r!\left(n-r\right)!}\left(0\ \le \ r\ \le \ n.\ 단,\ 0!\ =\ 1\right)$
 
 이렇게 되는 이유는, 순열로 뽑은 것에서 중복되는 것이 r!개 나오기 때문이다. 다르게 말하자면 조합으로 뽑은 모든 경우의 수에 순서를 고려하면 r!번 곱해지기 때문이다.

 

 

예시

 [1, 2, 3, 4] 서로 다른 4개의 원소에서 중복을 허용하지 않고 뽑는 순서를 고려하지 않고 3개를 뽑는 경우

1 2 3 
1 2 4 
1 3 4 
2 3 4

 

중복순열

개념

 서로 다른 n개의 원소에서 r개를 뽑을 때, "중복을 허용하고", "뽑는 순서를 고려하는" 것이 중복순열이다.

 중복을 허용한다는 말은 한 원소를 뽑고 다시 그 원소를 뽑을 수 있다는 말이다. 즉, 모든 자리에서 n개의 경우의 수를 택할수 있으며, 자리는 r개가 있으므로 중복순열 공식은 아래와 같다.

$_n\Pi _r\ =\ n^r$

 

예시

 [1, 2, 3, 4] 서로 다른 4개의 원소에서 중복을 허용하고 뽑는 순서를 고려하고 2개를 뽑는 경우

1 1
1 2
1 3
1 4
2 1 
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1 
4 2
4 3
4 4

 

중복조합

개념

 서로 다른 n개의 원소에서 r개를 뽑을 때, "중복을 허용하고", "뽑는 순서를 고려하지 않는" 것이 중복조합이다.

​

 중복조합은 개념이 좀 헷갈려서 다른 방식으로도 접근할 수 있다. 동일한 r개의 원소를 서로 다른 n개의 상자에 넣는 경우의 수이다. 이렇게 봤을 때 상자를 구분하기 위해 n-1개의 막대가 있다고 가정하고, r개의 원소와 n-1개의 막대를 나열한다면 주어진 조건을 만족하는 경우를 찾을 수 있다. 그리고 이 경우, 원소와 막대는 동일하므로 중복되는 것이 있는 순열이고,

$\frac{\left(n+r-1\right)!}{\left(n-1\right)!\left(r\right)!}$

 

와 같이 나타나진다.

$_nH_r\ =\ _{n+r-1}C_r\ =\ \frac{\left(n+r-1\right)!}{\left(n-1\right)!\left(r\right)!}$

 

 

예시

 [1, 2, 3, 4] 서로 다른 4개의 원소에서 중복을 허용하고 뽑는 순서를 고려하지 않고 2개를 뽑는 경우

1 1 1 
1 1 2 
1 1 3 
1 1 4 
1 2 2 
1 2 3 
1 2 4 
1 3 3 
1 3 4 
1 4 4 
2 2 2 
2 2 3 
2 2 4 
2 3 3 
2 3 4 
2 4 4 
3 3 3 
3 3 4 
3 4 4 
4 4 4