계수와 응용 (Counting and Its Applications) 이산수학(Discrete Mathematics) 계수와 응용 (Counting and Its Applications) 2016년 봄학기 강원대학교 컴퓨터과학전공 문양세

계수의 기본 원리(Basics of Counting) 비둘기 집 원리(The Pigeonhole Principle) 강의 내용 Counting and Its Applications 계수의 기본 원리(Basics of Counting) 비둘기 집 원리(The Pigeonhole Principle) 순열과 조합(Permutations and Combinations)

Combinatorics (계수) 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 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 (집합 이론적 해석) 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) Basics of Counting 예제: 한 개의 대문자(A~Z)와 100이하(1~100)의 양의 정수를 사용하여, 의자에 번호(예: A36)를 붙이려 한다. 서로 다르게 번호를 붙일 수 있는 의자는 최대 몇 개인가? 대문자 개수 = 26개, 숫자 개수 = 100개 가능한 조합 = 26 x 100 = 2600개 ( We use product rules)

Examples of Product Rules (2/4) Basics of Counting 예제: 자동차 번호판이 대문자 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) Basics of Counting 예제(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) Basics of Counting 예제(가능한 전화번호 개수): 전화번호가 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) Basics of Counting 예제 (대표자 선발): 위원회에 컴퓨터과학전공 교수 8명, 같은 과 학생 150명이 포함되어 있고, 이중에서 한 명을 대표로 선발한다고 할 때, 가능한 경우의 수는? 교수 중 한 명이 대표가 되는 경우의 수 = 8 학생 중 한 명이 대표가 되는 경우의 수 = 150 대표를 뽑는 경우의 수 = 8 x 150 ?  Oh, NO 8 + 150 = 158  Ok. It is because “either … or …”

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

Password Example Basics of Counting 예제 (패스워드 가지 수): 패스워드는 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) 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 address 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) 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 (포함 배제 원리) 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|.

계수의 기본 원리(Basics of Counting) 비둘기 집 원리(The Pigeonhole Principle) 강의 내용 Counting and Its Applications 계수의 기본 원리(Basics of Counting) 비둘기 집 원리(The Pigeonhole Principle) 순열과 조합(Permutations and Combinations)

Pigeonhole Principle (비둘기 집 원리) The Pigeonhole Principle A.k.a.(as known as) Dirichlet drawer principle (또한, “디리크레의 서랍 원리”라고도 알려짐) If ≥k+1 objects are assigned to k places, then at least 1 place must be assigned ≥2 objects. (k+1개의 객체(비둘기)가 k개의 장소(상자, 비둘기 집)에 배분된다면, 적어도 한 곳은 두 개 이상의 객체가 배분된다.) In terms of the assignment function: If f:A→B and |A|≥|B|+1, then some element of B has ≥2 preimages under f. That is, f is not one-to-one.

Examples of Pigeonhole Principle (1/3) The Pigeonhole Principle 예제(생일 문제): 367명의 사람이 있다면 적어도 두 명은 생일이 같다. 가능한 생일은 366개이고, 사람이 이보다 하나 많다. 장소(생일)는 366개인데, 객체(사람)는 367이므로, 적어도 두 명은 생일이 같게 된다. 예제(성적 부여 문제): 0점에서 100점까지 1점 단위로 채점을 하게 되었을 때, 적어도 두 명의 학생이 점수가 같다 하면, 학생은 몇 명이 있어야 하는가? 가능한 점수(장소)는 0, 1, …, 99, 100의 101개이고, 점수에 할당되는 학생(객체)이 102명이면, 두 명은 점수가 같게 된다.

Examples of Pigeonhole Principle (2/3) The Pigeonhole Principle 예제(n의 배수 문제): 정리: 모든 정수 n에 대해서, n의 배수 중에는 0과 1만을 포함하는 십진수가 반드시 존재한다. n을 양의 정수라 하고, n+1개의 정수 1, 11, 111, …, 111  1(1이 n+1개)가 있다고 하자. 어떤 정수를 n으로 나누었을 때, 가능한 나머지의 개수는 최대 n개이다. (나머지의 가능한 범위는 0 ~ n-1 이므로) 따라서, 비둘기 집 원리에 의해 상기 n+1개의 정수 중에서 적어도 두 수는 나머지가 같게 된다. 이들 두 수를 각각 x와 y라 하자(x > y). 이 두 수 x와 y의 차를 z(= x – y)라 했을 때, z는 n으로 나누어 떨어지고, 이 수는 0과 1로만 표현된다. (x%n = y%n 이므로, z%n = 0이 된다.) Please refer to an example in the next slide.

