자연수 124는 얼마나 많은 약수를 갖고 있는지 생각하여

보시오.

 

   일반적으로 세는 방법에 있어서 (1)순서(order)를

고려하던지 또는 고려하지 않던지;(2)반복(repetition)을

허락하던지 또는 허락하지 않던지 등을 고려하여 여러

제한 조건하에서 선택이나 분포를 counting 하는 것을

학습한다. 

 두 가지 세기(Counting)의 방법

 

문제.  원형의 탁자에 5쌍의 부부가 앉으려고 한다. 이 때,남자와 여자는 교대로 앉아야 하고, 부부는 옆에 나란히 앉을 수 없다고 한다. 그러면 앉을 수 있는 방법 은 모두 몇 가지나 되는지 알아보시오.

     일상 생활 중에서 우리는 위의 문제와 같은 많은 상황을

만나게 되며, 우리는 이와 같은 문제를 해결하기 위하여 여러

방법의 세기(counting)를 잘 하여야 한다.

 

일반적으로 세는 방법에 있어서

(1) 순서(order)를 고려하던지 또는 고려하지 않던지;

(2) 반복(repetition)을 허락하던지 또는 허락하지 않던지

등을 고려하여 여러 조건 하에서 선택이나 분포를 counting

하는 것은 중요한 문제이며 , 지금부터 차례대로 알아보기로

합시다.

 

예제 1. 개인사물함에 두 자로 된 명찰을 붙여서 구분 하려고 한다. 한글 `가, 나, 다, ... , 파, 하 ` 의 14자 중에서 한 글자와 수자 `0, 1, 2, ... , 8, 9`의 열 개중 한 수자를 사용하려고 한다.   이 때  사물함을 구별할 수 있는 명찰을 몇 개 만들 수 있는지 알아보시오.

풀이. 사물함의 명찰의 모양은  

 한글 : 수자    (예를 들면,  가 3 )

  수자 : 한글   (예를 들면,   4 라 )

의 경우가 가능하므로,

 한글 : 수자 의 경우는 14 x 10 = 140 (가지)

수자 : 한글 의 경우는 10 x 14 = 140 (가지)

 따라서, 구별할 수 있는 사물함의 명찰의 개수는 모두

 140 + 140 = 280 (개)

이다.    ?

위 예제 1에서 알 수 있듯이, k 개의 가능성이 있는 일이

독립적으로 시행될 수 있고,  또 각각의 경우의 수가

m₁, m₂, ..., m_k 일 때,  가능한 전체의 경우의 수는 모두

이다.  이것을  합의 법칙 (the addition principle)이라고 한다.

각각의 경우의 수가  m₁, m₂, ..., m_i 인 연속된 일을 시행할 때,

가능한 전체의  경우의 수는 모두

이다. 이것을  곱의 법칙 (the multiplication principle)이라고

한다.

   이 두 가지 법칙은 모든 경우의 세기 문제에 있어서 가장 기본적인

법칙이다.

 

예제 2. 15명의 회원을 가진 어떤 모임이 있다. 이 때, 회장, 부회장, 총무, 감사를 각각 선출하려고 한다. 가능한 경우의 수는 모두 몇 가지인가 ?

풀이. 회장, 부회장, 총무, 감사를 연속하여 선출하여야 하므로, 곱의

법칙에 의하여

15 x 14 x 13 x 12 (가지)     ?

 

예제3. 빨간 주사위 R과 파란 주사위 B를 동시에 던질 때 나올 수 있는 눈의 경우의 수를 구하여 보시오. 또, 동일한 두 주사위를 던질 때 나올 수 있는 눈의 경우의 수도 구하여 보시오.

풀이.

(1)     빨간 주사위 R의 눈이 나올 수 있는 경우의 수는 6 가지

            파란 주사위 B의 눈이 나올 수 있는 경우의 수는 6 가지

따라서 곱의 법칙에 의하여 구하는 경우의 수는 모두

6 x 6 = 36 (가지)

이를 구체적으로 구하여 보면, 빨간 주사위 R과 파란 주사위 B의 나온 각각

눈을 r, b 라 하고 순서쌍 (r, b)로 표시하면

(1,1), (1,2), (1,3), (1,4), (1,5), (1,6)

(2,1), (2,2), (2,3), (2,4), (2,5), (2,6)

...

(6,1), (6,2), (6,3), (6,4), (6,5), (6,6)

(2) 동일한 두 주사위를 던지는 경우에 위의 경우에서의  (1,2)와 (2,1)은

구별할 수가 없고, 같은 모양으로 이해되므로 가능한 전체의 경우의 수는

모두  

  1 + 2 + 3 + 4 + 5 + 6 = 21 (가지)    ?

위 예제는 우리가 곧 학습할 중복순열과 중복조합의 전형적인 예로서,

경우 (1)은  중복순열

이고,  경우 (2)는 중복조합

이다.

 

문제 1.  세 자리의 양의 정수 중에서 7, 8, 9 를 자리수에 모두 갖고 있지  않은 정수는 몇 개인가 알아보시오.

순서가 있는 선택의 문제  (Ordered choices)

m 개의 대상으로부터 r 개를 선택할 경우에,

(1) 중복을 허락하는가?

(2) 순서를 고려하는가?

를 고려하여 경우의 수를 계산하여야 한다.

S가 공집합이 아닌 집합일 때, 중복을 허용하고 순서를 고려하여

r 개를 선택한 부분집합을  S의  r 표본(r-sample)이라 한다.

S의 원소의 개수를 n이라 하고, r표본의 개수를 구하여

봅시다.

   먼저 순서를 고려하므로  r개의 방을 먼저 순서대로 나열하고

□ □ □ … □

각 방에는 S의 원소 n 개 중에서 임의로 한 개를 선택할 수 있으므로

곱의 법칙에 의하여

n×n×…×n= n^r

이며,  이것을 중복순열이라고 부른다

  

정리1.  S의 원소의 개수를 n이라 하면,  r 표본의 개수는 n×n×…×n= nr     이다.

  

예제 1. 운동복에 0부터 9까지의 수자를 사용하여 두 자리 수자를 붙이려 한다. 그러면 중복순열의 수이므로, 102= 100 가지의 운동복 번호를 붙일 수 있다. 즉, 00 부터 99 까지 모두 100 가지이다.

 

문제 2. 26자의 영어 알파벳 중에서 5자 사용하여 임의로 낱말 모양을 만들려고 한다. 가능한 낱말은 모두 몇 가지 인가?

컴퓨터의 모든 코드는 모두  0과  1을 사용하여 표현된다.

이것을 binary code 라고 한다.  0,1 중 한 개로 이루어진 정보를 1 bit

라 하고 8 bit를 1byte라고 한다.  이때, 1byte code의 가능한 경우의

수를 살펴보면  중복순열의 원리의 의하여

2 x2 x···x 2 =2⁶ = 64 (가지)

가 가능하다. 

 개인용 PC는 정보처리 단위에 따라서 8 bit, 16 bit , 32 bit , 64 bit

등과 같이 한 번에 처리할 수 있는 정보양으로 PC를 구분하여 부르며,

요즘 Pentium Ⅱ processor를 갖춘 PC를  64 bit 운영체제인 PC라고

부른다.

 이 때, 4 byte (32bit) code의 경우의 수를 알아보면 중복순열의 수에

의한 경우의 수는 모두

이다.    이 숫자는 앞에서 학습한 Hanoi Tower 문제에서 나온 숫자에

버금가는 커다란 수이다.

 

문제 3. 2 byte 조합형 한글의 경우, 한글의 최소정보량은 2 byte이다.  이 때, 2 byte 조합형 한글code의 가능한 모든 경우의 수를 구하시오.

 

문제 4.  아이스크림의 향의 종류가 10가지 이고 , 아이스크림 컵에 두 주걱의 아이스크림을 담을 경우, 가능한 아이스크림 종류의 경우의 수를 모두 구하여라.  또 , 두 주걱의 아이스크림이 서로 다른 경우 가능한 아이스크림 종류의 경우의 수를 모두 구하여라.

 이제 반복이 허용되지 않고 선택의 수에 대하여 알아

보도록 합시다.

집합 S의 r-sample 중에서 원소가 모두 다른 것들을 우리는

r-순열 (r- permutation) 이라고 부른다. 또, S의 원소의

개수가 r 인 경우에 S의 r-순열은 단순히 순열 (permutation)

이라고 한다.

 

정리 2.  S의 원소의 개수가 n 일 때, r-순열의 수는                          이다.

증명. r-순열은 모두 다른 원소를 r 개 골라서 순서대로 나열하는 방법의

수이므로,  곱의 법칙을 사용하면

이다.       ?

 

기호의 약속 (1)  n  =  r  일 때  :      (2)  r   =  0 일 때  :    0-순열은 의미가 없다. 그러나 계산의 편의를 위하여   모든 n에 대하여 로 약속한다. 실제로   n !    은  Gamma 함수로 정의되는 수의 특수한 경우로 이해되는 수로서,   p > 0 인 임의의 실수 일 때  함수는 다음과 같이 정의된다 :   그러면  모든  p > 0 에 대하여 점화식 가 성립하고, 이 때 특별히 p가 자연수이면 가 된다.  ( 공학수학이나 해석학 책을 참조하시오.)

 

예제 4. 12명의 회원을 가진 모임에서 서로 다른 직함을 갖는 4 명을 선출하는 방법의 경우의 수는 ?

풀이.

  ?

   

예제 5. 알파벳 A, B, C, D 가 각각 쓰여진 네 장의 카드를 모두 사용하여 만들 수 있는 단어는 모두 몇 가지인가 알아보시오.

풀이.

   ?

 

 본 강의에서는, 일반적으로 세는 방법에 있어서 순서

(order)를 고려할 때,반복(repetition)을 허락하던지

또는 허락하지 않던지 등을 고려하여  counting 하는

방법을 학습하였다. 

 

 

영어 단어   MATHEMATICS 의 모든 철자를 사용하여

만들 수 있는 단어의 개수는 모두 몇 개인가 알아보시오.

 

 

일반적으로 세는 방법에 있어서 순서(order)를 고려하지

않을 때, 반복(repetition)을 허락하던지 또는 허락 하지

않던지 등을 고려하여 여러 조건 하에서 선택이나 분포를

counting하는 것을 학습한다. 

 

순서가 없는 선택의 문제 (Unordered choice)

   n 개의 원소를 갖는 집합 S로 부터 r 개의 서로 다른 원소를

순서를 고려하지 않고 선택한 집합을 S의 r-조합

(r-combination)이라고 하고,  r-조합의 수를

과 같이 표기한다.

 

정리 1.

증명.     r-순열의 개수는

이고  r 개를 나열하는 방법의 수는

이다.  따라서

  ?

  

예제 1. 12 명의 모임에서 4 명을 임의로 선출 하는 방법의 수는?

풀이.

 ?

  

예제 2. OCU의 교양과정에는 5 개의 과학 교과목과 4 개의 역사 교과목이 있다. 은지는 이번 학기에 2 개의 과학 교과목과 2 개의 역사 교과목을 선택하려고 한다. 이 때 은지가 선택할 수 있는 과목의 경우의 수는?

풀이.

 ?

  

예제 3. 7 개의 -(dash)와 5 개의 / (slash)를 한 줄에 나열하는 방법은 모두 몇 가지인가 알아보시오.

풀이. 우선 모두 12 개의 방이 나열되어 있다고 생각하고, 그 중 5 개를

순서에 관계없이 골라서 그 방에 / 를 넣는다고 생각하면 된다. 따라서

구하는 경우의 수는 모두  

이다.    ?

또 위의 문제의 풀이에서 7 개의 방을 골라서 - 를 넣어도 되므로

가 되며, 이 두 수는 같다.  즉,

일반적으로, 우리는 조합수에 관한  항등식

을 얻을 수 있다.

  

문제 1.  위의 조합수에 관한 항등식을 증명하여 보시오.

 

예제 4. 영어 단어 MISSISSIPI의 모든 영어 철자를 사용하여 만들 수 있는 새로운 단어의 개수를 구하여 보시오.

풀이.     영어 단어  MISSISSIPI는                    

M 이  1개

I 가  4개

S 가  4개

P 가  2개

이므로  모두 11자이다.

그러면, 11개의 방을 나열해 놓고, 먼저 S를 넣는 방법은

다음에 M을 넣는 방법은

S를 넣는 방법은

P를 넣는 방법은

이다.  따라서 구하는 방법의 수는  곱의 법칙에 의하여

  ?

이와 같은 중복되어 있는 것들에 관한 순열을 중복순열이라고 한다.

일반적으로 다음의 정리가 성립한다.

 

정리 2. 전체의 개수가 인  object를 한 줄에 나열하는 방법의 수는

증명. 위의 예제와 같은 방법으로 생각한다. 즉, n 개의 방이 있을 때, 먼저

n₁개를 고르는 방법은

또 ( n-n₁)개 가운데서  n₂개를 고르는 방법은

또, 이와 같은 방법으로 우리가 구하는 전체 경우의 수는

따라서,  구하는 전체의 가지 수는

이다.     ?

위의 정리 2 에서 가능한 경우의 수를

라 쓰며, 이를  다항계수(multinomial coeffcient) 라고 한다.

특히  k=2인 경우 다항계수는 앞에서 학습한 조합의 수

과 같다 . (왜냐하면, n = n₁ + n₂이므로)

 

원소의 개수가 n 인 집단으로부터 중복을 허용하여 r 개를 고르는

것을 r-선택 (r-selection)이라 하고, 이를 중복조합이라고 한다.

이 때, r 은  n 보다 커도 무방하다.  또,  r-선택 중에서 원소가 모두 다른 것을 우리는

r-조합이라고 부른다.

 

정리 3. 원소의 개수가 n 인 r-선택의 수(중복조합)는                  이다.

증명. 집합 S를    이라 두자.

각각의 r-선택을  r 개의  - 와 (n-1) 개의 / 로 이루어진 수열로 대응

할 수 있다.   예를 들면,   집합  S가   

  일 때,

 가  5-선택이라면  이것은 -/--//--/ 와 같다고 생각할 수 있다. 또,

s_2, s_2, s₃ 는  3-선택으로    이것은 /-/--// 와 같다고 생각한다.

따라서, 우리가 구하는 선택의 수는 정리 3 에 의하여

이다.   ?

 

예제 5. 알파벳 26자를 중복을 허락하여 3자를 골라서 나열하여 만들 수 있는 단어의 수는 몇 개인가?

풀이. 먼저 중복 조합의 수는

순서대로 나열하는 수는 중복순열이므로

?

    원순열과 기타 배열의 방법

모든 배열의 경우의 수는 모든 기본적인 수 법칙 , 즉 곱의

법칙과 합의 법칙에 의하여 구할 수 있다.

 

예제 1. 원판을 꼭 같은 넓이로 100 등분하여 수자 1부터 100까지 임의대로 쓰려고 한다. 이 때, 가능한 모든 경우의 수는?

풀이. 일렬로 나열하는 방법은 모두 100! 이다. 그런데 수자가 원형으로

나열되어 있으므로, 한 수자를 임의로 고정시키고 나머지는 일렬로 나열

한다고 생각하면 된다 . 따라서 구하는 경우의 수는 (100-1)!  이다.   ?

위의 예제와 같은 순열을  원순열(circular

arrangement)이라고 한다.

 

문제 1. 4 쌍의 부부가 원탁에 앉으려고 한다. 이 때, 남녀가 교대하여 앉는다면 가능한 모든 경우의 수는 얼마인가?

 

문제 2. 영어 단어 girl 에 사용된 한 철자라도 포함하는 4 자로 된 영어 단어의 수는 모두 몇 개인가?

어떤 성질을 갖는 object 의 counting은 전체의 경우에서

그 성질을 object의 수를 빼어서 계산할 수 있다. 이와 같은

방법을  여사건을 이용하여 counting 하는 방법 이라고 한다.

 

예제 2. 48 장의 트럼프 카드가 있다.  두 장의  카드를 나누어 줄 때, (1) 적어도 1 장이 ace 일 경우의 수는? (2) 두 장이 모두 ace일 경우의 수는? (3) 한 장 만이 ace일 경우의 수는?

풀이.   (1) 곱의 법칙에 의하여

4×3 가지

(2) 여사건을 이용하여 계산한다. 즉, 두 장이 모두 ace가 아닌 경우의

수는 모두 48 x 47 가지이므로, 구하는 경우의 수는

52×51 - 48×47 = 396

다른방법으로  ace×ace가 아닌 것 또는 ace가 아닌 것×ace 인

경우이므로

4 × 48 = 192 48 × 4 = 192

따라서 구하는 전체 경우의 수는 모두 396 가지

(3) (1)에 의하여

396 - 12 = 384 가지       ?

 

예제 3. 3 명의 남자와 6 명의 여자가 한 줄로 정렬한다. 이 때, 두 남자는 계속하여 줄서지 않는다고 한다. 정렬할 수 있는 가능한 경우의 수는?

풀이. 먼저 여자들이 정렬하는, 방법을 구하면

6!

이다. 이 때, 여자와 여자 사이의 빈 칸에 남자가 추가되는 것으로 이해하면,

모두 7 칸의 빈 칸 중에서 3 칸을 골라서 나열한 것이므로

따라서 구하는 경우의 수는

  ?

 

문제 3.   3 명의  남자와 6 명의 여자가 원형탁자에 앉으려고 한다.  이 때, 두 남자는 계속하여 나란히 앉지 않는다고 한다.  정렬할 수 있는 가능한 경우의 수는?

  

예제 4.  1부터 9 까지의 수자 중에서 연속한 두 수자를 뽑지 않고서 3 개의 수자를 선택하는 방법의 수는?

풀이.    선택한 수를 1, 선택안한 수를 0으로 표시한다면,  예를 들어

1001010000 은 숫자 1, 4, 6을 뽑은 것으로 생각 할 수 있다. 따라서, 6 개의

0 이 나열되어 있고 0 사이의 빈칸 7 개 중에서 3 개를 고르면 되므로 구하는

경우의 수는

이다.   ?

 

문제 4.   0부터 9 까지의 수자 중에서 연속한 세 수자를 뽑지 않고서  4 개의 수자를 선택하는 방법의 수는?

 

일반적으로 세는 방법에 있어서 순서(order)를 고려하지

않을 때,  반복 (repetition) 을 허락하던지 또는

허락하지 않던지등을 고려하여 여러 조건 하에서 선택이나

분포를 counting 하는 것을 학습하였다.