야곱베르누이 (Bernoulli, J., 1654~1705) 스위스의수학자 이글은 1713 년에출간된확률론에관한저서 추측술 에서, 어떤일이일어날가 능성을정확하게예측하기위해서는가능한경우의수를아는것이중요함을강조한 것이다. 260 Ⅵ. 경우의수
경우의수 합의법칙과곱의법칙을이해하고, 이를 이용하여경우의수를구할수있다. 합의법칙 어느식당에는후식으로 컵케이크 가지와아이스크림 가지 한개의주사위를던질때, 다음을구하시오. ⑴ 짝수의눈이나오는경우의수 ⑵ 의배수의눈이나오거나 의약수의눈이나오는경우의수 가준비되어있다. 컵케이크또는아이스크림중에서하나를택하는경우의수를구해보자. 위의생각열기에서컵케이크하나를택하는경우의수는 이고, 아이스크림하나를택하는경우의수는 이다. 이때컵케이크와아이스크림을동시에택할수는없으므로, 컵케이크 가지또는아이스크림 가지중에서하나를택하는경우의수는 이다. 년에우리나라의대표적인프로바둑기사가인공지능바둑프로그램과대국을펼쳤다. 바둑한판을둘때나올수있는경우의수는약 정도인데, 프로바둑기사는한수당보통 ~가지의수에서 ~ 가지의수로압축해가는과정을통해최적의수를찾아낸다고한다. 이처럼효율적인의사결정을하기위해서, 가능한경우의수를예상해보는과정이필요할때가있다. 이와같이동시에일어나지않는두사건에대하여다음과같은합의법칙이성립한다. 합의법칙두사건, 가동시에일어나지않을때, 사건 와사건 가일어나는경우의수가각각, 이면, 사건 또는사건 가일어나는경우의수는 이다. 합의법칙은어느두사건도동시에일어나지않는셋이상의사건에대 해서도성립한다. 문제 서로다른두개의주사위를동시에던질때, 나오는눈의수의합이 의배수인경우의수를구하시오. 1. 경우의수 261
예제 자연수, 에대하여 를만족시키는순서쌍 의개수를구하시 오., 가자연수이므로 인 의값은,, 이고, 각경우의순서쌍 는 (ⅰ) 인경우 (ⅱ) 인경우 (ⅲ) 인경우 의 개 (, 의 개,, 의 개 따라서구하는순서쌍 의개수는합의법칙에의하여 문제 음이아닌정수, 에대하여 을만족시키는순서쌍 의개수 를구하시오. 곱의법칙 어느식당에는후식으로컵케이크 가지와아이스크림 가지가준비되어있다. 컵케이크중에서하나와아이스크림중에서하나를동시에택하는경우의수를구해보자. 위의생각열기에서컵케이크를택하는경우의수는 이고, 그각각에대하여아이스크림을택하는경우의수는 이므로, 컵케이크 3가지중에서하나와아이스크림 가지중에서하나를동시에택하는경우의수는 이다. 사건이일어나는모든경우를나뭇가지모양의그림으로나타낸것을수형도 (tree graph) 라고한다. 이와같은사실은오른쪽그림과같이수형도를그려서확 인할수도있다. 262 Ⅵ. 경우의수
이와같이동시에일어나는두사건에대하여다음과같은곱의법칙이성립한다. 곱의법칙 곱의법칙은두사건이 잇달아일어나는경우에도 성립한다. 두사건, 에대하여사건 가일어나는경우의수가 이고그각각에대하여사건 가 일어나는경우의수가 일때, 두사건, 가동시에일어나는경우의수는 이다. 곱의법칙은동시에일어나는셋이상의사건에대해서도성립한다. 문제 서로다른꽃병 개와장미 송이가있다. 꽃 병에장미를꽂기위해서꽃병한개와장미한송이를 동시에택하는경우의수를구하시오. 문제 민서는서로다른종류의티셔츠, 바지, 점퍼를각각 개, 개, 개가지고있다. 민서가이중에서티셔츠, 바지, 점퍼를각각하나씩택하여입는경우의수를구하시오. 예제 의약수의개수를구하시오. 을소인수분해하면 의약수는,,, 의 개 의약수는,, 의 개이중에서각각하나씩택하여곱한수는모두 의약수가된다. 따라서구하는약수의개수는곱의법칙에의하여 문제 다음수의약수의개수를구하시오. ⑴ ⑵ 1. 경우의수 263
예제 어느휴양림에는오른쪽그림과같이야영장에서 대피소로가는길이 가지, 대피소에서정상으로가는길이 가지, 야영장에서정상으로바로가는길이 가지가있다. 세지점중에서같은지점을두번이상지나지않는다고할때, 다음을구하시오. ⑴ 야영장에서대피소를거쳐정상까지가는경우의수 ⑵ 야영장에서정상까지가는모든경우의수 ⑴ 야영장에서대피소로가는길은 가지, 대피소에서정상으로가는길은 가지이므로, 곱의법칙에의하여야영장에서대피소를거쳐정상까지가는경우의수는 ⑵ 야영장에서대피소를거쳐정상으로가는경우의수는, 아영장에서정상으로바로가는경우의수는 이다. 이때두사건은동시에일어날수없으므로, 합의법칙에의하여야영장에서정상까지가는모든경우의수는 ⑴ ⑵ 문제 오른쪽그림과같이네지점 A, B, C, D 를연결하는 도로망이있다. 주어진도로를이용하여 A 지점에서 D 지점까지 가는경우의수를구하시오. ( 단, 같은지점을두번이상지나지않는다.) 문제해결 추론 창의 융합 의사소통 정보처리 태도및실천 다음은서로다른두개의주사위를동시에던질때나오는눈의수의합이홀수인경우의수를 구하는방법에대하여민지와정우가나눈대화이다. 민지의방법으로경우의수를구해보자. 정우의방법으로경우의수를구하고, 민지의방법으로구한결과와비교해보자. 264 Ⅵ. 경우의수
순열 순열의뜻을이해하고, 순열의수를구할 수있다. 순열 영국에는일렬로배치된교회의종들을이용하여음악을연 주하는 전조명종술 이라는기술이전해지고있다. 다음그림은음색이서로 두자리자연수중에서십의자리숫자와 일의자리숫자가서로다른자연수의개 수를구하시오. 다른네개의종,,, 중에서종 를친것을나타낸다. 네개의종중에서서로다른두개를택하여순서대로치는경우의수를 구해보자. 위의생각열기에서첫번째종을택하는경우는,,, 의 가지이고그각각에대하여두번째종을택하는 경우는첫번째종을제외한 가지이므로, 네개의종중 바다를항해하는배는깃발을이용하여신호를보내기도한다. 이때서로다른깃발을나열하는순서에따라여러가지신호를만들어항해에필요한정보를전달할수있다. 이처럼서로다른것중에서일부를택하여나열할때, 순서를고려해야하는경우가있다. 에서서로다른두개를택하여순서대로치는경우의수는곱의법칙에의하여 이다. 오른쪽수형도에서와같이서로다른두개의종을순서대로치는경우를모두나열하면 가지가있음을알수있다. 일반적으로서로다른 개에서 개를택하 여일렬로나열하는것을 개에서 개를택하는순열이 라하며, 이순열의수를기호로 P 와같이나타낸다. P 의 P 는순열을뜻 하는 permutation 의첫글 자이다. 266 Ⅵ. 경우의수
순열의수 P 를구하는방법을알아보자. 서로다른 개에서 개를택하여나열할때, 첫번째자리에올수있는것은 가지이고그각각에대하여두번째자리에올수있는것은첫번째자리에놓인것을제외한 가지이다. 이와같이차례대로생각하면 번째자리에올수있는것은, 즉 가지이다. 따라서곱의법칙에의하여다음이성립한다. P 개 이상을정리하면다음과같다. 순열의수 ⑴ 서로다른 개에서 개를택하는순열의수는 P P 문제 다음값을구하시오. ⑴ P ⑵ P ⑶ P 서로다른 개에서 개를모두택하는순열의수는 P 이다. 여기서 부터 까지의자연수를차례대로곱한것을 의계승이라하며, 이것을기호로 은 의계승 ( 階乘 ) 또 는 factorial 이라고읽는 다. 과같이나타낸다. 즉, 이다. 따라서 P 이다. 1. 경우의수 267
한편, 일때순열의수 P 를계승을이용하여다음과같이나타낼수있다. P 이면 P P 이면 P 여기서, P 로정의하면, 위의등식은 과 일때도성립한다. 이상을정리하면다음과같다. 순열의수 ⑵ ➊ P,, ➋ P P ( 단, ) P 문제 다음값을구하시오. ⑴ P ⑵ ⑶ P ⑷ P 예제 일때, 등식 P P 이성립함을증명하시오. P 따라서 P P 이성립한다. P P 는서로다른 개에서 개를택하여일렬로나열하는경우의수이다. 개에서한개를택하는경우는 가지이고, 그각각에대하여하나를택하고남은 개에서 개를택하여일렬로나열하는경우의수는 P 이다. 따라서곱의법칙에의하여 P P 이성립한다. 문제 일때, 등식 P P P 이성립함을증명하시오. 268 Ⅵ. 경우의수
예제 네명의선수 A, B, C, D 가한팀을이루 어 인조정경기에출전했다. 다음을구하시오. ⑴ A 와 C 가서로이웃하게배에앉는경우의수 ⑵ B 와 D 가배의양끝에앉는경우의수 ⑴ A 와 C 를한사람으로생각하면모두 명이고, 명이한줄로앉는경우의수는 이다. 이때각경우에대하여 A 와 C 의자리를바꾸는경우의수는 이다. 따라서구하는경우의수는곱의법칙에의하여 ⑵ B 와 D 가배의양끝에앉는경우의수는 이고각경우에대하여나머지 명이 한줄로앉는경우의수는 이다. 따라서구하는경우의수는곱의법칙에의하여 ⑴ ⑵ 문제 세개의문자,, 와두개의숫자, 를일렬로나열할때, 다음을구하시오. ⑴ 두개의숫자를서로이웃하게나열하는경우의수 ⑵ 문자와숫자를교대로나열하는경우의수 문제 다섯개의숫자,,,, 를모두사용하여만들수있는다섯자리자연수 중에서짝수의개수를구하시오. 퍼즐속의경우의수 미국의수학자로이드 (Loyd, S., 1841~1911) 는 개의칸에아무렇게나나열 된 부터 까지의숫자를빈칸을이용해서옮기는과정을반복하여오른쪽그 림과같이작은수부터차례대로나열하는숫자퍼즐을만들었다. 이퍼즐은주어진숫자의배열에따라풀리지않는경우도있는데, 그림과같이 풀리는경우의수는 임이알려져있다. ( 출처 : Culberson, J. C. 외, Efficiently searching the -puzzle ) 1. 경우의수 269
조합 조합의뜻을이해하고, 조합의수를구할 수있다. 조합 교내합창경연대회에참가 한지연, 수빈, 영은, 민지네명의학생은 다음값을구하시오. ⑴ P ⑵ 소프라노파트에지원했다. 위의네명중소프라노파트를맡을세 명을선발하는경우의수를구해보자. 순열에서서로다른것을순서를생각하여택하는경우의수를배웠다. 이제서로다른것을순서를생각하지않고택하는경우의수를알아보자. 네개의문자,,, 중에서순서를생각하지않고세개를택하는경우는,,, 의 가지이다. 일반적으로서로다른 개에서순서를생각하지않고 개를택하는것을 개에서 개를택하는조합이라하며, 다섯명의회원중에서회장과부회장을선출하는경우의수를구할때는순서를고려해야하지만, 두명의임원을선출하는경우에는순서를고려하지않아도된다. 이처럼서로다른것중에서순서에관계없이몇개를택하는경우의수를구해야할때가있다. 이조합의수를기호로 C 와같이나타낸다. C 의 C는조합을뜻하는 combination 의첫글자이다. 순열과조합의관계를이용하여조합의수 C 를구하는방법을알아보자. 네개의문자,,, 중에서세개를택하는조합의수는 C 이고 그각각에대하여다음과같이 가지의순열을만들수있다. 270 Ⅵ. 경우의수
그런데서로다른 개에서 개를택하는순열의수는 P 이므로곱의법칙에의하 여 C P 이성립함을알수있다. 일반적으로서로다른 개에서 개를택하는조합의수는 C 이고, 그 각각에대하여 개를일렬로나열하는경우의수는 이다. 그런데서로다른 개에서 개를택하는순열의수는 P 이므로곱의법칙에의하여 C P 이다. 즉, 다음이성립한다. C P 또,, P 이므로 C 로정의하면, 위의등식은 일때도성립한다. 이상을정리하면다음과같다. 조합의수 서로다른 개에서 개를택하는조합의수는 C P P C 문제 다음값을구하시오. ⑴ C ⑵ C ⑶ C 문제 다음을구하시오. ⑴ 어느세점도일직선위에있지않은 개의점중에서택한 개의점을꼭짓점으로하는삼각형의개수 ⑵ 명의학생중에서 명의학생회임원을선출하는경우의수 1. 경우의수 271
예제 일때, 등식 C C 가성립함을증명하시오. C 따라서 C C 가성립한다. C 서로다른 개에서 개를택하는조합의수는 개의원소중에서 개를택할경우남 아있을 개를택하는조합의수와같으므로 C C 가성립한다. 문제 일때, 등식 C C C 이성립함을증명하시오. 예제 청소년문화재지킴이 모집에남학생 명, 여 학생 명이지원했다. 이중에서남학생 명, 여학생 명 을선발하는경우의수를구하시오. 남학생 명중에서 명을선발하는경우의수는 C 이고, 여학생 명중에서 명을 선발하는경우의수는 C 이다. 따라서구하는경우의수는곱의법칙에의하여 C C 문제 부터 까지의숫자가각각하나씩적힌 개의공이들어있는주머니에서 개 의공을동시에꺼낼때, 다음을구하시오. ⑴ 이적힌공을포함하는경우의수 ⑵ 짝수가적힌공 개와홀수가적힌공 개를꺼내는경우의수 문제 오른쪽그림과같이직사각형의가로와세로에평행 한선분을각각 개, 개그었을때, 그림에서찾을수있는 크고작은직사각형의개수를구하시오. 272 Ⅵ. 경우의수
Ⅵ 1. 경우의수 경우의수 ⑴ 합의법칙두사건, 가동시에일어나지않을때, 사건 와사건 가일어나는경우의수가각각, 이면, 사건 또는사건 가일어나는경우의수는 이다. ⑵ 곱의법칙두사건, 에대하여사건 가일어나는경우의수가 이고그각각에대하여사건 가일어나는경우의수가 일때, 두사건, 가동시에일어나는경우의수는 이다. 순열 ⑴ 서로다른 개에서 개를택하여일렬로나열하는것을 개에서 개를택하는순열이라하며, 이순열의수를기호로 P 와같이나타낸다. 01 02 부터 까지의숫자가각각하나씩적힌 개의공이들어있는상자에서한개의공을꺼낼때, 의배수또는 의배수가적힌공이나오는경우의수를구하시오. 한개의주사위를두번던질때, 첫번째에는 의약수의눈이나오고, 두번째에는 의배수의눈이나오는경우의수를구하시오. ⑵ 부터 까지의자연수를차례대로곱한것을 의계승 이라하며, 이것을기호로 과같이나타낸다. 즉, 이다. ⑶ 순열의수 ➊ P 03 다음값을구하시오. ⑴ P ⑵ ( 단, ) ⑶ C ⑷ C ➋ P,, P 조합 ⑴ 서로다른 개에서순서를생각하지않고 개를택하는것을 개에서 개를택하는 조합이라하며, 이조합의수를기호로 C 와같이나 타낸다. ⑵ 조합의수 C P ( 단, ) 04 다음을구하시오. ⑴ 개의문자,,,, 중에서 개를택하여일렬로나열하는경우의수 ⑵ 명의학생을일렬로세우는경우의수 ⑶ 색이서로다른 장의색종이중에서 장을뽑는경우의수 1. 경우의수 273
05 서로다른두개의주사위를동시에던질때, 나오는눈의수의합이 이상인경우의 수를구하시오. 06 어느샌드위치가게에는샌드위치를주문할때, 추가 로택할수있는 가지의야채, 가지의치즈, 가지 의소스가준비되어있다. 이가게에서야채, 치즈, 소 스를각각하나씩추가로택하여샌드위치를주문하 는경우의수를구하시오. 07 다음을구하시오. ⑴ 양의정수, 에대하여 를만족시키는순서쌍 의개수 ⑵ 다항식 를전개할때, 생기는항의개수 08 영어단어 smile 을이루는 개의알파벳을모두사용하여일렬로나열할때, 다음을 구하시오. ⑴ 일렬로나열하는경우의수 ⑵ 모음이양끝에오도록나열하는경우의수 09 이어달리기에참가한남학생 명과여학생 명을일렬로세울때, 다음을구하시오. ⑴ 남학생 명을서로이웃하게세우는경우의수 ⑵ 여학생을양끝에세우는경우의수 274 Ⅵ. 경우의수
10 오른쪽그림과같은정팔각형에대하여다음을구하시오. ⑴ 두꼭짓점을이어서만들수있는직선의개수 ⑵ 세꼭짓점을이어서만들수있는삼각형의개수 11 명의배구선수중에서경기에출전할 명의선수를뽑으려고할때, 다음을구하시오. ⑴ 두선수 A, B 를포함하여뽑는경우의수 ⑵ 두선수 A, B 를포함하지않고뽑는경우의수 12 오른쪽그림과같이구분된 개의영역을서로다른 가지색중 전부또는일부를사용하여칠하려고한다. 한가지색을여러번 사용해도좋으나이웃한영역은서로다른색으로칠하여구분할 때, 칠하는경우의수를구하시오. 13 서로다른 개의주사위를던져서나오는눈의수를각각,, 라할때, 의값이홀수가되는경우의수를구하는풀이과정과답을쓰시오 14 개의의자가일렬로놓여있다. 두명의학생이서로다른의자에앉을때, 두명사 이에적어도하나의빈의자가있도록앉는경우의수를구하는풀이과정과답을쓰 시오. 1. 경우의수 275
ⅥⅠ 01 서로다른두개의주사위를동시에던져서나오는눈의수를각각, 라할때, 이차방정식 이실근을갖는경우의수를구하시오. 05 인천국제공항과목포사이를운행하는고속철도에는 개의정차역이있다. 고속철도의출발역과도착역이표기된열차표를발행하는경우의수를구하시오. ( 단, 출발역과도착역은서로다르다.) 02 오른쪽그림과같은정육면체에서모서리를따라꼭짓점 A 를출발하여꼭짓점 G 까지최단거리로가는경우의 수를구하시오. 06 개의알파벳 N, I, C, E, D, A, Y 를자음과모음이 교대로나오도록나열하는경우의수를구하시오. 03 한개의동전과서로다른두개의주사위를동시에던질 때, 나오는모든경우의수를구하시오. 07 등식 P P 을만족시키는자연수 의 04 오른쪽그림과같이입구로들어 값을구하시오. 가서세개의벽 A, B, C 를통과 하여출구로나가게되어있는건물이있다. 세개의벽 A, B, C 를통과할수있는문이각각 개, 개, 개있을때, 입구로들어가서출구로나가는경우의수를구하시오. ( 단, 같은벽을두번이상통과하지않는다.) 08 크기가서로다른빨간구슬 개와파란구슬 개가들어있는주머니에서빨간구슬 개와파란구슬 개를꺼내는경우의수를구하시오. 276 Ⅵ. 경우의수
09 오른쪽그림과같이 개의평행선과 개의평행선이서로만나고있다. 이들평행선을이용하여만들수있는크고작은평행사변형의개수를구하시오. 11 개의숫자,,,, 중에서서로다른 개의숫자를택하여세자리자연수를만들려고한다. 다음에답하시오. ⑴ 백의자리숫자가 또는 인경우의수를구하시오. ⑵ 큰수부터차례대로나열했을때, 번째에오는수 를구하시오. 10 에대한이차방정식 P C 의두근이, 일때, 의값을구하시오. ( 단,, 는자연수이다.) 12 어느은행의본점이있는도시에 개의지점이있는데, 본 점에서각지점까지의거리는모두다르다. 본점에소속된 명의직원 A, B, C, D, E 를각지점에출장보내려고 할때, A 를 B 보다가까운지점으로보내는경우의수를 구하시오. 대단원평가하기 277