Examples of Pigeonhole Principle (3/3) The Pigeonhole Principle Let n = 3. Consider 1, 11, 111, 1111. 1 % 3 = 1 11 % 3 = 2 111 % 3 = 0 1,111 % 3 = 1 1,111 – 1 = 1,110 = 370 x 3 It has only 0’s and 1’s in its expansion. 1,110 mod 3 = 0, so it’s a multiple of 3.

Generalized Pigeonhole Principle (G.P.P.) The Pigeonhole Principle If N objects are assigned to k places, then at least one place must be assigned at least N/k objects. (N개의 객체가 k개 장소에 배정된다면, 적어도 한 곳은 N/k개 객체를 가진다.) E.g., there are N=280 students in this class. (학생 280명) There are k=52 weeks in the year. (한 해는 52주) Therefore, there must be at least 1 week during which at least 280/52= 5.38=6 students in the class have a birthday. (일반화된 비둘기 집 원리에 의해서) 최소 6명의 학생은 같은 주에 생일이 들어 있게 된다.

예제(생일이 같은 달…): 100명 중에서 적어도 몇 명은 같은 달에 태어났다고 볼 수 있는가? G.P.P. Examples (1/3) The Pigeonhole Principle 예제(생일이 같은 달…): 100명 중에서 적어도 몇 명은 같은 달에 태어났다고 볼 수 있는가? 100/12 = 9명 적어도 9명은 태어난 달이 같게 된다.

G.P.P. Examples (2/3) The Pigeonhole Principle 예제(카드 문제): 52장의 카드에서 적어도 3장은 같은 무늬가 나오는 것을 보장하기 위해서는 몇 장의 카드를 선택해야 하는가? 2 x 4 + 1 = 9장 8장을 선택하면, 최악의 경우에 같은 무늬가 두 장씩이고, 여기에 한 장만 추가하면, 적어도 세 장은 같은 무늬가 된다. 적어도 3장의 하트 무늬 카드가 선택되기 위해서는 몇 장을 골라야 하나? 13 x 3 + 3 = 42장 (재수 없게, 최악의 경우에) 클로버, 다이아몬드, 스페이드가 13장씩 선택된다면, 추가로 3장을 더 선택하면 이것은 모두 하트 무늬가 된다.

G.P.P. Examples (3/3) The Pigeonhole Principle 예제(야구 경기 문제): 한 달이 30일 때, 야구 팀이 매일 적어도 한 경기씩 경기를 하는데, 45경기 이하를 한다. 그러면, 이 팀이 14경기를 연속적으로 하는 기간이 반드시 존재함을 증명하라. (즉, ith day에서 jth day까지의 경기 합이 반드시 14인 ith day와 jth day가 존재함을 증명하라.) 먼저, kth day까지의 누적 경기 수를 ak라 하면, a1, a2, …, a30은 증가하는 양의 수열이고, 1 ak  45이다. 또한, a1+14, a2+14, …, a30+14 도 증가하는 양의 수열이다. 이때, 60개의 양의 정수 a1, a2, …, a30, a1+14, a2+14, …, a30+14 는 모두 59이하이다. (ak가 45이하이므로) 따라서, 비둘기 집 원리에 의해, 이들 60개 중 적어도 두 개는 같은 수가 된다. 그런데, a1, a2, …, a30는 모두 다른 수이고, a1+14, a2+14, …, a30+14 도 모두 다른 수이므로, ai = aj + 14를 만족하는 i와 j가 반드시 존재한다. 결국, j+1번째 날에서 i번째 날까지는 정확히 14 경기를 하게 된다.

계수의 기본 원리(Basics of Counting) 비둘기 집 원리(The Pigeonhole Principle) 강의 내용 Counting and Its Applications 계수의 기본 원리(Basics of Counting) 비둘기 집 원리(The Pigeonhole Principle) 순열과 조합(Permutations and Combinations)

