[ 이산 수학 ] 10. 경우의 수

경우의 수는 솔직히 쉬워서 뭘 해야할지 모르겠음..

 

 

ex) 3개의 영어와, 3개의 숫자로 만들 수 있는 문자열의 경우의 수는?

 

영어 알파벳 26개, 숫자 0~9 : 10개

 

26*26*26*10*10*10 = 17,576,000

 

 

● 그냥 조건없는 함수 : set n개 ->  m개 로 던질 때

 

n^m  :

첫번째 애가 던질 수 있는 경우의 수 =m개

두 번째 애가 "... :m개

...n번째 애가 :m개

 

 

● 일대일 함수 : nPm

첫번째 애가 던질 수 있는 경우의 수 =m개

두 번째 애가 "... :m-1개

...n번째 애가 :m-n+1개

 

 

---

혹은 겹치는 게 있으면 아래와 같다.

 

겹치는 게 있는 경우엔 아래와 같이 수행을 해야한다.

예시를 보자.

첫 비트 시작이 1이고, 끝 비트 2개가 00으로 끝나는 8비트 숫자가 나올 수 있는 경우를 계산해보자면

 

이거로 생각해보자

앞이 1인 경우 + 가장 뒤 2개가 0인 경우 - 앞이 1이고, 끝이 00인 경우

 

= 2^7  + 2^6 - 2^5

 

 

---

비둘기집 이론

 

넣어야 할 요소의 개수  > 넣을 수 있는 통의 개수

 

이면, 하나의 통에는 2개 요소가 이상이 들어가있다.

 

당연한 거 아님?ㅋㅋ

 

 

 

K+1 개에서 K로 보낸다.

쏘는 건 무조건 쏴야함.

one to one 가능?  X

 

 

---

Permutations  (순열)

 

ex) 5명의 학생 중 3명을 골라 각 자리에 앉혀 사진을 찍게 하는 방법은?

--> 첫 번째 자리에 앉을 수 있는 학생의 경우 = 5

두 번째 자리에 앉을 수 있는 학생의 경우 = 4

세 번째 자리에 앉을 수 있는 학생의 경우 = 3

 

5x4x3 = 60

 

주로 순열은 (n,r)로 이루어지고, n개에서  r개를 뽑는 경우를 센다.

 

공식은 n * n-1 * n-2 * ... * ( n-r +1 )

 

혹은

 

---

salesman visit count

출장을 7도시에 가야한다. 7개의 도시를 도는 순서의 개수는?

P(7,7) = 7! = 7*6*5*4*3*2*1 = 5040

 

 

 

 

---

Combinations (조합)

 

4명 중에 3명을 골라 일을 시키는 경우의 수는?

 

4명중에 3명을 구성하면 1명은 구성원이 되지 않는다.

각 경우당 1명이니 4명이 돌아가면서 되지 않는 걸 생각하면 

4.

 

조합으로 풀면 C(4,1) = C(4,3)

 

분자는 순열로 뽑고, 분모는 뽑은 개수로

 

 

표현법

증명

---

포커 카드 52장에서 5장을 고르는 경우의 수

C(52,5) = 52! / 5! 47! = 52*51*50*49*48 / 5*4*3*2*1

 

* C(n, r) = C(n, n−r)

 

 

---

(x+y)^n일 때, 각 항의 계수 구하는 법임

x랑 y의 계수가 1이 아니라 a 와 b라면

 

k번째 항의 계수는

n C k * a^k * b^n-k 이다.

 

 

---

 

이렇게 푸는 법도 알아두면 쓸모있을 듯

 

이런 것도 알아는 두자~

 

 

---

파스칼 정의 

 

(n+1) C k = nC(k-1) + nC

 

 

* 제곱을 할 때 각 항의 계수들도 이와 같다.

---

슬라이드 안 주신 거 보니 그리 안 중요한 듯

 

 

 

(출처)

한동대학교 최희열교수님 - 이산수학