6 순열과 조합

이전포스트

브루트 포스

순열과 조합

경우의 수 문제들 중에 대부분이 - 특정 크기의 집합으로부터 고유한 원소들을 순서를 따지면서 뽑으며 구성하는 경우의 수를 말한다. 또, 뽑은 순서는 상관없이 구성하는 경우의 수 문제도 있다.

5명 학생중에 3명을 선택해서 줄을 세우는 경우의 수는? --> 순열
4명 학생중 3명의 학생을 뽑는 경우의 수는?  --> 조합

이게 바로 순열과 조합이다

순열

예제 1

5명 학생들 중에 3명을 선택해서 일렬로 줄을 세우려고한다. 이 때 이 경우의 수는 몇 개인가?

정답

우선 어떤 학생을 선택하는지에 대한 그 순서가 중요하다. 첫 번째에 줄서는 애를 뽑기위해선 5가지 경우의수가 있고, 그 친구가 선택되었을 경우에는 이제 두번째로 줄 서는 애를 뽑기위해선 4가지의 경우의 수가 있다. 그리고 두번째 친구도 줄 선경우에 마지막 친구를 뽑는 경우의 수는 3가지이다. 그러니까 즉 곱의 규칙에 따라서, 5명의 학생들 중 3명을 일렬로 세우는 경우의 수는 5*4*3 = 60의 경우의 수가 존재한다.

5명 학생들 중 5명을 일렬로 세우기 위해서는 5*4*3*2*1 = 120 가지의 경우의 수가 나온다.

지금 우리가 살펴본 것이 고유한 개체들을 순서대로 나열하는 것에 대한 경우의 수를 본것입니다. 이게 바로 우리가 배울려고 하는 컨텐츠와 연관되어 있는데요

그게 바로 순열입니다. 순열은 고유한 원소들을 포함하고 있는 집합에서 이 원소들을 순서에 상관있게 나열하는 것입니다. 여기서 모든 원소들을 순서에 상관있게 나열하는 것 말고도 일부 원소들만 그렇게 나열하는 것도 있는데요. 

둘 다 할거긴 합니다만, 우선 집합에서 r개의 원소들을 뽑아서 나열하는 것을 r-permutation r-순열 이라고 합니다.

예제 2 (문제아님)

Let S = {1, 2, 3}. S의 순열 중에는 3, 1, 2 가 있다. S의 2-permutation에는 2, 3 이 있다.  한 집합에서 r-순열을 표현할 때는 P(n, r) 이라고 할 수 있습니다. 이 때 n은 집합의 전체 원소개수이고, r은 뽑을 원소의 개수입니다. 

예제 3 (문제아님)

Let S = {a, b, c}. S의 2순열은 다음과 같다. a,b; a,c; b,a; b,c; c,a; c,b; 그러니까 3개의 원소를 가진 S에서 2-순열은 6개가 있는 것이다. 원소 3개로 이루어진 집합에서 2-순열 경우의 수는 항상 6개이다. 

첫 원소를 꺼내는데 3개의 경우의 수가 있고, 두번째 원소를 꺼내는데 2개의 경우가 있다. 곱의 규칙에 따라 (두 개의 원소를 꺼내는 경우는 위 두 경우의 수로 이루어져있으므로) P(3, 2)= 3*2=6이다. 

정리 1

전체 원소의 개수가 n인 집합에서 r-순열의 수. P(n, r)

P(n, r)= n(n-1)(n-2)...(n-r+1), 여기서 1<= r <= n.  

증명

이 식이 맞다는 것을 증명하기 위해 우선 곱의 규칙을 사용할 겁니다. 순열의 첫 번째 원소는 n개의 원소들 중에 하나 뽑는것이므로 n개의 경우가 있습니다. 그다음 순열의 두 번째 원소엔 n-1개의 경우의 수가 존재하겠지요, 왜냐면 집합엔 n-1개가 있으니까요. 그리고 그다음은 n-2가지의 방법 ...계속 계속 하다보면 r번째 원소를 뽑기위해선 n-(r-1) = n-r+1 가지의 방법이 있는겁니다. 따라서, 곱의 규칙에 따라 다음과 같습니다.

n*(n-1)*(n-2)* ... *(n-r+1) , 원소개수가 n개인 집합에서 r순열의 경우의 수.

참고로 1<=n일때 P(n,0)=1 입니다. 왜냐하면 집합에서 0개의 원소를 뽑아내는 방법은 단 한가지만 존재하기 때문입니다. 그러니까, 공집합인 리스트가 딱 한개 반드시 존재한다는 말입니다.

딸림정리 1  

0<=r<=n 일때, P(n,r) = n!/(n-r)! 이다.

증명

정리 1에 따라 1<=r<=n 일때 P(n,r)= n(n-1)(n-2)...(n-r+1) = n!/(n-r)! 입니다. 

왜냐면 1<=n 일떄 n!/(n-0)!= n!/n!=1 이니까, P(n,r)= n!/(n-r)! 식은 r=0일 때도 동작하는겁니다.

걍 n개의 집합에서 r순열을 뽑을때 0-순열 또한 존재한다는 겁니다.

예제7 

글자 ABCDEFGH에서 ABC를 포함하는 순열은?

풀이 

마치 ABC가 블록처럼 발생시켜야하니까. 글자수가 8개임에도 해당 글자 집합이 6개 원소로 이루어져있다고 취급하면된다. ABC, D, E, F, G, H 처럼말이다. 이 여섯개 원소들은 어떠한 순서로도 발생가능하니까 6!=720 개의 경우의 수가 나타난다.

조합

이제는 순서에 상관없는 경우의 수를 살펴봅시다. 그러니까 n개 중 r개를 뽑는데 순서는 상관없는 경우의 수예요.

예제 4

4명 학생들 중 3명을 뽑아서 청소담당 시키려고하는데, 경우의수가 몇 개 일까요?

답

우선 이걸 답하려면, 4명의 학생들중 3명을 뽑아서 만드는 고유한 부분 집합의 수를 세야하는데요. 우린 부분집합 4개를 찾을 수 있어요, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}. 여기서 뜻은 4명 학생들 중 3명을 뽑아서 청소시키려고할 때엔, 학생들이 지목당하는 순서는 상관이 없다는거에요

바로 위 문제에서 살펴본게 어떤 n 개의 원소로 이루어진 집합에서 특정 사이즈의 부분 집합의 개수인데요. 

이걸보고 n 집합의 r-조합이라고 해요. n개의 원소들 중 순서에 상관없는 선택으로 r개의 원소들을 선택하는거죠. 그러니까 r-조합은 원소 r개로 이루어진 부분집합을 뜻해요.

예제 9 (문제아님)

Let S be the set {1, 2, 3, 4}. 그럼 {1, 3, 4}는 집합 S의 3-조합이다. 집합 {4, 1, 3} 은 {1, 3, 4}와 같으므로 조합의 경우의 수에 포함되지 않는다.

n 개의 고유한 원소로 이루어진 집합의 r- 조합은 다음과 같이 표기할 수 있다. C(n, r), 또는 이항계수 (binomial coefficient) ( a b) 로 나타낼 수 있다.

예제 10 (문제아님)

C(4,2) = 6임을 보았다. {a, b, c, d}의 2-조합은 6이다. {a, b}, {a, c}, {a, d}, {b,c} {b,d}, {c,d} 

n개의 원소를 가진 집합의 r-조합의 경우의 수를 수식을 이용해 구할 수 있는데요. 우선 r-순열은 우선 r 조합을 뽑은뒤에 그 후에 조합들의 순서를 정하는 것과 같습니다.

정리 2에선, C(n, r)의 값이 이러한 방식으로 결정되는 걸 볼 수 있는데요

정리 2

0<=r<=n 일 때, n 원소의 r-조합은 다음과 같다. C(n, r) = n!/r!(n-r)!

증명 

n 원소의 r-순열인 P(n, r)은 r-조합의 C(n, r)을 통해 얻을 수 있는데, 여기서 각 r-조합을 정렬해주면 된다. 이 정렬이 P(r, r) 경우의 수가 있다. 따라서, 곱의 규칙에 따라서 P(n, r) = C(n, r) * (r, r)

이는 다음을 뜻한다.

C(n, r) = P(n,r) / P(r,r) = n!*(r-r)!/ r!(n-r)! = n!/r!(n-r)!

또, 이 정리를 증명하기위해 경우의 수의 나눗셈 규칙을 이용할 수도 있는데, 조합에서의 원소 정렬은 필요가 없다. n 원소에서의 r-조합에서는 r을 정렬하는 경우의 수가 P(r, r)만큼이 있다. 각 C(n,r)개의 조합에는 정확하게 P(r,r) 만큼의 정렬이 필요없는 것이다. 나눗셈 규칙에 따라, C(n, r)= P(n,r)/P(r,r) 이며, 이건 결국 C(n,r)=n!/(r!*(n-r)!) 이다. 아래의 그림을 참조해보자.

그리고 C(n, r)= n!/r!(n-r)! 을 그대로 쓰는것보다, n!/r!(n-r)!= {n*(n-1)*(n-2)...(n-r+1)}/r! 을 쓰면 조금 더 효율적 일 수 있다. 

예제 11

52개의 카드에서 5개의 카드를 선택해서 패를 만드는 경우의 수는? 또는, 52개의 47개의 카드를 선택하는 경우의수는?

정답

52개의 카드에서 5개의 카드를 선택해서 패를 만드는 경우의 수는 순서가 중요하지않으므로 다음과 같은 경우의 수가 생성된다. C(52, 5) = 52!/(5!*47!) 이 수는, 5개의 카드를 선택해서 각기 다른 카드패를 만드는 경우의 수다. 52*51*50*49*48/5! 만큼의 경우가 있는것이다. 

C(52,47) = 52!/47!5! = 52*51*50*49*47/5! 이므로 47개의 카드를 선택하는 경우의 수도 같은 것이다.

딸림정리2

0<=r<=n 일 때, C(n, r) = C(n, n-r)이다.

증명

예제 14

n 길이의 비트 문자열에 정확하게 r개의 1을 가지고 있는 경우의 수는 몇인가?

정답

예제 15

수학과 9명과 컴퓨터과학과 11명이 있다. 수학과 3명과 컴퓨터과학과 4명을 뽑아서 청소를 시키려고한다. 경우의 수는?

정답

곱의 규칙에 따라, 정답은 C(9, 3)과 C(11, 4)의 곱일것이다. 따라서, 27720가지의 경우가 있다.

자 여기까지 기본적인 순열과 조합이였구요

다음 포스트에서는 본격적인 순열과 조합의 구현을 보겠습니다.

다음포스트

순열과 조합 구현