[이산수학] 조합이론 - 계수, 순열

1. 기본 계수 법칙

1) 곱셉법칙

두 사건 A, B가 일어날 경우의 수가
N(A) = m , N(B) = n 일 때,
사건 A, B가 동시에 일어날 경우의 수는 m x n이다.
N(A × B) = N(A) × N(B) = m × n

 

 

✏️ 예) 5비트로 표현할 수 있는 2진수는?

 

= 2⁶ = 64개

 

 

 

2) 합의 법칙

두 사건 A, B가 일어날 경우의 수가

N(A) = m , N(B) = n 일 때, A ⋂ B = ∅일 때,

각각 사건 A, B가 일어날 경우의 수 m + n

즉,  N ()A ⋂ B = ∅

N (A ∪ B) = N(A) + N (B) = m + n 

 

사건 X, Y, Z가 발생할 방법의 집합을 각각 A, B, C라고 하면
(1) X 또는 Y가 발생할 경우의 수
= A ∪ B = | A | + | B | − | A ∩  B |

 

X 또는 Y 또는 Z가 발생할 경우의 수
= | A ∪ B ∪ C | = | A | + | B | + | C |
− | A ∩ B | − | A ∩ C | − | B ∩ C |
+ | A ∩ B ∩ C | 

 

✏️ 예) 4비트 2진수 중에서 1로 시작하거나 1로 끝나는 2진수의 개수는 모두 몇 개인가?

(계산식까지 고려하여 답하시오)

 

A: 1로 시작하는 4비트 이진수

B: 1로 끝나는 4비트 이진수

일때 A ∪ B의 개수를 구하면 된다.

 

|A ∪ B| = |A| + |B| - |A ∩ B|

 

 

• |A|: 1로 시작하는 경우 : 첫 자리가 1이면, 나머지 3자리는 자유롭게 결정 (0 또는 1)
  |A| = 2³ = 8
•  |B|: 1로 끝나는 경우 : 마지막 자리가 1이면, 앞의 3자리는 자유롭게 결정(0 또는 1)
  |B| = 2³ = 8
•  |A ∩ B|: 1로 시작하고 1로 끝나는 경우
  첫 자리가 1, 마지막 자리가 1이면, 가운데 두 자리는 자유롭게 결정(0 또는 1)
   |A ∩ B| = 2² = 4

|A ∪ B| = |A| + |B| - |A ∩ B|

= 2³ + 2³ - 2²

= 8 + 8 − 4

= 12

 

 

 

---

 

2. 순열(Permutation)

0 ≤ r ≤ n을 만족하는 정수 n, r에 대하여,
n개의 원소를 갖는 집합에서 순서를 고려해서
r개의 원소를 뽑는 경우의 수는
P (n, r) = n(n − 1)(n − 2) ⋯ (n − r + 1)
또는
P (n, r) = n! / n−r !

 

✏️ 1~5까지 숫자를 한번씩만 사용해 만들수 있는 3자리 수는 모두 몇 가지 인가?

 

P(5, 3) =

= 3 x 4 x 5 = 60

 

 

1) 중복순열(permutation with repetition) : 중복 집한에서의 순열

n개의 원소를 갖는 집합에서 중복을 허용하고
순서를 고려해서 r개 원소를 뽑는 경우의 수는
n ∏ r = n ʳ

 

1~4개의 원소가 들어있는 주머니면

4개 중 1개를 뽑고, 뽑은 원소는 다시 주머니에 넣고

4개 중 1개를 다시 뽑기를 반복하는 형식.

 

 

✏️  예) S, T, Y, L, E 의 5개 문자 중 3개를 이용해서 (중복허용) 만들 수 있는 단어는 모두 몇 가지인가? 

5∏3 = 5³ = 125

 

 

2) 원순열(Circular permutation)

n개의 원소를 갖는 집합의 모든 원소들을
원형으로 나열하는 경우의 수는
n! / n = n(n − 1)! / n = (n − 1)!

 

✏️  예) A와 B를 포함한 6명이 하나의 원탁에 앉아야한다. A와 B는 서로 마주 보고 앉아야 한다.
앉을 수 있는 경우의 수는?

A와 B는 순열에서 제외.

5명이 원탁에 앉는 경우의 수는
(5-1)! = 4! =24

 

 

* 선형 순열에서는 서로 다른 위치로 보이지만, 회전만 다르고 같은 경우는 같은 순열로 취급

선형 순열 예 (일렬로 세울 때)	원순열 예 (원형으로 배열)
빨-초-파-노 초-파-노-빨 파-노-빨-초 노-빨-초-파 → 모두 다른 순열로 취급 (4! = 24가지)	빨-초-파-노 (시계방향 회전) → 초-파-노-빨 → 파-노-빨-초 → 노-빨-초-파 → 회전한 것뿐이므로 전부 같은 순열로 간주
n!	(n−1)!