6 경우의 수 (곱셈 규칙)

경우의 수

영어로는 Counting이다. 수 세기. 셈법. 조합론. 등 으로도 불린다.

조합론은 무엇인가?

1 무엇보다 이산수학에서 굉장히 중요한 분야 중 하나다.

2 비교적 최근 수학이다. 17세기 즈음에 도박 확률 문제와 연관되어 정립되었다.

3 주로 특정 상태의 어떤 것들을 세는데 사용한다. 

예) 2개 이상 연속하는 0을 포함하지않는 0과 1로만 이루어진 n길이의 문자열 갯수는?

4 이론적인 곳 외에도 굉장히 다양한 곳에서 사용된다.

예) 알고리즘의 복잡도 구하기, IP 수요와 그 할당의 문제, DNA 염기서열 등등의... 앗 복잡해

어찌됐든 알아보기로 하자...

경우의 수 기초

컴퓨터를 사용할 때 패스워드를 생성하는 것을 생각해보자. 패스워드를 생성하는데 최소 1개의 숫자를 포함해야하고 최대 8자의 소문자 알파벳+ 숫자로 이루어진다면 가능한 패스워드는 몇 개가 존재하겠는가?

좀 더 호기심을 자극할만한 주제로 질문해보자.

상대방의 비밀번호를 알아내고 싶다고 하자. 내가 코딩한 비밀번호 생성기가 어떤 시간 복잡도를 가질까? 거기다 이론상 반드시 필요한 연산 수(경우의 수)도 있으니.. 유효한 시간내에 알아내는게 가능할까?

어쩌면 비밀번호 생성기로 해킹하는 것보다 다른 방법이 더 효율적이지 않을까? 재밌는 문제다.

자 우선 기초섹션이니, 경우의 수의 기초가 되는 매우 중요한 원리를 배워볼 것이다.

나중에 응용 문제를 많이 풀다보면 직감적으로 정답을 알지만, 왜 그렇게 되는지의 원리를 깜빡하게 되는 상황이 왕왕있다. 

어찌보면, 의미없는 정답이다. 사람이니 어쩔 수 없다.씁쓸하다.

내가 한창 응용 문제들을 풀어야 되는 상황에서도 이 기초 부분을 포스팅하는 이유도 이 때문이다.

경우의 수의 기초 원리 (곱의 규칙과 덧셈의 규칙)

경우의 수는 기본적으로 두 개의 규칙이 있다. 곱의 규칙(product rule)와 덧셈의 규칙(sum rule)이다. 이 두 가지로 어떤 다양한 문제들을 해결할 수 있는가 먼저 살펴볼것이다.

 

Definition: 곱의 규칙 

어떤 수행 절차가 두 개의 업무가 연속되어서 수행된다고 하자. 그러니까 C라는 업무가 있는데, C라는 것은 A와 B가 모두 수행되어야 완성된다고 하자. 그리고 A를 수행하는데 n1 만큼의 방법이 있고, B를 수행하는데 n2 만큼의 방법이 있다. 그러면 C를 완료하기 위해서는 n1*n2 만큼의 방법이 있는 것이다.

예제 1

단 두 근로자만 근로하는 신생기업이 있다고 하자. 요한이와 민수는, 한 층에 12개 사무실이 있는 층을 빌렸다. 이 상황에서, 요한이와 민수의 각 각 개인 사무실을 배정하는 방법은 몇 가지가 있을까?

답

각 각 개인 사무실을 배정하는 행위는 두 가지로 이루어진다.

요한이의 개인 사무실을 배정하는 것과 민수의 개인 사무실을 배정하는 것이다. 우선 요한이의 사무실을 배정한다고 생각해보자. 그렇다면 경우의 수는 12가지이다. 그 후 민수의 사무실을 배정한다면 요한이에게 배정된 사무실 한 개를 제외한 11가지의 경우가 있다. 따라서, 곱의 규칙에 따라 12개의 사무실에 2명의 근로자를 배정하는데엔 12*11 = 132 가지의 경우의 수가 존재한다.

예제 3

전산실에는 초소형 컴퓨터가 32개가 있고, 각 초소형 컴퓨터는 24개의 서비스 포트를 가지고 있다. 그렇다면 전산실에 있는-, 각각 고유한 포트들은 총 몇개 있는가?

답

포트의 갯수를 찾는데에는 두 가지 요소로 break down 할 수 있다. 

첫 번째로는 초소형 컴퓨터를 선택하고, 그 뒤 그녀석이 가지고 있는 포트를 선택하는 것이다. 따라서, 초소형 컴퓨터를 선택하는 32가지 방법과, 해당 컴퓨터에서 포트를 선택하는 방법 24가지 방법이 있다. 곱의 규칙에 따라 32*24= 768 포트가 존재한다.

Application 곱의 규칙 응용

곱의 규칙의 확장판은 다음과 같다. 수행절차가 2개 이상으로 이루어져 있는 것이다. 즉, 어떤 수행 절차가 다음의 업무들로 이루어져있다고 생각해보자. T1, T2, T3, .... , Tm 여기서 T는 Task이다. 그리고 각 업무 Ti 는 다음의 수행 방법을 가지고 있다고 하자. n1, n2, n3 ... nm. 그렇다면 해당 수행절차를 수행하는데 n1*n2*n3 ... * nm 의 방법의 수가 있다. 

