경우의 수 (5) - 다양한 테크닉

0. 경우의 수를 세는 다양한 테크닉

• 유니폼 분포는 경우의 수를 세면 그 것이 곧 확률이다. (유니폼 분포는 근원사건이 같은 분포를 말함)
• 경우의 수를 세기 위한 다양한 테크닉이 존재함.
• 아래의 테크닉들은 각 상황에 특화되어 사용되면 굉장히 파워풀 하다.

 

1. Enumeration (직접 세기)

• 경우의 수를 직접 일일이 다 세보는 방법임.
• 너무 비효율적이고 오래걸리지만, 가장 확실한 방법임

 

2. Divide & Conquer (분할 정복)

• 부분부분의 경우의 수를 세서 더하거나 곱하는 방법으로 자주쓰이는 방법
• 사건 A와 사건 B가 일어났다면, 각각 사건의 경우의 수를 구해서 더하거나 곱하는 것
• 순서 없이 남자 8명중 2명을 뽑고, 여자 6명중 3명을 뽑는 경우의 수 = 8C2 * 6C3
• A에서 B로 가는 경로가 3가지, B에서 C로 가는 경로가 2가지 일때, 전체 경우의 수는 6가지

 

3. Tree Diagram (트리 다이어그램, 수영도)

• 경우의 수 세기에서 가장 중요한 테크닉 중 하나임
• 아래와 같이 트리의 형태로 모든 경우를 나타내고, 리프노드의 개수를 세면 됨.
• 가장 깔끔하고 명확하게 경우의 수를 알 수 있지만, 경우가 많아지면 그리기 힘듬

 

4. Function Relation (함수 릴레이션)

• 경우의 수 세기 테크닉 중 가장 고급 테크닉에 속하는 방법으로 직접 함수를 설계해야함
• 사용하기는 어렵지만 잘만 사용하면 엄청나게 파워풀한 방법으로, 꼭 알아두기
• 만약 사건 f와 사건 g가 1 : 3 함수인 것을 알았고, F의 집합 수가 N개라는 것을 알았을 때
• N : ? = 1 : 3이라는 비례식을 세워서 ? = 3N이라는 것을 알 수 있다.

 

5. Inclusion - Exclusion Principle (포함 배제의 원리)

• 교집합과 합집합의 관계를 이용하여, 전체 경우의 수(합집합)을 구해내는 방법
• 합집합은 Union, 교집합은 Intersection이라고 부르며, 일반화 시킬 경우,
• 세번째 형태처럼 Sigma기호로 정리하여 나타낼 수 있고, 집합의 수가 많아질수록 항이 추가됨.

 

6. 여집합 (Compliment)

• $|A|$를 구하기 위해 $|U| - |A^C|$를 계산하는 방법
• 간단하지만 실제로 경우의 수를 구할 때 사용하면 굉장히 파워풀함.

 

7. 예제 문제풀이

1) 축구공의 하얀색 면 개수 구하기

• 축구공의 검정색 면에는 5개의 흰색 면이 연결되어 있고, 흰색면에는 3개의 검정색 면이 연결되어있다.
• 만약 검정색 면이 12개라면,  하얀색 면은 몇개인가? (함수 릴레이션 설계 문제)
• 검정색 : 하얀색 = 3 : 5이기 때문에, 3하얀색 = 5검정색이고, 하얀색면 = (5/3) * 검정색이다.
• 검정색 면이 12개이기 때문에 축구공에 있는 하얀색 면의 개수는 5/3 * 12로 총 20개이다.

 

2) 문자열 "Mississippi"를 배열하는 조합의 개수는?

• 문자열 "BOB"를 만드는데 사용되는 순열은 총 6가지의 경우의 수가 나옴.
• 그러나 "B1 B2 O"와 "B2 B1 O"는 같은 문자열("BOB")이고, 중복되는 문자열을 2개씩 묶어서 나눌 수 있음
• 즉, 2개의 순열로 1개의 조합을 만들 수 있고, 순열 : 조합 = 2 : 1이기 때문에, 2조합 = 1순열이고, 조합의 수는
• 총 3개가 됨. 이런 원리를 이용해서 Mississippi를 적용해보자면, Mississippi는, 11!개의 순열이 만들어지는데,
• 1!*4!*4!*2!개의 조합으로 1개의 순열을 만들 수 있기 때문에 답은 11! / 1!*4!*4!*2!이 됨.

 

8. Reference