이산 수학 - 17 순열과 조합

확률

- 우리 일상 생활에서 자주 접하는 수학적 개념

- 확률 계산을 위한 개념 => 순열과 조합

 

순열과 조합

- 확률 계산에서 많이 사용하는 도구

 

경우의 수 관련 용어

- 시행 : 어떤 일이 일어날 가능성을 조사하기 위해 실험하거나 관찰하는 행위

  -> 주사위를 던져 나오는 주사위 눈을 조사하는 행위

- 사건 : 시행의 결과로 나타나는 현상

  -> 주사위를 던져 짝수의 눈이 나오는 현상

- 경우의 수 : 어떤 사건이 일어나는 방법의 가지수

  -> 주사위를 던져 짝수의 눈이 나오는 사건의 경우의 수 = 3

 

 

 

실생활에서 경우의 수

- 동전 2개를 던질때 2개의 동전이 다른 면이 나오는 경우의 수 = 2

 -> (H, T) (T, H)

- 두 사람이 가위바위보 할때 비기는 경우의 수 = 3

 -> (가위, 가위), (바위, 바위), (보, 보)

 

 

 

순열 

- 서로 다른 n개의 원소 중 r (1<= r <= n)개를 중복하지 않고 선택하여 순서대로 나열했을때 경우의 수

순열의 예시

- 1, 2, 3, 4에서 서로다른 3개의 숫자를 나열해서 만들 수 있는 3자리 숫자의 개수

- A, B, C, D, E, F, G를 한 번씩만 이용해 만들 수 있는 단어의 총 가지수

 

순열의 성질

 

문제

- 0, 1, 2, 3, 4, 5, 6을 한번씩만 이용해서(중복 허락 x) 네 자리 정수를 만들면?

- 2가 천의 자리가 되는 경우의 수

- 짝수가 되는 경우의 수

 -> 0이 맨뒤에 오는 경우의 수 : 6 x 5 x 4 = 120

 -> 2가 맨뒤에 나오는 경우의 수 :  5 x 5 x 4 = 100

->  4가 맨뒤에 나오는 경우의 수 :  5 x 5 x 4 = 100

->  6가 맨뒤에 나오는 경우의 수 :  5 x 5 x 4 = 100

=> 420가지

 

 

 

 

중복 순열

- 서로 다른 n개의 원소 중 r개를 중복을 허용해서 선택한 후 나열 한 경우 경우의 수

 

 

예시

- 1, 2, 3, 4에서 3개의 숫자를 나열해 만들 수 있는 3자리 숫자의 개수

- A, B, C, D, E를 이용해 만들 수 있는 단어의 총 가ㅣ쑤

 

중복 집합의 순열

- n개의 원소중에서 p개, q개 .., r개가 같은 원소일때 n개를 순서대로 나열할 때 경우의 수

 

중복 집합의 순열 예시

- 만약 p = q = ... = r = 1인 경우 n개를 일열로 배열하는 경우의 수

 

- A, A, A, B, B, B, B, C, C, D를 일렬로 배열하는 경우의 수

 

 

아래의 그림에서 A에서 B까지 가는 경로 중 최단 경로의 개수는?

- x는 5회, y는 4회 -> 총 9회 이동

 

 

 

조합

1. 조합의 정의

2. 중복 조합

3. 조합의 응용

 

 

 

조합의 정의

- 조합 : 서로다른 n개의 원소 중 r(1<= r <= n)개를 중복없이 선택한 후, 순서에 상관없이 나열한 경우의 수

 

- 예시 : 1, 2, 3, 4에서 서로다른 3개의 숫자를 뽑는 방법의 수

 

 

조합의 성질

 

 

예시

- 남성 회원 13명, 여성 회원 10명 인 동아리에서 5명인 대표를 뽑을 때

- 성별 구분 없이 대표를 뽑는 경우->  23명중 5명

- 남성 3명, 여성 2명을 대표로 뽑는 경우 -> 남성 13명중 3명, 여성 10명중 2명

 

 

조합 2

- 서로 다른 n개의 원소를 p1, p2, ..., pk개의 원소를 가지는 k개의 그룹으로 나누는 방법의 수

- pi가 다 다른 경우

 

- pi가 모두 같을 때

 

-pi중 같은게 m1, m2, ...개가 있을 때

 

조합 2 예시

- 학생 수가 15명인 반에서

-> 5명, 4명, 3명, 2명, 1명으로 나누는 방법의 수

-> 5명, 5명, 5명으로 나누는 방법의 수

-> 4명, 4명, 2명, 2명, 1명으로 나누는 방법의 수

 

 

중복 조합

- 서로 다른 n개의 원소 중 r개를 중복을 허용하여 선택한 후 이를 순서에 상관없이 나열 할 떄 경우의 수

 

중복 조합 예시

- 1, 2, 3, 4에서 중복을 허락하여 3개의 숫자를 선택하는 방법의 수

 

- 1, 2, 3에서 중복을 허락해 5개의 숫자를 뽑는 경우의 수

 

이항 정리

 

 

이항 정리의 예시

- (a + b)^2

 

- (a + b)^3

 

 

집합의 분할

- 분할 : 집합 A를 부분집합 A1, A2 ... , Ak가 다음을 만족시키면 {A1, A2 ..., Ak}를 A의 분할이라고 함

 

 

- S(n, k) = 원소 개수가 n인 집합을 k개의 부분 집합으로 분할하는 방법의 수

- 인도 수학자 라마누잔은 분할의 성질에 대한 연구로 수학 발전에 킁 공헌을 함

 

 

예시 S(5,2) = ?

- 원소의 개수가 1개, 4개인 집합으로 분할하는 경우의 수

- 원소의 개수가 2개, 3개인 집합으로 분할하는 경우의 수

- S(5, 2)는?