4.1 계수의 기본 원리 (Basics of Counting) 이산수학 (Discrete Mathematics) 4.1 계수의 기본 원리 (Basics of Counting) 2006년 봄학기 문양세 강원대학교 컴퓨터과학과

We will cover … in Chapter 4. 4.1 Basics of Counting $4.1 Basics of Counting (계수의 기본 원리) $4.2 The Pigeonhole Principle (비둘기 집 원리) $4.3 Permutations and Combinations (순열과 조합)

Combinatorics (계수) 4.1 Basics of Counting The study of the number of ways to put things together into various combinations. (주어진 물건을 여러 가지 조합으로 묶는 여러 가지 방법에 대한 연구이다.) E.g. In a contest entered by 100 people, how many different top-10 outcomes could occur? (100명이 참여한 경연에서 톱10이 구성되는 모든 경우의 수는?) E.g. If a password is 6-8 letters and/or digits, how many passwords can there be? (패스워드가 6-8개의 글자/숫자로 구성된다면, 가능한 패스워드의 개수는?)

Sum and Product Rules 4.1 Basics of Counting Let m be the number of ways to do task 1 and n the number of ways to do task 2 (with each number independent of how the other task is done), and assume that no way to do task 1 simultaneously also accomplishes task 2. (타스크 1을 수행하는데 m개, 타스크 2를 수행하는데 n개의 방법이 있다 하자(이때, 두 타스크는 독립적이다). 또한, 두 개의 타스크는 동시에 수행될 수 없다고 가정하자.) The sum rule: The task “do either task 1 or task 2, but not both” can be done in m+n ways. (덧셈 법칙: 둘 중 하나만 수행하는 경우) [예: 주사위 혹은 동전 던지기] The product rule: The task “do both task 1 and task 2” can be done in mn ways. (곱셈 법칙: 두 타스크를 모두 수행해야 하는 경우) [예: 주사위 던지고 동전도 던지기]

Set Theoretic Version (집합 이론적 해석) 4.1 Basics of Counting If A is the set of ways to do task 1, and B the set of ways to do task 2, and if A and B are disjoint, then: (A는 타스크 1을 수행하는 방법의 집합이고, B는 타스크 2를 수행하는 방법의 집합이며, A와 B는 서로 소자 하자. 그러면, 다음이 성립한다.) The ways to do either task 1 or 2 are AB, and |AB|=|A|+|B| (타스크 1과 2중 하나를 수행하는 경우의 수는 합집합으로 해석된다.) The ways to do both task 1 and 2 can be represented as AB, and |AB|=|A|·|B| (타스크 1과 2 모두를 수행하는 경우의 수는 카티젼 콥으로 해석된다.)

Examples of Product Rules (1/4) 4.1 Basics of Counting 예제 1: 한 개의 대문자(A~Z)와 100이하(1~100)의 양의 정수를 사용하여, 의자에 번호(예: A36)를 붙이려 한다. 서로 다르게 번호를 붙일 수 있는 의자는 최대 몇 개인가? 대문자 개수 = 26개, 숫자 개수 = 100개 가능한 조합 = 26 x 100 = 2600개 ( We use product rules)

Examples of Product Rules (2/4) 4.1 Basics of Counting 예제 4: 자동차 번호판이 대문자 3개(예: ABC)와 숫자 3개(예: 456)로 구성된다면(예: ABC456), 서로 다른 번호판은 모두 몇 개인가? 대문자 개수 = 26개  번호의 앞부분 세 자리에 대한 경우의 수 = 26 x 26 x 26 숫자 개수 = 10개  번호의 뒷부분 세 자리에 대한 경우의 수 = 10 x 10 x 10 서로 다른 가능한 번호판의 수 = 26 x 26 x 26 x 10 x 10 x 10 = 17,576,000

Examples of Product Rules (3/4) 4.1 Basics of Counting 예제 6(1대 1 함수의 계수): 원소가 m개인 집합에서 원소가 n개인 집합으로의 1대 1 함수는 모두 몇 가지 인가? m > n: 1대 1 함수가 존재할 수 없다. m  n: 정의역(domain)의 원소를 a1, a2, …, am이라 하자. a1에서 상(image)을 선택하는 방법은 n가지이다. a2에서는 (n-1)가지, a3에서는 (n-2)가지, …, am에서는 (n-m+1)가지이다. 결국, 가능한 모든 가지 수는 n(n-1)(n-2)(n-m+1)이다. 예: 원소 3개인 집합에서 원소 5개인 집합으로의 1대 1 함수는? 5 x 4 x 3 = 60개

Examples of Product Rules (4/4) 4.1 Basics of Counting 예제 7(가능한 전화번호 개수): 전화번호가 NYX-NNX-XXXX의 체계를 가지고, N, Y, X는 각각 N=2~9, Y=0/1, X=0~9의 범위를 가질 때 가능한 전화번호의 개수는? NYX: 8 x 2 x 10 = 160개 (예: 지역번호) NNX: 8 x 8 x 10 = 640개 (예: 국번호) XXXX: 10 x 10 x 10 x 10 = 10,000개 결국, 160 x 640 x 10,000 = 1,024,000,000개의 전화번호가 가능하다.

