9장
순열,이산적확률,재귀적관계
• 경우의 수(number of cases)
• 일어날 수 있는 모든 사건의 수
• 트리를 이용하여 구하는 방법과 표를 이용하여 구하는 방법이 있음
• 예제 1 : 두 개의 주사위 A, B를 동시에 던졌을 때 주사의 눈의 합이 홀수가 나오는 경우의 수를 구하라.
1. 경우의 수
경우의 수
A
B1
1 2 3 4 5 6
A
B2
1 2 3 4 5 6
A
B3
1 2 3 4 5 6
A
B4
1 2 3 4 5 6
A
B5
1 2 3 4 5 6
A
B6
1 2 3 4 5 6 6ⅹ3=18
1. 경우의 수
• 경우의 수 법칙
• 합의 법칙(rule of sum) : 두 사건 A와 B가 서로 소일 때(즉, A∩B=Ø) 사건 A 또는 B가 일어날 경우의 수는 두 사건이 각각 일 어날 경우의 수를 n(A)=n, n(B)=m이라 할 때 n+m임
•
곱의 법칙(rule of product) : 두 사건 A와 B가 서로 소일 때(즉,
A∩B=Ø) 사건 A와 B가 동시에 일어날 경우의 수는 두 사건이 각 각 일어날 경우의 수를 n(A)=n, n(B)=m이라 할 때 nⅹm임• 예제 2 : A 지역과 B 지역 사이에 길이 3개 있고, B 지역과 C 지 역 사이에 길이 2개 있다.
• A 지역에서 출발하여 반드시 B 지역을 거쳐 C 지역으로 가 는 길의 경우의 수를 구하라.
• A→B : 3, B→C : 2이므로 A→B→C는 3ⅹ2=
6
• A 지역에서 출발하여 반드시 B 지역을 거쳐 C 지역으로 갔 다가 C 지역에서 다시 B 지역을 거쳐 A 지역으로 돌아오는 길의 경우의 수를 구하라.
• A→B : 3, B→C : 2이므로 A→B→C는 3ⅹ2=6이고, C→B : 2, B→A : 3이므로 C→B→A는 2ⅹ3=6이고, 이 둘을 곱하므로 6 A→B : 3, B→C : 2이므로 A→B→C는 6ⅹ6=36
1. 경우의 수
• 예제 3 : 어떤 시스템에서 한 자리 또는 두 자리로 된 ID를 만들 수 있다. 이 때 첫 자리는 대소문자 구분 없이 무조건 영문자여야 하고, 두 번째 자리는 대소문자 구분 없이 영문자 또는 숫자여야 한다. 이 시스템에서 만들 수 있는 ID의 총 개수는?
• 한 자리 ID : 첫 자리는 대소 구분 없이 영문자이므로 26개
• 두 자리 ID : 첫 자리는 대소 구분 없이 영문자이므로 26개, 두 번째 자리는 대소 구분 없이 영문자 26개 또는 숫자 10개 이므로 36개, 즉 26개ⅹ36개=936개
• 한 자리 또는 두 자리 ID의 개수는 26개+936개=
962개
• 예제 4 : 영문 대문자로 구성된 5자리 ID를 만들려고 한다. 첫 문자 또는 마지막 문자가 A인 경우의 수는?
• A가 첫 문자 또는 마지막 문자로만 사용된 경우 : A****로 구성되는 ID는 26개ⅹ26개ⅹ26개ⅹ26개=456,976개, ****A 로 구성되는 ID는 26개ⅹ26개ⅹ26개ⅹ26개=456,976개
• A가 첫 문자와 마지막 문자 모두로 사용된 경우 : A***A로 구성되는 ID는 26개ⅹ26개ⅹ26개=17,576개
• 456,976개+456,976개+17,576개=
931,528개
2. 순열
• 순열(permutation)
• 서로 다른 원소들을 순서를 고려하여 나열하는 것을 말하는데 서로 다른 n개의 원소를 한 줄로 배열하는 순열의 수는 nⅹ(n-1)ⅹ(n- 2)ⅹ…ⅹ3ⅹ2ⅹ1이고, 통상 n!(팩토리알)이라고 함
• 서로 다른 n개의 원소 중에서 r개를 선택하는 순열의 수는 nⅹ(n- 1)ⅹ(n-2)ⅹ…ⅹ(n-r+1), (단, 0<r≤n) 이고, 이를 nPr로 나타냄 순열
2. 순열
• 예제 1 : 학생 6명 중에 3명을 선택하여 줄을 세우는 경우의 수 를 구하라.
• 6P3이므로 n=6, r=3으로 놓고 계산하면 6ⅹ(6-1)ⅹ(6- 3+1)=6ⅹ5ⅹ4=120
• 예제 2 : 서로 다른 4개의 문자 A, B, C, D를 이용해서 만들 수 있는 문자열에 대해 사전적 순서로 BDAC는 몇 번째 순서인가?
• A로 시작하는 문자열은 A***이므로 A와 관계없이 B, C, D 세 개의 문자열을 나열하는 방법으로 3P3=3!=3ⅹ2ⅹ1=6
• B로 시작하고 그 다음에 A가 나오는 문자열은 BA**이므로 B, A와 관계없이 C, D 두 개의 문자열을 나열하는 방법으로
2P2=2!=2ⅹ1=2
• 문자는 1개씩이므로 B로 시작하고 그 뒤에 B가 올 수 없음
• B로 시작하고 그 다음에 C가 나오는 문자열은 BC**이므로 B, C와 관계없이 A, D 두 개의 문자열을 나열하는 방법으로
2P2=2!=2ⅹ1=2
• B로 시작하고, 그 뒤에 D가 오는 문자열 중에는 BDAC가 제일 앞이므로 6+2+2+1=11번째 문자열임
2. 순열
B
y
2. 순열
• 중복 순열(permutation with repetition)
• 서로 다른 n개의 원소 중 중복을 허용하여 r개를 선택하여 나열 하는 것으로 다음과 같이 구함
• n∏r=nr
• 예제 5 : 0부터 9까지 총 10개의 숫자가 3열로 나열되어 있고, 그 중 각 줄에서 하나씩의 숫자를 선택하여 잠그는 자물쇠에서 만 들 수 있는 비밀번호의 개수는?
• n∏r=nr=10∏3=103=1,000
• 예제 6 : A, B, C, D, E 5개의 문자 중에서 3개의 문자를 골라 나 열할 때 (1) 중복을 허락하지 않을 때와 (2) 중복을 허락할 때 각 각 몇 가지 경우가 나오는가?
• (1) 중복을 허락하지 않을 때 : 5P3이므로 5ⅹ4ⅹ3=60
• (2) 중복을 허락할 때 : 5∏3=53=125
• 예제 7 : 숫자의 중복을 허락하면서 0, 1, 2, 3, 4로 만 단위의 숫 자를 만든다면 몇 가지 경우가 나오는가?
• 만의 자리에는 1, 2, 3, 4 등 4개만 올 수 있고, 천의 자리 이하는 0, 1, 2, 3, 4 모두 올 수 있으므로 4ⅹ 5∏4=54=2,500
3. 조합
• 조합(combination)
• 서로 다른 n개의 원소 중에서 순서를 고려하지 않고 r개를 선택하는 것 조합
3. 조합
3. 조합
• 이항 계수(binomial coefficient)
• (a+b)n을 전개해서 나오는 식을 이항 정리(binomial theorem)라 하 고, 이 때 nCr을 이항 계수라고 함
• 예제 4
• (a+b)3=a3+3a2b+3ab2+b3
• (a+b)4=1a4+4a3b+6a2b2+4ab3+1b4
• n=4, r=0일 때 : 4C0=1
• n=4, r=1일 때 : 4C1=4
• n=4, r=2일 때 : 4C2=6
• n=4, r=3일 때 : 4C3=4
• n=4, r=4일 때 : 4C4=1 이항 계수
3. 조합
• 파스칼의 삼각형(Pascal’s triangle)
• 이항 정리에서 이항 계수를 만들어주는 다음 식
• n-1Cr-1+n-1Cr=nCr
•
(a+b)
0=1
•
(a+b)
1=a+b
•
(a+b)
2=a
2+2ab+b
2•
(a+b)
3=a
3+3a
2b+3ab
2+b
3•
(a+b)
4=a
4+4a
3b+6a
2b
2+4ab
3+b
4•
(a+b)
5=a
5+5a
4b+10a
3b
2+10a
2b
3+5ab
4+b
54. 이산적 확률과 통계
확률
4. 이산적 확률과 통계
4. 이산적 확률과 통계
5. 비둘기 집 원리
• 비둘기 집 원리(pigeonhole principle)
• n개의 비둘기 집과 n+1 마리의 비둘기가 있다면 n개의 비둘기 집 중 어딘가에는 2마리 이상의 비둘기가 들어있다는 원리로, 19세기 말 프랑스의 수학자 디리클레(Peter Gustav Lejeune Dirichlet)에 의 해 제안된 원리
• 예 : 서울의 인구를 1,000만 명으로 봤을 때 머리카락의 수가 같은 사람은 얼마나 될 지 추정하라.
• 인간의 머리카락 수는 10만~15만개라고 하는데 계산하기 용 이하게 10만개라고 가정하고 머리카락의 수 10만개를 비둘기 집의 수로, 서울의 인구 1,000만 명을 비둘기의 수로 가정함
• 머리카락의 수가 1개인 경우부터 10만개인 경우까지를 비둘기 집 번호 1번부터 10만 번까지로 할당
• 여기에 서울시의 인구 1,000만 명을 한 명씩 할당하면 한 번호 에 반드시 100명은 할당되기 때문에 최소한 100명은 머리카락 의 수가 같다고 추정됨
비둘기 집 원리
6. 재귀적 정의
• 재귀적 정의(recursive definition)
• 첫 번째 요소가 정의되고, n+1번째 요소는 n번째 요소와 그 앞의 요소들로 정의할 수 있을 때 ‘재귀적’이라 말하고, 재귀적인 경우는
재귀적 관계(recursive relation)로 문제를 해결할 수 있음
• 주어진 문제를 원래와 똑같은 개념의 더 작은 문제로 분할할 수 있 고, 가장 작은 문제로 분할한 후 문제를 해결하여 전 단계로 전할 수 있어야 함
• 예를 들어, 팩토리알 계산은 전형적인 재귀적 관계임
• n!=nⅹ(n-1)!
• (n-1)!=(n-1)ⅹ(n-2)!
• (n-2)!=(n-2)ⅹ(n-3)!
• 3!=3ⅹ2!
• 2!=2ⅹ1!(1!=1)
• ‘재귀’는 ‘순환’ 또는 ‘되부름’이라는 이름으로 컴퓨터 프로그램 개 발에 많이 사용되는 기법임
재귀적 관계식
6. 재귀적 정의
• 예제 1 : f(0)=1, f(n+1)=2f(n)+1로 정의되었을 때 f(1), f(2), f(3), f(4), f(5)의 값을 구하라.
• f(1)=2f(0)+1=2ⅹ1+1=3
• f(2)=2f(1)+1=2ⅹ3+1=7
• f(3)=2f(2)+1=2ⅹ7+1=15
• f(4)=2f(3)+1=2ⅹ15+1=31
• f(5)=2f(4)+1=2ⅹ31+1=63
• 예제 2 : 0!=1, 1!=1일 때 5!을 구하라.
• 5!=5ⅹ4!=5ⅹ4ⅹ3!=5ⅹ4ⅹ3ⅹ2!=5ⅹ4ⅹ3ⅹ2ⅹ1!=
5ⅹ4ⅹ3ⅹ2ⅹ1
int factorial(int n) {
if(n <= 1) return 1;
else
return n*factorial(n-1);
}
7. 피보나치 수와 하노이 탑
• 피보나치 수(Fibonacci number)
• Fib(0)=0, Fib(1)=1
• Fib(n)=Fib(n-1)+Fib(n-2), n=2, 3, 4, …
• 피보나치 수 : 0, 1, 1, 2, 3, 5, 8, 13, … 피보나치 수
int include<stdio.h>
inf( fib(int n) {
if(n==0) return(0);
else if(n==1) return(1);
else return(fib(n-1)+fib(n-2));
}
int main (void) {
int i, n;
int result;
printf(“구하려는 피보나치 값 입력 : “);
scanf(“%d”, &n);
result=fib(n);
printf(“＼nFib(%d)=“, n);
if(n==0 || n==1) printf(“%d＼n＼n”, result);
else printf(“%d + %d = %d＼n＼n”, fib(n-2), fib(n-1), result);
}
7. 피보나치 수와 하노이 탑
• 하노이 탑(Tower of Hanoi)
• 고대 인도의 베나레스라는 지방에 큰 사원이 하나 있었는데 이 사 원에는 다이아몬드 막대가 3개 있고, 그 중 한 막대에 크기가 다른 64개의 순금 원반이 크기가 큰 것부터 아래에서 차곡차곡 쌓여있었 다고 함
• 어느 날 신이 승려들에게 다음과 같은 몇 가지 규칙을 준수하여 순 금 원반을 다른 다이아몬드 막대에 옮기라고 지시함. 이게 다 옮겨지 면 모든 생명체는 먼지처럼 사라지고 세상의 종말이 올 것이라고 말 함
• 순금 원반은 한번에 한 개 씩만 옮겨야 함
• 작은 원반이 큰 원반 밑에 들어갈 수 없음
• 원반이 2개일 때 22-1번, 3개일 때 23-1번, 이런 식으로 추정하면 원반이 64개인 경우는 264-1번 옮겨야 하고, 하나를 옮기는데 1초 걸린다고 했을 때 64개의 원반을 다 옮기는데 264-1초(약 5,845억년) 가 걸림
하노이 탑
7. 피보나치 수와 하노이 탑
int include<stdio.h>
void hanoi_tower(int n,char from,char tmp,char to) {
if(n==1)
printf(“원반 1을 %c에서 %c로 옮긴다.＼n”,from,to);
else {
hanoi_tower(n-1,from,to,tmp)
printf(“원반 %d을 %c에서 %c로 옮긴다.＼n”,n,from,to);
hanoi_tower(n-1,tmp,from,to) }
}
int main(void) {
int n;
printf(“구하려는 원반의 개수를 입력하세요.＼n”);
scanf(“%d”,&n);
printf(“원반이 %d개 있을 때 하노이 탑의 결과＼n＼n,n);
hanoi_tower(n,’A’,’B’,’C’);
}