Permutations (순열) Permutations & Combinations A permutation of a set S of objects is a sequence containing each object once. (객체들의 집합 S에 대한 순열이란 해당 객체들이 한번씩 나오는(객체들을 한번씩 포함하는) 시퀀스를 의미한다.) An ordered arrangement of r distinct elements of S is called an r-permutation. (집합 S에 포함된 r개의 원소들을 순서대로 나열하는 방법을 r-순열이라 한다.) The number of r-permutations of a set with n=|S| elements is (n개 중 r개를 선택하여 나열하는 방법은)

Permutation Examples (1/2) Permutations & Combinations 예제(경품을 탑시다..): 100명이 참여한 경품 행사에서, 1등, 2등, 3등을 한 명씩 선발하는 방법은 모두 몇 가지 인가? 3등을 선발하는 방법 = 100가지 2등을 선발하는 방법 = 99가지 1등을 선발하는 방법 = 98가지 결국, 100 x 99 x 98 = 970,200가지 이다. 순열을 활용하면…. 100명 중에서 세 명을 뽑아서 순서대로 나열하는 방법… 결국, P(100,3) = 970,200가지 이다.

Permutation Examples (2/2) Permutations & Combinations 예제(외판원 문제): 외판원이 8개의 도시를 방문해야 한다. 출발 도시는 춘천으로 정해져 있다고 할 때, 이들 도시를 방문하는 순서의 가지 수는? 첫 번째 도시 선택하는 방법 = 7가지 두 번째 도시 선택하는 방법 = 6가지 … 결국, 7 x 6 x 5 x 4 x 3 x 2 x 1 = 7! = 5,040가지 이다. 순열을 활용하면…. 한 개는 이미 결정되어 있으므로, 7개의 도시에서 7개 모두를 선택하여 순서대로 나열하는 방법의 수는… 결국, P(7,7) = 7! = 5,040가지 이다.

Combinations (조합) (1/2) Permutations & Combinations An r-combination of elements of a set S is simply a subset TS with r members, |T|=r. (집합 S의 r-조합이란, r개의 원소를 가지는 S의 부분집합 T의 개수이다.) (집합 S에서 r개의 원소(순서 무관)를 선택하는 방법의 개수이다.) The number of r-combinations of a set with n=|S| elements is (n개 원소를 갖는 집합 S에 대한 r-조합의 개수는)

Note that C(n,r) = C(n, n−r) Combinations (조합) (2/2) Permutations & Combinations Note that C(n,r) = C(n, n−r) Because choosing the r members of T is the same thing as choosing the n−r non-members of T. T에서 r개의 member를 선택하는 방법은 T에서 (n-r)개의 non-member를 선택하는 방법과 동일하다.

Combination Examples (1/2) Permutations & Combinations 예제(선수를 뽑읍시다): 10명으로 구성된 팀에서 경기에 나갈 선수 5명을 선발하는 방법은 모두 몇 가지인가? 10명 중에서 5명을 선발하되, 5명의 순서는 고려할 필요가 없으므로, 10개의 원소 집합에서 5-조합의 수를 구하는 문제임 결국, 252가지 이다.

Combination Examples (2/2) Permutations & Combinations 예제(비트 문자열 문제): 길이 10인 비트 문자열에서 1을 정확히 5개 포함하는 가능한 문자열의 개수는 몇 개인가? 일반화  길이 n인 문자열에서 1을 r개 포함하는 문자열 개수는? 각 비트 위치의 집합을 S = {1, 2, 3, …, n}이라 하면, 이 문제는 n개 원소를 가지는 집합 S에서 r개의 원소를 선택하는 방법으로 볼 수 있다. 결국, C(n, r)로 답을 구할 수 있게 된다. 상기 문제의 경우, n = 10, r = 5이므로, C(10, 5) = 252개이다.

계수의 기본 원리(Basics of Counting) 비둘기 집 원리(The Pigeonhole Principle) 강의 내용 Counting and Its Applications 계수의 기본 원리(Basics of Counting) 비둘기 집 원리(The Pigeonhole Principle) 순열과 조합(Permutations and Combinations)

Programming Assignment #2 Homework #6 Counting and Its Applications Homework #6 & Programming Assignment #2