Examples of Sum Rules (1/2) 4.1 Basics of Counting 예제 10(대표자 선발): 위원회에 컴퓨터과학과 교수 8명, 같은 과 학생 150명이 포함되어 있고, 이중에서 한 명을 대표로 선발한다고 할 때, 가능한 경우의 수는? 교수 중 한 명이 대표가 되는 경우의 수 = 8 학생 중 한 명이 대표가 되는 경우의 수 = 150 대표를 뽑는 경우의 수 = 8 x 150 ?  Oh, NO 8 + 150 = 158  Ok. It is because “either … or …”

Examples of Sum Rules (2/2) 4.1 Basics of Counting 예제 11(과제 선택 방법): 컴퓨터 과제를 하나 선택하여 수행하는 데 있어서, 세 개의 리스트 중에서 하나를 선택할 수 있고, 세 개의 리스트는 각각 23, 15, 19개의 과제를 포함할 때, 과제를 선택할 수 있는 방법은? 첫 번째 리스트에서 과제를 선택하는 경우의 수 = 23 두 번째 리스트에서 과제를 선택하는 경우의 수 = 15 세 번째 리스트에서 과제를 선택하는 경우의 수 = 19 과제 선택 방법 = 23 + 15 + 19 = 57가지

Password Example 4.1 Basics of Counting 예제 14 (패스워드 가지 수): 패스워드는 6~8 글자로 구성되는데, 각 글자는 대문자이거나 숫자이고, 적어도 한 글자는 숫자가 포함되어야 할 때, 가능한 패스워드의 개수는? 여섯 자리인 경우의 수 = 여섯 자리인 모든 경우의 수 – 숫자를 포함하지 않는 경우의 수 = (26 + 10)6 + 266 = 1,867,866,560. 일곱 자리인 경우의 수 = (26 + 10)7 + 267 = 70,332,353,920. 여덟 자리인 경우의 수 = (26 + 10)8 + 268 = 2,612,282,842,880. 결국, 상기 세 가지 경우를 모두 합한 2,684,483,063,360가지이다.

Some facts about Internet Protocol version 4(IPv4): IP Address Example (1/2) 4.1 Basics of Counting Some facts about Internet Protocol version 4(IPv4): Valid computer addresses are in one of 3 types: A class A IP address contains a 7-bit “netid” ≠ 17, and a 24-bit hostid” (클래스 A는 netid로 7 bits를 사용하나, 1111111은 사용치 않는다.) A class B address has a 14-bit netid and a 16-bit hostid. (클래스 B는 netid로 14 bits를 사용하고, 16 bits는 hostid로 사용한다.) A class C addr. Has 21-bit netid and an 8-bit hostid. (클래스 C는 netid로 21 bits를 사용하고, 8 bits는 hostid로 사용한다.) The 3 classes have distinct headers (0, 10, 110). Hostids that are all 0s or all 1s are not allowed. (모두 0이나 1일 수는 없다. 즉, “0.0.0.0”이나 “255.255.255.255”는 제외한다.) How many valid computer addresses are there?

IP Address Example (2/2) 4.1 Basics of Counting (# addresses) = (# class A) + (# class B) + (# class C)  덧셈 법칙 # class A = (# valid netids) x (# valid hostids)  곱셈 법칙 (# valid class A netids) = 27 − 1 = 127. (# valid class A hostids) = 224 − 2 = 16,777,214. Continuing in this fashion we find the answer is: 3,737,091,842 (3.7 billion IP addresses) However, the space will be insufficient!  IPv6 (256 bits)

Inclusion-Exclusion Principle (포함 배제 원리) – skip 4.1 Basics of Counting Suppose that km of the ways of doing task 1 also simultaneously accomplish task 2. (타스크 1을 수행하는 동시에 타스크 2를 수행할 수 있는 경우, 즉, 두 타스크가 동시에 수행될 수 있는 경우) Then the number of ways to accomplish “Do either task 1 or task 2” is mnk. (1 혹은 2를 수행하는 경우의 수는, 둘 중 하나를 수행하는 경우의 수에서 둘 다 수행하는 경우의 수를 뺀 값이다.) Set theory: If A and B are NOT disjoint, then |AB|=|A||B||AB|.

Inclusion-Exclusion Example (1/2) – skip 4.1 Basics of Counting Another password example: Passwords must be 2 characters long. (패스워드는 반드시 두 글자로 구성되어야 한다.) Each password must be a letter a-z, a digit 0-9, or one of the 10 punctuation characters !@#$%^&*(). (패스워드는 소문자, 숫자, 구두점 문자로 구성될 수 있다.) Each password must contain at least 1 digit or punctuation character. (패스워드는 적어도 한 글자 이상의 구두점 혹은 숫자를 포함하여야 한다.)

Inclusion-Exclusion Example (2/2) – skip 4.1 Basics of Counting A legal password has a digit or punctuation character in position 1 or position 2. (# of passwords w. OK symbol in position #1) = (10+10)·(10+10+26) = 20·46 = 920 (# of passwords w. OK symbol in position #2) = also 20·46 = 920 (# of passwords w. OK symbol both places) = 20·20 Thus, the answer is 920+920−400 = 1,440