제 1 장 순열과조합
01 경우의수
1. 경우의수 01 순열과조합 빠짐없이, 중복되지않게 사전식배열, 수형도 복잡한경우의수를셀때는점화식을이용하는경우도있다. (1) 합의법칙한사건 가 가지의방법으로일어나고, 다른사건 가 가지의방법으로일어난다고할때 또는 가일어나는경우의수는, 가동시에일어나지않을때 m+n 가지, 가동시에일어나는경우가 가지있을때 m+n-l 가지 (2) 곱의법칙한사건 가 가지의방법으로일어나고, 그각각에대하여다른사건 가 가지의방법으로일어난다고할때 와 가동시에일어나는경우의수 m n 가지 화폐의지불방법과지불금액 원짜리동전 개, 원짜리동전 개, 원짜리동전 개를사용하여거스름돈없이지불할때, 지불방법과지불금액의수를구하시오. 1 지불방법곱의법칙에따라 100원 개, 50원 개, 10원 개라할때 (,, ) 의개수를구한다. 3 4 5-1 가지 2 지불금액 50 원두개로 100 원을지불할수있을때는 100 원짜리를 50 원짜리로바꾸어 50 원 7 개, 10 원 4 개로지불하는방법과같다. 8 5-1 가지 노박사수학 / 3
점화식을이용한풀이 01 순열과조합 경우의수를구하는데 점화식을이용하면편리한경우가있다. 예제, 기호다섯개를같은기호는연속하여세번이상 이어지지않게나열하는경우의수, 기호네개를나열하고맨앞은다른기호한개, 기호세개를나열하고맨앞은다른기호두개 를추가하면, 다섯개의기호가연속하여세번이상이어지지않게나열되는것을알수있다. 2 4 6 10 16 피보나치의수열 4 / 제 1 장순열과조합
핵심체크 약수의개수와총합 약수와배수 1. 약수와배수 세개의정수 사이에 인관계가있을때, 를 의배수, 를 의약수라한다. 2. 배수판정법 1 2 의배수판정법 : 2 3 의배수판정법 : 3 4 의배수판정법 : 4 5 의배수판정법 : 5 6 의배수판정법 : 6 7 의배수판정법 : 7 8 의배수판정법 : 8 9 의배수판정법 : 9 11 의배수판정법 : + +, + + -2 + + ( + + )-( + ) 3. 약수의개수와총합 : 정수 가 과같이소인수분해될때 1 양의약수의개수 N= 2 양의약수의총합 S= 3 양의약수전체의곱 P= 4. 약수의개수로정수분류 1 약수의개수가 개 1 2 약수의개수가 개 소수 3 약수의개수가 개 ( 소수 ) 2 4 약수의개수가홀수개 ( 자연수 ) 2 노박사수학 / 5
심화학습 완전순열 약수와배수 1 에서 n 까지의번호가붙은 n 개의상자와 1 에서 n 까지의번호가붙은 n 개의공이 있다. 다음은각상자마다 1 개씩의공을임의로넣을때상자의번호와공의번호가맞는 것이하나도없는경우의수는 임을증명한것이다. 증명 공 1 을 2, 3,, n 의어느상자에넣는방법은 ( 가 ) 가지이고, 공 1 이 2 번상자에들어갈때, 다음과같이두경우가있다. ⅰ) 1 이 2 번, 2 가 1 번상자에들어가는경우는 가지 ⅱ) 1 이 2 번, 2 가 1 번상자에들어가지않는경우는 ( 나 ) 가지,, = ( 가 ) ᄀ ᄀ을변형하면 = = = = = ( 다 ) ᄂ ᄂ의양변을 n! 로나누면 다 n 에 2, 3,, n 을대입하여변끼리더하면 ( 가 ), ( 나 ), ( 다 ) 에알맞은것을순서대로적어라. 정답 : ( 가 ) ( 나 ) ( 다 ) 6 / 제 1 장순열과조합
02 순열
1. 순열 02 순열 서로다른 개의물건에서 개를택하여한줄로배열하는 것을 개의물건에서 개를택하는 순열이라하고 이경우의수를기호로 와같이나타낸다. (1) P r (2) 특히, 개를다뽑는순열의수는 (3) 1, P 1 P r 의계산 아래그림과같이 개의장소를미리만들어놓는다. 1 2 3 r 안에차례로서로다른것을택하여한개씩넣는다. 1 의장소에는 개중에서어느것이라도좋으니 n 가지 2 의장소에는 1 에이미한개를넣었으므로 n-1 가지같은방법을되풀이하면 r 의장소에는 n-r+1 가지따라서, 구하는순열의수 P r 는곱의법칙을이용하여 P r 8 / 제 1 장순열과조합
2. 인접순열 (1) 특정한원소끼리인접할때 인접하는것들을묶어서하나로생각하고, 묶인부분의자체내에서의순열의수를곱한다. 02 순열 ( 묶어서배열 ) ( 자리바꿈 ) (2) 특정한원소끼리인접하지않을때 인접해도좋은것을먼저배열하고, 그사이사이에인접하지못하는것들을배열하는순열의수를곱해준다. ( 나머지배열 ) ( 자리채움 ) 서로인접하지않는순열 서로다른 n 개의순서가정해진배열에서 서로인접하지않은 r 개를선택하여순서대로배열하는순열 r 개를제외한 n-r+1 개 ( 자리채움 ) P r 모델링 [modeling] 수리현상을특정한목적에맞추어이용하기쉬운형식으로 표현하는것을모델링 [modeling] 이라고한다. 예제 주차구역열군데에대형차두대와소형차세대를 주차시키는방법 ( 단, 대형차는두구역에걸쳐주차한다.) 1 2 3 4 5 6 7 8 9 10 P 두구역을폐쇄하고대형차가들어가면한구역을늘려준다. 노박사수학 / 9
3. 원순열 02 순열 서로다른 개의물건을원형으로배열하는순열 (1) 개의물건을배열하는원순열의수 (2) 개중 개를택한원순열의수 원순열의수 (1) ( 순열의수 ) ( 자리수 ) 가지 (2) 하나를고정한순열 10 / 제 1 장순열과조합
4. 다각형순열 ( 대칭인경우 ) 02 순열 (1) 정사각형식탁에 8 명이앉는방법 (2) 정삼각형식탁에 6 명이앉는방법 (3) 직사각형식탁에 10 명이앉는방법 노박사수학 / 11
5. 같은것이있는경우의순열 02 순열 개중에같은것이각각 개, 개, 개있을때, 이 개를모두택하여만든순열의수 ( 단, ) 모양과크기가같은흰공 2 개와검은공 3 개를나열하는순열의수구하는순열의수를 라하고그중하나인 에대하여 에서흰공을구별하여 1, 2 라하고, 검은공을구별하여 ❸, ❹, ❺ 라하면흰공 2 개를나열하는방법의수 검은공 3 개를나열하는방법의수 흰공 2 개, 검은공 3 개를배열하여 와같이나열하는방법의수 흰공 2개, 검은공 3개를구별하여 일렬로나열하는방법의수 12❸❹❺ 12❸❺❹ 12❹❸❺ 12❹❺❸ 12❺❸❹ 12❺❹❸ 21❸❹❺ 21❸❺❹ 21❹❸❺ 21❹❺❸ 21❺❸❹ 21❺❹❸ 순서가정해진순열 같은것으로생각하여배열 최단거리 A a a a B b b 1 3 6 10 1 2 3 4 1 1 1 A 에서 B 에이르는최단거리는 < 초딩해법 > 오른쪽으로세칸, 위로두칸이동하는경우이다. 즉, a a a b b 를나열하는경우의수와같다. A B 12 / 제 1 장순열과조합
6. 중복순열 02 순열 서로다른 개에서중복을허용하여 개를택하는순열을 개의물건에서 개를택하는중복순열이라하고 이경우의수를기호로 와같이나타낸다. 의계산 개를배열할자리를다음과같이나타내면 첫째칸에 n 가지, 둘째칸에도 n 가지,, 마지막칸에도 n 가지가들어갈수있으므로 노박사수학 / 13
심화학습 최단거리문제 최단거리문제 (1) A PQ 위의점 B A B A B P Q P Q B (2) A PQ 위의적어도한칸 B A B A A' B P Q P Q B B [ 한칸을지운다음멘아래에도달하면한칸을벌려준다,] 14 / 제 1 장순열과조합
심화학습같은것을포함하는원순열 같은것을포함하는원순열 빨간공네개와파란공두개를원형으로배열하는방법은그림과같이세가지이다. 이를구하는식을생각하여보자. 노박사수학 / 15
03 조합
1. 조합 03 조합 서로다른 개중에서순서를생각하지않고 개를택할때, 이것을 개에서 개를택하는조합이라하고, 이경우의수를기호로는 로나타낸다. np r (1) C r r (2) C n r (3) C r n C r (4) C, C 의계산 서로다른 개중에서 개를택하는조합을한줄로나열하는방법의수는 이므로 C r 개의조합으로만들수있는순열의총수는 양변을 으로나누면 C r P r 을대입하면 C r 노박사수학 / 17
03 조합 2. 조 ( 組 ) 로나누는방법 ( 분할 분배 ) 1) 서로다른 9 개의사과를 3 개, 3개, 3 개씩 분할 분배 (2) 서로다른 9 개의사과를 5 개, 2 개, 2 개씩 분할 분배 (3) 서로다른 9 개의사과를 4 개, 3 개, 2 개씩분할 분배 분할과분배 주는쪽받는쪽해법풀이 사과 5 개 3 무더기경우의수자연수의분할 과일 5 개 3 무더기경우의수집합의분할 (1, 1, 3) (1, 2, 2) (1,1,3) (1,2,2) 사과 5 개 3 명중복조합 3 H 5 과일 5 개 3 명중복순열 3 5 서로다르게구별되면, 이니면 18 / 제 1 장순열과조합
03 조합 3. 자연수의분할 (1) 자연수의분할 자연수 4 를순서를고려하지않고자연수의합으로나타내는방법은 4, 3+1, 2+2, 2+1+1, 1+1+1+1 와같이 5 가지임을알수있다. 이와같이자연수를순서를고려하지않고한개이상의자연수의합으로나타내는것을 자연수의분할이라하고, 자연수 을 개의자연수로분할하는경우의수를 n P k ( P : Partition ) 으로나타낸다. 3+1, 2+2 (2) 자연수의분할에관한성질 1 1 2 1 3 4 는 곳에 개를배치하는건데, 일단 곳에한개씩배치하고 나머지 개를한곳, 또는 2, 3,, k 곳에배치하면된다. 는자연수 1 을포함하는경우 자연수 1 을포함하지않는경우 노박사수학 / 19
03 조합 4. 집합의분할 (1) 집합의분할 집합을서로소인집합들의합집합으로나타내는것을 집합의분할 이라하고, 원소의개수가 개인집합을서로소인 개의집합의합집합으로나타내는경우의수를 n S k ( S : Stirling number) 으로나타낸다. (2) 집합의분할에관한성질 1 1 2 1 3 특정한원소 a 가분할할때혼자있는경우 a 가분할할때다른원소와같이있는경우 20 / 제 1 장순열과조합
5. 중복조합 03 조합 서로다른 개중에서순서를생각하지않고중복을허락하여 개를택할때, 이것을 개에서 개를택하는중복조합이라하고, 이경우의수를기호로는 H r 로나타낸다. H r 중복조합의계산 1, 2, 3, 4, 5 다섯개의수에서중복을허용하여세개의수를선택하는경우의수를구하여보자. (1) 각자리숫자에차례로 0, 1, 2 를더한숫자를대응시키면 111 123 112 124 113 125 114 126 115 127 122 134 123 135 124 136 125 137 133 145 134 146 135 147 144 156 145 157 155 167 222 234 223 235 224 236 225 237 233 245 234 245 235 246 244 256 245 257 255 267 333 345 334 346 335 345 344 356 345 357 355 367 444 456 445 457 455 467 555 567 (153 은 135 로간주하더라도경우의수는같다.) 1~7 에서세수를선택하는경우의수 C (2) 가로는 5 개의선을긋고세로는 3 개의칸으로만든바둑판모양의도형에서좌상단에서우하단에이르는최단거리는 가로 4 개, 세로 3 개의선분을지난다. 1 2 3 1 2 3 4 5 가로축의번호 3, 5, 5 (3) 네개의슬로트 //// 와세개의 를 순서대로나열하는경우의수 // / / 1/2/3/44/5 3, 4, 4
핵심체크 도형의해석 1. 삼각형 정십이각형의꼭지점위의세점을잡아만들어진삼각형 도형의해석 직각삼각형둔각삼각형예각삼각형 ❶ ❷ ❶ ❷ 원주위의세점을잡아만들어진삼각형 [ 심화 ] x y 2π-(x+y) 직각삼각형예각삼각형둔각삼각형 2. 직육면체 직육면체의각면에수를넣는경우의수 ( 뒤집거나회전하여같은경우는하나로생각 ) (1 1 1) 1 ~ 6 대면의합 : 7 ( 분할 ) ( 밑면 ) ( 윗면 ) ( 측면 ) ( 밑면 ) ( 윗면 ) ( 측면 ) 1 1 5 3! 1 1 2 (1 1 2) ( 분할 ) ( 밑면 ) ( 윗면 ) ( 측면 ) 6C2 1 1 3! ( 밑면 ) ( 윗면 ) ( 측면 ) 3 1 2 (3 1 2) ( 분할 ) ( 밑면 )( 윗면 )( 측면 ) ( 밑면 ) ( 윗면 ) ( 측면 ) 6C2 4C2 2C2 3 1 2 2 3 1 2 2 정팔면체 1 ~ 8 대면의합 : 9 ( 한면 ) ( 대면 ) ( 한면과이웃 ) ( 대면과이웃 ) 1 7 6C3 2! 3! ( 한면 ) ( 대면 ) ( 한면과이웃 ) ( 대면과이웃 ) 1 1 2 3 2! 1 22 / 제 1 장순열과조합
핵심체크 토너먼트대진 토너먼트대진표 4 강 8 강 16 강 경우의수 3 3 2 ( 3 2 ) 2 분할 ( ) 2 ( ( ) 2 ) 2 배열 명의학생이오른쪽대진표에따라게임을할때, 대진표를 작성하는방법 팀이오른쪽그림과같이시합을할때, 대진표를작성하는 방법 다섯학교에서 명씩대표를뽑아 다음그림과같은대진표에따라경기를하며같은학교 선수끼리는결승전외에는만나지않도록할때, 대진표를 작성하는방법 노박사수학 / 23
04 이항정리
1. 이항정리 04 이항정리 (1) 의전개식에서 의계수 (2) 파스칼의삼각형 (1) (2) ( 각수는왼쪽위와오른쪽위에있는두수의합 ) ( 각행의수는중앙에대하여좌우대칭 ) (3) (1 에서시작하여대각선방향으로수들을더하면꺽여진곳의수 ) 노박사수학 / 25
2. 이항계수의성질 04 이항정리 (1) x=1 : C n C n C n C n C n (2) x=-1 : C n C n C n C n n C n (3) C n C n C (4) C n C n C 의양변을미분하면, 에서 을대입하면 26 / 제 1 장순열과조합
핵심체크 이항계수의곱 의계산 (1) 의전개 에서 의계수 (2) 상자에서공을꺼내는방법 각각 20 개, 15 개의공이든 A, B 두상자에서 10 개의공을꺼내는방법 A B 20개 15개 10 개 A B 경우의수 0 개 10 개 1 개 9 개 2 개 8 개 10 개 0 개 계 노박사수학 / 27