곱의 규칙은 수학적 귀납법을 이용하여 증명할 수 있다.  (다음에 꼭.. 증명... ㅠ..ㅠ )

<이런 자세에서 부터 난 늦은 것일수 있어...ㅠ.ㅠ 

챕터 5할때 꼭 할게요 ㅠ.ㅠ>

예제 4

길이가 7인 각기 다른 비트 문자열은 몇개가 존재할 수 있는가?

답    

비트는 각 문자당 2가지의 경우의 수가 존재한다. 길이가 7인 비트 문자열은 7개의 문자로 이루어진다. 즉, c1, c2, c3 ... c7 은 각 두 가지의 방법으로 완성될 수 있으므로, 곱의 규칙에 따라 2*2* ... *2 ,2^7=128 가지의 경우의 수가 존재한다.

예제 5

<군필자들이 잘 아는 번호판>

위와 같은 번호판이 있다고하자. 얼마나 많은 고유한 번호판을 만들 수 있는가? 단, 여기서 3번째의 한글은 알파벳 소문자로 대체한다고 하자. 즉, @@A@@@@ 를 만족하는 번호판의 개수는? 

답

길이가 7인 번호판은 다음과 같이 구성된다. N1, N2, A1, N3, N4, N5, N6. 여기서 N은 숫자, A는 알파벳이다. 곱의 규칙에 따라 10*10*26*10*10*10*10 =  26,000,000 가지의 번호판이 생성될 수 있다.

예제 6

함수 개수 세기 원소의 갯수가 m인 집합에서 원소의 갯수가 n인 집합으로의 함수는 몇 개가 존재할 수 있는가?

답

정의역의 m개의 원소에서 공역의 n개의 원소로의 함수는, 공역의 n개 원소가 정의역을 선택하는 것과 같다. 즉, 곱셈 규칙에 따라 n*n .... *n = n^m 개의 함수가 가능하다. 예로, 정의역의 원소가 5개이고 공역의 원소가 3개인 함수는 총 3^5=243가지 존재할 수 있다.

<각자 한개씩만 보급품을 선택가능한 경우의 수를 생각해보자.
그럴듯한 함수다. 일반적인 함수의 원소들은 그냥 숫자이겠지만 이해를 돕기위해 바꿔보았다>

예제 7

전단사 함수 세기 원소의 개수가 m인 정의역으로부터 원소 개수가 n인 공역으로의 일대일 함수의 개수는 몇개가 존재할 수 있는가?

 

답

우선 함수의 정의에 따라 정의역의 모든 원소가 사용되어야하므로, m>n 이면서 일대일 대응인 함수는 존재하지 않는다.

자 그러니까 앞으로 설명할 것은 m<=n 인 경우를 가정하고 한다. 정의역의 원소가 a1, a2, ... am이 존재할 때 a1의 값을 결정할 수 있는 공역 원소의 경우의 수는 n개 이다. 함수가 일대일 대응이므로, a2의 원소의 값은 a1이 선택한 값을 선택할 수 없다. 따라서 원소 a2의 값을 결정할 수 있는 공역 원소의 경우의 수는 n-1개이다. 

일반화하면, 정의역 원소 ak 의 경우 선택할 수 있는 공역 원소개수는 n-k+1이다. 따라서 곱의 규칙에 따라 원소 개수가 m인 정의역으로부터 원소 개수가 n인 공역으로의 일대일 함수 개수는 n*(n-1)*(n-2)..*(n-m+1) 개가 존재가능한다.

예로, 정의역 원소 개수가 3개이며 공역 원소 개수가 5인 일대일 함수의 개수는 5*4*3= 60 이다.

예제 9

다음의 코드를 보고, ans의 값을 유추해보자. (우와앗 코딩이다 ㅠ.ㅠ)

답

초기 ans의 값은 0이다. 각 반복문이 돌 때마다 ans값이 1씩 증가한다. 전체 반복문을 T라고 하면 각각의 반복문은 Ti, Tj, Tk, Tl, Tm, Tn 으로 구성된다. 각 반복문의 반복횟수는 10, 9, 8, 7, 6, 5 이다. (다르게표현하자면 반복문의 반복 인덱스 {i,j,k,l,m,n}의 각기 다른 고유한 숫자 상태라고도 할 수 있다. 반복한 횟수에 따라 반복자는 항상 고유하게 결정된다. )

곱셈 규칙에 따라, 반복문의 전체 반복 횟수는 10*9*8*7*6*5 이며 ans의 값은 10*9*8*7*6*5 = 151,200 이다.

다음 포스트 읽기 

경우의수 덧셈 규칙

 http://ingyeoking13.tistory.com/162

* 사설

나는 졸업과 동시에 조합론과 확률 관련 원서를 독파하려고했는데 아직 공부 1도안했다. 지금은 10월이다. 졸업은 2월에했고... 난 진짜 공부를 정말 안하는거같다. 이로써 조금이나마 용서받았음 좋겠다.