이산수학 12강 :: 순열, 조합, 비둘기집의 원리

이산수학 12강을 보며 배운내용

 

 

순열(Permutation)

순서를 고려해서 r개의 원소를 뽑는 경우의 수

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

 

중복집합에서 순열

중복된 원소가 p개, q개, r개가 있을 때, n개를 일렬로 배열하는 경우의 수

n! / p! q! r!

 

이런 것도 풀 수 있다

노드 A에서 노드 B까지 최단 경로의 방법의 수

위로 4번, 오른쪽으로 6번가면 최단경로다

10개의 변을 지나는 것이니까

10! / 6! x 4! = 210

 

중복 순열

중복을 허용하고 순서를 고려해서 r개의 원소를 뽑는 경우의 수

∏ (n, r) = n^r

 

예시) S, A, N, T, A 문자 중 3개를 이용해서 만들 수 있는 단어 개수(중복 허용)

∏ (5, 3) = 5³ = 125

 

만약 중복이 허용되지 않으면

P(5, 3) = 5! / 2! = 60

 

원순열

n개의 원소를 갖는 집합의 원소를 원형으로 나열하는 경우의 수

n! / n = (n - 1)!

 

원순열 예시)

6명이 둘러 앉는데 음바페와 홀란드는 마주 앉아야 한다. 몇 개의 경우의 수가 나올까?

우선 음바페가 정해지면 홀란드는 정해지는거라 제외하고 5명이 앉는다 생각하면 된다.

(5 - 1)! = 24

 

 

조합(Combination)

순열과 다르게 순서 없이 뽑는 경우의 수

 

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

or

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

 

조합 예시)

8개 중에 4개 버튼 눌러 비밀번호 만들 때 몇가지 경우의 수가 있을까?

8개 버튼 중 4개 선택하는 것이라 조합을 이용

 

8! / 4! x (8 - 4)! = 70

 

 

이항 정리(Binomial Theorem)

 

이항정리 예시)

(x + y)⁶ 전개식에서 x³y³의 개수는?

C(3, 3) = 6! / 3! x (6 - 3)! = 6 x 5 x 4 / 3!

 

 

비둘기집 원리(Pigeonhole Principle)

k개의 비둘기 집에, n개의 물체를 넣으면,

적어도 집에는 Math.ceil(10 / 9)가 있다

 

10마리의 비둘기, 9개의 비둘기 집

하나의 집에는 2개의 비둘기가 적어도 하나는 존재한다