6.1 계수의 기본 원리
이산수학 <제6장> 계수
1
이상준 교수
(덕성여대 수학과)
교재 : 이산수학 (7판)
Kenneth H. Rosen 지음, 공은배 등 옮김 강의 슬라이드 : 이상준, 오연주(15)
곱셈법칙, 덧셈법칙
곱셈 법칙: 하나의 과정이 두 개의 연속된 작업으로 분리될 수 있다고 하자.
첫 번째 작업을 수행하는 𝑛"가지의 방법이 있고,
첫 번째 작업을 수행한 후 두 번째 작업을 수행하는 𝑛#가지의 방법이 있다면,
전체 과정을 완료하는 데는
𝒏
𝟏𝒏
𝟐가지의 방법이 있다. 덧셈 법칙:
첫 번째 작업을 수행하는 𝑛"가지의 방법이 있고
두 번째 작업을 수행하는 𝑛#가지의 방법이 있을 때,
둘 중의 한 가지 작업을 수행하는 데는
𝒏
𝟏+ 𝒏
𝟐가지의 방법이 있다.2
예제1: 산체스와 파텔, 두 명의 종업원을 가진 새로운 회사가 12개의 사무실을 가진 건물을 빌렸다. 이 두 명의 종업원들에게 서로 다른 사무실을 할당해 줄 수 있는 경 우의 수는 몇 가지인가?
예제3: 컴퓨터 센터에 32개의 마이크로컴퓨터가 있고, 각 마이크로컴퓨터는 24개의 포트를 가지고 있다. 이 센터에는 서로 다른 포트가 모두 몇 개 있는가?
3
예제4: 길이가 7인 서로 다른 비트 문자열은 모두 몇 개인가?
예제5: 자동차 번호판이 3개의 영문 대문자와 3개의 숫자로 구성되어 있다면 서로 다른 번호판은 모두 몇 개 인가? 단, 3개의 영문 대문자가 먼저 앞에 위치하고 그 뒤 3개의 숫자가 나타나며 금지된 단어는 없다고 가정하자.
4
예제6: (함수의 갯수) 원소가 m개인 집합으로부터 원소가 n개인 집합으로의 함수는 모두 몇 가지가 있는가?
예제7: (1대1 함수의 갯수) 원소가 m개인 집합으로부터 원소가 n개인 집합으로의 1대1 함수는 모두 몇 가지가 있는가?
5
예제10: (유한집합의 부분집합 계수) 유한집합 S의 서로 다른 부분집합의 개수는 2|*|임을 곱셈 법칙을 이용하여 증명하라.
예제13: 한 학생이 컴퓨터 과제를 수행하는 데, 세 개의 리스트 중에서 하나를 선택 할 수 있다. 세 개의 리스트는 각각 23, 15, 19가지의 과제물을 포함하고 있을 때, 과 제를 선택하는 방법은 모두 몇 가지나 가능한가?
6
예제9: 다음의 코드가 실행된 후 K의 값은 얼마인가?
단, 𝑛",𝑛#, … , 𝑛-은 모두 양의 정수들이다.
7
𝑘 ≔ 0
for 𝑖" ≔ 1 to 𝑛"
for 𝑖# ≔ 1 to 𝑛# ..
for 𝑖.- ≔ 1 to 𝑛- 𝑘 ≔ 𝑘 + 1
예제14: 다음의 코드를 수행한 후 k의 값은 무엇인가?
단, 𝑛",𝑛#, … , 𝑛-은 양의 정수이다.
8
𝑘 ≔ 0
for 𝑖" ≔ 1 to 𝑛"
𝑘 ≔ 𝑘 + 1 for 𝑖# ≔ 1 to 𝑛#
𝑘 ≔ 𝑘 + 1 ..
for 𝑖-.≔ 1 to 𝑛- 𝑘 ≔ 𝑘 + 1
예제16: 컴퓨터 시스템의 사용자는 6에서 8개의 글자로 패스워드를 구성하는데, 각 글자는 대문자이거나 숫자이고 적어도 한 개의 숫자가 있어야 한다.
가능한 패스워드의 수는 얼마인가?
9
포함-배제의 원리
포함-배제의 원리: |A∪B| = |A| + |B| - |A∩B|
예제18: 1로 시작하거나 00으로 끝나는 길이 8의 비트 문자열은 모두 몇 개인가?
10
예제19: 한 컴퓨터 회사가 일련의 새 웹 서버들을 설치하는 작업을 위해 새 직원 모 집을 공고하였고 이에 관련 졸업생 350명이 신청하였다. 신청자 중 220명이 컴퓨터 과학을 전공하였고 147명이 비즈니스(business)를, 그리고 51명이 컴퓨터과학과 비 즈니스를 같이 전공하였다면 컴퓨터과학도 비즈니스도 전공하지 않은 지원자는 총 몇 명인가?
11
예제20: 4인용 원형 탁자에 4명의 사람들은 앉힐 수 있는 서로 다른 방법의 수를 구 하시오. 단, 자신의 왼쪽 옆과 오른쪽 옆에 같은 사람들이 앉아 있는 경우는 같은 방 법으로 간주한다.
12
트리 도표 이용하기
예제21: 연속된 두 개의 1을 갖지 않는 길이 4의 비트 문자열은 모두 몇 개인가?
풀이:
13
예제22: 두 팀 간의 플레이오프는 최대 5번으로 진행되며 먼저 3경기를 이기는 팀 이 플레이오프의 승자가 된다. 플레이오프가 진행되는 방법은 모두 몇 가지인가?
풀이:
14
예제22: 두 팀 간의 플레이오프는 최대 5번으로 진행되며 먼저 3경기를 이기는 팀 이 플레이오프의 승자가 된다. 플레이오프가 진행되는 방법은 모두 몇 가지인가?
풀이:
15
