(Permutations and Combinations)

Presentation on theme: "(Permutations and Combinations)"— Presentation transcript:

1 (Permutations and Combinations)
이산수학 (Discrete Mathematics) 4.3 순열과 조합 (Permutations and Combinations) 2006년 봄학기 문양세 강원대학교 컴퓨터과학과

2 Permutations (순열) 4.3 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개를 선택하여 나열하는 방법은)

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

4 Permutation Examples (2/2)
4.3 Permutations & Combinations 예제 4(외판원 문제): 외판원이 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! = 970,220가지 이다.

5 Combinations (조합) (1/2) 4.3 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-조합의 개수는)

6 Note that C(n,r) = C(n, n−r)
Combinations (조합) (2/2) 4.3 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를 선택하는 방법과 동일하다.

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

8 Combination Examples (2/2)
4.3 Permutations & Combinations 예제 10(비트 문자열 문제): 길이 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개이다.

9 Homework #6 $4.1의 연습문제: 2, 8, 24 $4.2의 연습문제: 2, 5, 13
4.3 Permutations & Combinations $4.1의 연습문제: 2, 8, 24 $4.2의 연습문제: 2, 5, 13 $4.3의 연습문제: 10, 16, 20(b, c) Due Date: