경우의수순열조합
01. 순열 1. 경우의수 (1) 합의법칙두사건 와 가동시에일어나지않을때, 사건 가일어나는경우의수가, 사건 가일어나는경우의수가 이라하면사건 또는 가일어나는경우의수는 이다. 집합의개념을이용하여합의법칙을생각해보자. 두사건 가일어나는경우의집합을각각 라하면두사건 가일어나는경우의수는각각 와같다. 또사건 또는사건 가일어나는경우는집합 로나타낼수있고, 두사건 가동시에일어나는경우는집합 로나타낼수있다. 이때 가성립하며두사건 가동시에일어나지않을때는 이므로 이다. 따라서두사건 가동시에일어나지않을때는 이다. 이것이두사건 에대한합의법칙을나타낸다. (2) 곱의법칙 사건 가일어나는경우의수가 이고, 그각각의경우에대하여사건 가일어나는 경우의수가 이라할때, 사건 와사건 가잇달아일어나는경우의수는 이다. 예를들어주머니 에 이하나씩적혀있는 개의공이들어있고, 주머니 에 이하나씩적혀있는 개의공이들어있다고하자. 두주머니 에서하나씩공을선택했을때, 나올수있는경우를순서쌍으로나타내면다음과같다. 가지 가지 따라서두주머니 에서하나씩공을선택했을때, 나올수있는경우의수는 이다.
01. 순열 2. 순열 (1) 순열서로다른 개에서 개를택하여일렬로나열하는것을 개에서 개를택하는순열이라하고, 이순열의수를기호 로나타낸다. 순열의수 (1) 서로다른 개에서 개를택하여일렬로나열하는순열의수 ( 단, ) 특히서로다른 개에서 개를택하여나열하는순열의수는 이고, 이와같이 부터 까지의자연수를차례로곱한것을 의계승이라고하며이것을기호로 과같이나타낸다. 이때 은 팩토리얼 (factorial) 이라고읽는다. 한편 일때, 순열의수 을계승을이용하여나타내면 이때위의등식이 과 일때도성립하도록 로정의한다. 이상을정리하면다음과같다. 순열의수 (2) (1) ( 단, ) (2)
01. 순열 (2) 중복순열 서로다른 개의원소에서중복을허용하여 개를택하여일렬로배열하는순열을중복순열이라고하고, 그중복순열의수를기호로 과같이나타낸다. 중복순열의수 서로다른 개의원소에서중복을허락하여 개를선택하여일렬로배열하는중복순열의수는 (3) 원순열 서로다른원소를원형으로배열하는순열을원순열이라고한다. 원순열의수 서로다른 개의원소를원형으로배열하는원순열의수는 (4) 같은것이있는순열 같은것이있는순열의수 개중에서서로같은것이각각 개, 개,, 개씩있을때, 개를모두일렬로 배열하는순열의수는 ( 단, )
02. 조합 1. 조합 서로다른 개에서순서를생각하지않고 개를택하는것을조합이라하고, 이조합의수를기호로 로나타낸다. 이때서로다른 개에서순서를생각하지않고 개를택하고, 선택된 개를일렬로나열하는방법의수 은서로다른 개에서 개를선택하여일렬로나열하는순열의수 과같으므로 이성립한다. 또한 이므로 로정의하면 일때도성립한다. 이상을정리하면다음과같다. 조합의수 서로다른 개에서 개를택하는조합의수 ( 단, ) 2. 중복조합 서로다른 개에서중복을허용하여 개를선택하는것을중복조합이라하고, 그수를기호 로나타낸다. 예를들어서로다른세문자 중에서중복을허락하여 개를택하는방법을생각해보자. 선택된문자 개를 순서로놓은후서로다른문자사이에 를써놓고, 모든문자를 라하자. 이와같이 개의문자 중에서중복을허락하여 개를택하는조합의수는 모양 개와 모양 개를일렬로나열한순열의수와같고, 일반적으로서로다른 개에서 개를택하는중복조합의수는 개 의 모양과 개의 모양을일렬로나열하는순열의수와같으므로 이성립한다. 이상을정리하면다음과같다. 중복조합의수 서로다른 개에서중복을허락하여 개를선택하는중복조합의수는
1. 같은종류의축구공 개와같은종류의농구공 개를 세상자에남김없이나누어넣을때, 축구공 이들어있지않은상자가하나만생기도록공을상자에넣는경우의수를구하시오. ( 단, 같은종류의공은서로 구별하지않고, 공이없는상자도있을수있다.) [4 점 ] 2. 같은종류의아이스크림 개를 명의어린이에게남김없이나누어줄때, 다음조건을만족시키도록나누어주는경우의수를구하시오. [4점] ( 가 ) 한개만받는어린이는 명이다. ( 나 ) 한개도받지못하는어린이는없다.
3. 1 층에서 명이엘리베이터를타고출발하였다. 이들은 층부터 층까지어느한층에서내리며 층에서는 엘리베이터에남은사람들이모두내린다. 이때, 내리는모든방법의수는? ( 단, 층은멈추지않으며어느 한층에서모두내릴수도있다.) [4 점 ] 1 2 3 4 5 4. 서로다른종류의연필 자루를 명의학생 A B C D에게남김없이나누어주는경우의수는? ( 단, 연필 을받지못하는학생이있을수있다.) [3점] 1 2 3 4 5
5. 흰색탁구공 개와주황색탁구공 개를 명의학생에게남김없이나누어주려고한다. 각학생이흰색 탁구공과주황색탁구공을각각한개이상갖도록나누어주는경우의수는? [4 점 ] 1 2 3 4 5
6. 다음그림과같이크기가같은정육면체모양의투명한유리상자 개로직육면체를만들었다. 이중에서 개의유리상자를같은크기의검은색유리상자로바꾸어넣은직육면체를위에서내려다본모 양이 ( 가 ), 옆에서본모양이 ( 나 ) 와같이되도록만들수있는방법의수는? [4 점 ] ( 나 ) ( 가 ) 1 2 3 4 5
7. 그림과같이이웃한두교차로사이의거리가모두 인바둑판모양의도로망이있다. 로봇이한번움직일때마다길을따라거리 만큼씩이동한다. 로봇은길을따라어느방향으로도움직일수있지만, 한번통과한지점을다시지나지는않는다. 이로봇이지점 O에서출발하여 번움직일때, 가능한모든경로의수는? ( 단, 출발점과도착점은일치하지않는다.) [4점] 1 2 3 4 5
8. 의숫자가하나씩적힌 개의공을 개의상자 A B C 에넣으려고한다. 어느상자에도넣어 진공에적힌수의합이 이상이되는경우가없도록공을상자에넣는방법의수는? ( 단, 빈상자의경우에는 넣어진공에적힌수의합을 으로한다.) [4 점 ] 1 2 3 4 5
9. 다음그림과같이 개의섬이있다. 개의다리를건설하여 개의섬모두를연결하는방법의수를구하시오. [3 점 ] 10. 색깔이서로다른 개의열쇠가하나씩포장되어있다. 이중 개는자물쇠 A만을 개는자물쇠 B만을, 개는자물쇠 C 만을열수있다. 개의열쇠중에서 개를임의로선택할때, 자물쇠 A와 B는모두열리고 자물쇠 C 는열리지않도록선택하는경우의수는? [4점] 1 2 3 4 5
11. 여섯개의문자 A, B, C, D, E, F 를모두사용하여만든 자리문자열중에서다음조건을모두만족시 키는문자열의개수는? ( 가 ) A의바로다음자리에 B가올수없다. ( 나 ) B의바로다음자리에 C 가올수없다. ( 다 ) C 의바로다음자리에 A가올수없다. ( 예를들어 CDFBAE는조건을만족시키지만 CDFABE는조건을만족시키지않는다.) [4점] 1 2 3 4 5
12. 다음조건을만족시키는음이아닌정수 의모든순서쌍 의개수는? [4 점 ] ( 가 ) ( 나 ) 좌표평면에서세점 가한직선위에있지않다. 1 2 3 4 5
13. 다음조건을만족시키는음이아닌정수 의모든순서쌍 ( ) 의개수를구하시오. [4 점 ] ( 가 ) ( 나 ) 은 의배수이다.
14. 다음조건을만족시키는자연수,, 의모든순서쌍 의개수를구하시오. [4점] ( 가 ) 는홀수이다. ( 나 ) 15. 다음조건을만족시키는음이아닌정수,,,, 의모든순서쌍 의개수는? [4 점 ] ( 가 ),,,, 중에서 의개수는 이다. ( 나 ) 1 2 3 4 5
16. 세정수,, 에대하여 를만족시키는모든순서쌍 의개수는?[4점] 1 2 3 4 5
17. 어떤사회봉사센터에서는다음과같은 가지봉사활동프로그램을매일운영하고있다. 프로그램 A B C D 봉사활동시간 시간 시간 시간 시간 철수는이사회봉사센터에서 일간매일하나씩의프로그램에참여하여다섯번의봉사활동시간합계가 시간 이되도록아래와같은봉사활동계획서를작성하려고한다. 작성할수있는봉사활동계획서의가짓수는? [4점] 참여일참여프로그램봉사활동시간 봉사활동시간합계 시간 1 2 3 4 5
18. 어느회사원이처리해야할업무는 A B를포함하여모두 가지이다. 이중에서 A B를포함한 가지업무 를오늘처리하려고하는데, A를 B보다먼저처리해야한다. 오늘처리할업무를택하고, 택한업무의처리순서 를정하는경우의수는? [3점] 1 2 3 4 5 19. 다음표와같이 개과목에각각 개의수준으로구성된 개의과제가있다. 각과목의과제는수준 Ⅰ 의 과제를제출한후에만수준 Ⅱ 의과제를제출할수있다. 예를들어 국어 수학 국어 영어 영어 수학 순서로과제를제출할수있다. 수준 과목 국어수학영어 Ⅰ 국어 수학 영어 Ⅱ 국어 수학 영어 개의과제를모두제출할때, 제출순서를정하는경우의수를구하시오. [4 점 ]
20. 개의본사와 개의지사로이루어진어느회사의본사로부터각지사까지의거리가표와같다. 지사가나다라마 거리 (km) 본사에서각지사에 A B C D E를지사장으로각각발령할때, A보다 B 가본사로부터거리가먼지사의지 사장이되도록 명을발령하는경우의수는? [4점] 1 2 3 4 5
21. 그림과같이크기가서로다른 개의펭귄인형과 개의곰인형이두상자 A, B 에왼쪽부터크기가작 은것에서큰것순으로담겨져있다. 다음조건을만족시키도록상자 A, B의모든인형을일렬로진열하는경우의수를구하시오. ( 가 ) 같은상자에담겨있는인형은왼쪽부터크기가작은것에서큰것순으로진열한다. ( 나 ) 상자 A 의왼쪽에서두번째펭귄인형은상자 B 의왼쪽에서두번째곰인형보다왼쪽에진열한다.
[ 정답및해설 ]
1. (ⅰ) 같은종류의축구공 개를축구공이들어있지않은상자가하나만생기도록넣는경우의수를구하자. 축구공을넣지않는상자를결 정하는경우의수가 이고나머지두상자에 개의축구공이적어도 한개이상들어가도록공을나누어넣는경우의수가 이므로 (ⅱ) 같은종류의농구공 개를 세상자에남김없이나누어넣는경우의수는 (ⅰ), (ⅱ) 에의해구하는경우의수는 정답및해설 행을택하는방법의수는 가지이고, 이행의 개의유리상자중에서검은색유리상자로바뀔 개의상자를택하는경우는수는 ( 가지 ) 이다. 이제위의 가지경우의수중의하나가아래의그림과같다 고하자. a c b d 이제 중에서한행을택하고 중에서나머지한행을택하는방법의수는 ( 가지 ) 이다. 따라서구하는방법의수는 7. 3 2. 명중아이스크림을한개만받는어린이 명을택하여아이스크림을 한개씩나누어주는경우의수는 남은 개의아이스크림을나머지 명에게두개이상씩나누어주는 경우의수는서로다른 개에서중복을허락하여 ( 개 ) 를택하는중복조합의수와같으므로 따라서, 구하는경우의수는 이다. 왔던길로되돌아가지않고로봇이움직일수있는전체경우의수에서출발점과도착점이같은경우의수를빼면 8. 2 개의공을상자 A, B, C 에넣는전체방법의수는 합이 이상이되는경우는, 3. 3 명이각층마다내리는경우의수는 가지이므로 9. 4. 1 연필 자루를 명에게나누어주는경우의수는 5. 5 위그림과같이 개의섬을각각 A B C D 라하자. (ⅰ) 한개의섬에다리가 개, 나머지섬에다리가 개씩연결되는경 우 명의학생이흰색탁구공을각각,, 개씩받는다면 인자연수 ) H C ᄀ 주황색탁구공을각각,, 개씩받는다면 인자연수 ) H C ᄀ, ᄂ에서 6. 4 ᄂ 주어진조건을만족하려면 개의가로행에는각각적어도하나의검은색유리상자가들어가야하고, 개의세로열에도각각적어도하나의검은상자가들어가야한다. 따라서 개의가로행중에서 개의검은색유리상자가포함될 개의 개의다리가모두연결될섬을정해주는방법은 가지이다. (ⅱ) 두개의섬에다리가 개, 나머지섬에다리가 개씩연결되는경 우 오른쪽그림 (A C B D) 과같이 개의섬을일렬로나열하는경우의수와같고, 이때반대순서로나열하는 경우 (B D C A) 와다리를연결하 는방법이같으므로 (ⅰ), (ⅱ) 에서구하는방법의수는 가지
10. 4 (ⅰ) 자물쇠 A 의열쇠를 2 개, 자물쇠 B 의열쇠를 1 개선택하는경우 C C (ⅱ) 자물쇠 A 의열쇠를 1 개, 자물쇠 B 의열쇠를 2 개선택하는경우 C C (ⅰ), (ⅱ) 에서구하는경우의수는 11. 2 A, B, C, D, E, F 를모두사용하여만든 자리의문자열의집합을 라하면 이다. 한편, 의원소중에서 A 의바로다음자리에 B 가오는문자열의집합을, B 바로다음자리에 C 가오는문자열의집합을, C 바로다음자리에 A 가오는문자열의집합을 라하면주어진조건을모두만족시키는문자열의집합은 이다. 따라서포함배제의원리에의해 12. 5 조건 ( 가 ) 를만족시키는음이아닌정수 의순서쌍의개수는 H C 이중조건 ( 나 ) 를만족시키지않는경우 는두점 를지나는직선의기울기와두점 를지나는직선의기울기가같은경우이므로 정리하면 이고조건 ( 가 ) 에서 이므로, 따라서세점이한직선위에있는경우의수는 H C 이므로 구하는순서쌍의개수는 13. 방정식 을만족시키는모든순서쌍 ( ) 의개수는 H C C 이때, 조건 ( 나 ) 를만족시키지않는순서쌍 는 뿐이다. 따라서구하는순서쌍의개수는 14. 가홀수이므로, 는모두홀수이다 정답및해설 이때, 을만족시키는순서쌍 는 에서중복을허용하여 3 개를택하는경우의수와같 으므로 15. 4 인것 개를정하는경우의수는 C ᄀ 일때 을만족시키는자연수 의순서 쌍 의개수는,, ( 단, 는음이아닌정수 ) 라하면 을만족시키는순서쌍 의개수와같으므로 H C C ᄂ ᄀ, ᄂ에서구하고자하는순서쌍의개수는 16. 3 주어진조건을만족시키는세자연수 의순서쌍 의개수는 이하의자연수중에서중복을허락하여 개를택하는중복조합의수와같다. 이때 는각각음의정수와양의정수의값을가질수있으므로 순서쌍 의개수는 의개수의 배와같다. 따라서구하는순서쌍의개수는 H C C 17. 5 다섯번의프로그램에참여하여시간합계가 시간이되도록하는방법 은다음과같다. (1) 의경우 작성할수있는봉사활동계획서의가짓수는 A A A A D 를나열하는방법의수와같으므로 ( 가지 ) (2) 의경우 작성할수있는봉사활동계획서의가짓수는 A A A B C 를나열하는방법의수와같으므로 ( 가지 )
(3) 의경우 (ⅰ) 이 보다왼쪽에있는경우의수는 정답및해설 작성할수있는봉사활동계획서의가짓수는 A A B B B 를나열하는방법의수와같으므로 ( 가지 ) 따라서구하는가짓수는 ( 가지 ) (ⅱ) 이 보다오른쪽에있는경우의수는 (ⅰ), (ⅱ) 에의하여구하는경우의수는 18. 3 오늘처리할업무를택하는방법은 A B 를제외한 가지업무중 가 지를택하는조합이므로 ( 가지 ) 택한 가지업무중 A B 는순서가정해져있으므로이를같은업무 로생각하면이 가지업무의처리순서를정하는경우의수는 ( 가지 ) 따라서, 구하는경우의수는 ( 가지 ) 19. 각과목의수준 Ⅰ 의과제와수준 Ⅱ 의과제사이에는순서가이미정 해져있으므로 를모두나열하는경우의수와같다. [ 다른풀이 ] 개의순서중국어과목의과제를제출할순서를정하는경우의수는 C 나머지 개의순서중수학과목의과제를제출할순서를정하는경우 의수는 C 나머지 개의순서중영어과목의과제를제출할순서를정하는경우 의수는 C 이때국어 와국어 를나열하는경우의수는, 수학 와수학 를나열하는경우의수는 1, 영어 와영어 를나열하는경우의수 는 20. 3 개의지사에서 개를선택하여가까운지사에 를, 먼지사에 를발령하는경우의수는 C 이때 가 지사와 나 지사를선택하는경우는본사로부터의거리차이가없으므로제외하면 가지 한편나머지 명을발령하는경우의수는 따라서구하는경우의수는 21. 펭귄인형을크기가작은것부터,, 이라하고곰인형을크기 가작은것부터,,, 라하자.