• 이산수학

(1)

수의 세계

11주차. 이산수학과 그래프

(2)

1. 이산수학 2. 그래프

• 이산수학

• 그래프의 정의와 실생활에서의 이용 학습내용

학습목표

(3)

수의 세계

11주차. 이산수학과 그래프

(4)

1

이산수학

1

1) 이산수학이란?

“이산”이란 “연속”의 대칭어로서 낱낱의 개체가 떨어져 있다는 뜻이다. 이산 수학은 이산적인 대상과 이산적인 방법을 사용하는 수학을 말하고 조합론이 주종을 이룬 다.

(5)

1

이산수학

1

최근 중요성이 대두됨

1. 많은 자연현상의 연속적인 현상마져도 이산적인 모 델로 변환되고 이산수학 속의 아이디어가 수학 교육의 중심적 역할을 하고 있다는데 있다.

2. 지난 반세기 동안 Computer 기술이 급속히 발전하 면서 많은 대형 계산 문제가 해결 되었지만 Com-puter 는 program으로 움직이고 program은 이산적인

Algorithm에 의해 작성된다는 것이다. 즉 Computer Science의 핵심을 이루는데 있다.

(6)

1

이산수학

1

2) 세는 방법--곱의법칙

(7)

1

이산수학

1

2) 세는 방법--곱의법칙

ABCDE, ABCED, ABDCE, ABDEC, ABECD, … [예제1] 1. 다섯개의 문자 ABCDE를 가지고 길이가 4 인 단어를 만들 때 어느 문자도 반복되지 않은 단어는 몇 개가 가능할 것인가?

네 개의 자리 중 첫 위치에 올 수 있는 문자의 수는 5개, 두번째에는 4개, 세번째는 3개, 네번째는 2개가 가능하 므로 전체 가능한 단어의 수는 5•4 •3 •2 =120개 이다.

(8)

1

이산수학

1

2) 세는 방법--곱의법칙

ACDE, ACED, ADCE, ADEC, AECD, …

2. B로 시작하는 단어의 수는? 4 •3 •2 =24개

3. B로 시작하지 않는 단어의 수는?

4 • 4 •3 •2 =96개이다. 또는 120-24=96.

(9)

1

이산수학

1

[예제2] 집합 X의 원소는│X┃=ｎ이라하자. A⊆B가 되 는 X의 부분 집합의 쌍 (A,B)은 얼마나 많이 있는가?

주어진 한쌍 (A,B) 이 있으면 X의 각 원소는 A, B-A, X- B의 세 부분집합 중 단 하나에 속하게 된다. 역으로 X의 각 원소를 이 세 부분 집합들 중의 하나에 포함시킴으로 서 A⊆B⊆X가 되는 단 하나의 쌍 (A,B)를 얻는다. 따라 서 이러한 쌍들의 개수는 X 의 각 원소를 이 세 부분 집 합들 중의 하나에 포함시키는 방법의 수와 같다. 즉, X의 각 원소는 세가지의 선택권이 있으므로 3 · 3…3=3ⁿ이다.

(10)

1

이산수학

1

2) 세는 방법--합의법칙

• 합의 법칙(사건 A 또는 사건 B가 일어나는 경우의 수) 두 사건 A, B가 동시에 일어나지 않을 때, 사건 A가 일 어나는 경우의 수가 m가지이고 사건 B가 일어나는 경 우의 수가 n가지이면

(사건 A 또는 사건 B가 일어나는 경우의 수)=m+n(가지)

(11)

1

이산수학

1

2) 세는 방법--합의법칙

[예제3] 6인 위원회가 있고 여기서 회장, 비서, 재무를 선출 코자 한다.

1. 몇 가지 방법이 가능한가? (6 · 5 · 4 = 120)

2. 두 사람만이 회장 자격이 있다면? (2 · 5 · 4 = 40) 3. 한 사람은 꼭 한자리를 해야 한다면?

(5 · 4 + 5 · 4 + 5 · 4 = 60)

4. 두 사람은 꼭 한자리씩을 해야 한다면?

(두 사람이 한자리씩 차지하고 나면 나머지 한자리를 채 울 수 있는 길은 4가지가 있다. 각 각의 경우 세 자리를 달 리 할 수 있는 길은 3 · 2 · 1 = 6가지이므로 총 4 · 6 = 24 이다.)

(12)

1

이산수학

1

2) 세는 방법--합의법칙

(13)

1

이산수학

1

3) 순열

(14)

1

이산수학

1

3) 순열 원순열

서로 다른 n 개를 원형으로 나열하는 한 방법. n 개 모두를 일렬로 배열하는 순열의 수는 n! 이고 원은 돌려도 변하지 않으므로 중복되는 것이 n 개 있다.

원순열의 수는

)!

1

! (



 n n

n

(15)

1

이산수학

1

3) 순열 염주순열

서로 다른 구슬 n 개로 목걸이를 만드는 방법. 원순열의 수는 (n - 1)!이고 목걸이는 뒤집을 수 있으므로 염주 순열의 수는

n!

2n = (n -1)!

2

(16)

1

이산수학

1

3) 순열

100명이 참여한 경품 행사에서, 1등, 2등, 3등을 한 명씩 선발하는 방법은 모두 몇 가지 인가?

• 3등을 선발하는 방법 = 100가지

• 결국, 100 X 99 X 88 = 970,220가지 이다.

(17)

1

이산수학

1

3) 순열 Anagram

단어나 문장을 구성하고 있는 문자의 순서를 바꾸어 다른 단어나 문장을 만드는 놀이

가나 → 나가, 국왕 → 왕국, 남장 → 장남, 성탄 → 탄성, 순조 → 조순, 비굴 → 굴비

국자감 → 감자국, 남해군 → 해남군, 창원역 → 원창역, 모로코 → 코모로

(18)

1

이산수학

1

3) 순열 Anagram

Mary → Army, Andrew → Warned, Slow → Owls, Act → Cat

(19)

1

이산수학

1

3) 순열

Anagram

(20)

수의 세계

11주차. 이산수학과 그래프

(21)

1

이산수학

1

4) 조합

(22)

1

이산수학

1

4) 조합

[예제4] 52장의 poker카드에는 4가지 종류의 패(suits) (clubs ♣, diamonds ◇, hearts ♡, spades ♠)가 있고 각각은 13가지 순위가 있다.(ace, 2-10, jeck, queen, king)

(23)

1

이산수학

1

4) 조합

[예제5] 아래 그림과 같은 n x n 정방형 격자판에서 좌 측 및 귀퉁이에서 오른쪽 또는 위쪽으로만 전진하여 우 측 상단 귀퉁이로 갈수 있는 길의 수는?

(24)

1

이산수학

1

4) 조합

(25)

1

이산수학

1

같은 것이 있는 순열

n 개 중에 같은 것이 각각 p 개, q 개, , r 개가 있을 때, n 개 모두를 일렬로 배열하는 순열의 수는

n!

p!q! r!

5) 중복을 허용한 순열과 조합

[예제] Mississippi 에서 처럼 M 한개, I 네개, S

네개, P 두개로 만들 수 있는 순열의 수는?

(26)

1

이산수학

1

6) 중복순열

(27)

1

이산수학

1

n 개 중에서 중복을 허락하여 r 개를 선택하는 방법의 수는

C(n + r -1, n -1) = C(n + r -1, r)

7) 중복조합

(28)

1

이산수학

1

7) 중복조합

(29)

1

이산수학

1

방정식 x

₁

+ x

₂

+  + x

_n

= r 의 음이 아닌 정수해의 개수는

) , 1 (n r r C _ _

7) 중복조합

방정식 x

₁

+ x

₂

+  + x

_n

= r 의 자연수 해의 개수는

) ,

1

(r r n

C _ _

(30)

1

이산수학

1

8) 이항정리

(31)

1

이산수학

1

8) 이항정리

정리에서 a =1, b = 1이면

2ⁿ = C(n,i)

i=0

å

n

C(n,i)를 이항계수(binomial coefficient)라 한다.

(32)

1

이산수학

1

8) 이항정리--다항계수

i₁, i₂, …, i_k 이 i₁ + i₂ +  + i_k = n 을 만족하는 음이 아닌 정수 일 때,

n i₁i₂ i_k æ

èç ö

ø÷ = n!

i₁!i₂! i_k!

을 다항계수라고 한다.

다항계수는 a₁ i₁ 개, a₂ i₂ 개, … , a_k i_k개를 일렬 로 나열하는 반복이 있는 순열의 개수와 같다.

(33)

1

이산수학

1

8) 이항정리--다항계수

정리에서 x =1, y = 1, z = 1 이면

3

ⁿ

= n!

i

₁

!i

₂

!i

₃

!

i_1,i₂,i₃³0

å

n

(34)

1

이산수학

1

8) 이항정리--다항정리

(35)

1

이산수학

1

8) 이항정리—Pascal의 삼각형

(36)

수의 세계

11주차. 이산수학과 그래프

(37)

[문제1] 단어 MATHEMATICS에 사용된 문자의 순서를 바꾸어 만들 수 있는 모든 단어의 수를 구하라.

평가하기

(38)

[문제2] 8을 하나만 포함하는 네 자리 수의 개수를 구하라.

평가하기

(39)

[문제3] 문자 a, e, i, o, u, x, x, x, x, x, x, x 를 모두 이용하여 일렬로 배열할 때 모음끼리 는 서로 이웃하지 않도록 하는 방법의 수를 구 하라.

평가하기

(40)

[문제4] 다음 물음에 답하라.

1) 남자 n 명, 여자 n 명 중에서 대표 n 명을 뽑는 방법의 수를 구하라.

2) 포함된 남자의 수가 k일 때, 대표를 뽑는 방법 의 수를 구하라.

3) 다음 식이 성립함을 보여라.

평가하기

2n n æ

èç

ö

ø÷ = n

k æ èç

ö ø÷

2

k=0

å

n

(41)

수의 세계

11주차. 이산수학과 그래프

(42)

정리하기

 기본적인 세기의 방법.

 순열

1강. 순열

(43)

정리하기

 조합

 이항정리

2강. 조합

(44)