이산수학 정주희경북대학교수학교육과 2017년 8월 31일 차례 1 시작하면서 2 1.1 NIM........................................... 2 2 순열과조합 4 2.1 순열과조합의기본.................................. 4 2.2 여러가지순열 조합................................. 8 2.3 2항계수와계차행렬.................................. 11 3 배열과분배 15 3.1 비둘기집의원리.................................... 15 3.2 포함배제의원리.................................... 17 3.3 분배와분할....................................... 19 1
1 시작하면서 1.1 NIM NIM 은 일단의대상을두고두사람이번갈아가면서가져가는게임 이라했다. (p26 정확한 수학적정의를내리지는않고 NIM 의예를몇개들면서알아보기로하겠다. 예제 1.1 (p25: 1.2.5 16 개의동전이탁자위에놓여있다. 갑과을이게임을하는데갑부터 시작하여번갈아한번에 4 개이하의동전을가지고갈수있다. 맨마지막동전을가지고 가는사람이이긴다고할때갑이이기기위한전략은? ( 풀이. 이게임의 상태 는현재까지가져간동전의개수로나타낼수있다. 상태들의전체집합은 S def {0,..., 16} 이고 종료승리상태 는 w 16 S 이다. 종료승리상태를만드는 사람이이긴다. 승리상태집합을 W {16, 11, 6, 1} 로정의하면이집합은다음의성질을가진다 : (1 W 에 속하는상태를받은사람이 move 하면반드시 W 밖으로나간다. (2 W 의여집합에속하는 상태를받은사람은잘하면 W 안으로들어올수있다. (3 종료승리상태 w 는 W 의원소이다. 처음에갑이받은상태 0 은 W 바깥의원소이므로 1 개를가져가서상태 1 W 를만들고, 이후로계속 W 의원소만상대방에게되돌려주면이긴다. NIM 게임에서의승리상태집합의성질 (1, (2, (3 을좀더수학적으로정의하면다음과 같다. 함수 f : S P 를 f(x {y y is obtained from x by a single move} 로정의하면 (i ( x W (f(x W (ii ( x W (f(x W (iii w W (W 예제 1.2 (p26: 게임 1 2개의통에각각 m, n 개의동전이담겨있다. 갑과을이게임을하는데규칙은다음과같다. (1 갑부터시작하여번갈아 1개이상의동전을가져간다. (2 한번가져갈때는하나의통에서만가져간다. ( 한통에서 1개, 다른통에서 2개이런식으로가져갈수없다. (3 마지막동전을가져가는사람이이긴다. ( 풀이. S {(i, j 0 i m, 0 j n} W {(i, i 0 i min(m, n} w (0, 0 2
그러므로 m n 이라면갑이이길수있다. 예제 1.3 (p27: 게임 2 3 개의통에각각 n 1,..., n 개의동전이담겨있다. 규칙은게임 1 의경우와같다. ( 풀이. 3, n 1 1 인경우를예로하여설명을시작하겠다. S {(i, j, l 0 i 1, 0 j n 2, 0 l n 3 } W { x S ( m ( x (1, 2m, 2m + 1 or x (1, 2m + 1, 2m or x (0, m, m } w (0, 0, 0 승리집합조건 (W 이만족됨을확인할수있을것이다. 예를하나더들어보겠다. 3 이고 n 1 14, n 2 3, n 3 7 로둔다. S 와 w 는당연한 방법으로정의하면되므로이들에대한정의는생략하기로하고, W 의정의는좀복잡하다. 일단 (i, j, l S 의각성분을 2 진법으로나타낸다. 예를들어초기상태 (14, 3, 7 은 14 1 1 1 0 3 0 0 1 1 7 0 1 1 1 이다. 이표의오른쪽부분의 3 4 행렬에주목한다. 각열에대해서 1 의개수가짝수개인 것을짝수열, 홀수인것을홀수열이라고부른다. 위의행렬에서왼쪽에서 1 번째와 3 번째열이 홀수열이고, 2 번째와 4 번째열은짝수열이다. 이제 W 는 모든열이짝수열인상태 들의집합으로정의한다. 그러면 (W 의 (iii 이만족됨은아주쉽게확인된다. (ii 가만족됨을확인해보기위하여위의예에서 14 개의동전이들어있는통에서 10 개를 꺼내보자. 결과로얻은상태는다음과같다. 4 0 1 0 0 3 0 0 1 1 7 0 1 1 1 이상태는 W 에속함을확인할수있다. 이런승리상태에서어느통이든하나를골라몇개든 동전을꺼내면그결과로얻은상태는반드시홀수열을포함하게됨을보여야한다. 조금만 생각해보면이건지극히당연하다. 하나의행을골라그것의숫자를줄이면그행에속하는 적어도하나의열은바뀌어야한다. 0 이었다면 1 로, 그리고 1 이었다면 0 으로. 그러므로행렬 에서그열은 1 이하나늘거나줄어들게되며, 따라서짝수열이었던것이홀수열로바뀌게될 것이다. (iii 이만족됨을보이는것이가장까다롭다. 홀수열이단하나만있는상태라면쉽다. 그 리고홀수열이여러개있다해도, 그모든홀수열들에서 1 을가지는행이존재한다면쉽다. 왜냐하면이런경우에는그행에속한홀수열들에있는숫자만 1 에서 0 으로바꾸면되기때 문이다. (14, 3, 7 T 에서 (4, 3, 7 T 를얻은것이바로이런경우에해당한다. (12, 3, 5 T W 같은 경우는조금더까다롭다. 3
12 1 1 0 0 3 0 0 1 1 5 0 1 0 1 첫째열과셋째열이홀수열인데, 이두열에서모두 1 을가지고있는행은없기때문이다. 그러나여기서잘생각해보면, 홀수열에서 1 을없애는것이아니라새로만들어내도된다! 그러므로첫째행에서첫째열은 1 을 0 으로바꾸고, 셋째열은 0 을 1 로바꾸면된다. 즉, 12 개의동전중에 6 개를꺼내서 6 개를남겨두면아래와같이 W 의원소를얻게된다. 6 0 1 1 0 3 0 0 1 1 5 0 1 0 1 이제일반적인비승리상태에서승리상태를얻는방법을설명하겠다. 비승리상태의행렬에는 반드시홀수열이있다. 홀수열중에가장왼쪽의것을골라거기서 1 을가진행을찾는다. 이 행에서몇개의동전을빼서승리상태를얻을수있음을보이겠다. 홀수열들을왼쪽부터차례로 C 1,..., C m 이라하자. 그리고 C 1 은 2 d 1, C 2 는 2 d 2,..., C m 은 2 dm 에대응된다하자. 그러면 d 1 > d 2 > > d m 이성립할것이다. C 1 에서 1 인행 R 을골라 거기서 2 d 1 개의동전을빼둔다. ( 빼서버리는것이아니라일단가지고있는다. 그러면이제 홀수열은하나줄어들어 C 2,..., C m 가남아있을것이다. 이제 R 의 C 2 가 0 이라면 R 에 2 d 2 의동전을넣어주고, R 의 C 2 가 1 이라면 R 에서 2 d 2 개 개의동전을더뺀다. 이제 C 2 는짝수열이 되었을것이다. 이런식으로 C m 까지계속작업한다. 이러한작업은가능하다, 왜냐하면 2 d 1 은 2 d 2 + + 2 dm 보다크기때문이다. 연습문제 1.4 (13, 17, 35, 38 T 를승리상태로바꾸려면어떻게해야하겠는가? 2 순열과조합 2.1 순열과조합의기본집합 X의순열은 X의모든원소를 중복과누락없이일렬로나열한것. 위의정의를엄격하게하자면집합 X의순열은 X의 cardinality, 즉원소의개수를 κ라했을때 에서 X로가는전단사함수를뜻한다. 우리는 κ가유한한경우, 즉 κ n N인경우만다룰것이다. X의일부원소만배열하는것도순열이라한다. 개의원소를취하여일열로배열한것을 X의 -순열이라고하며수학적으로는단사함수 σ : {1,..., } X로나타낼수있다. 원소의개수가 n인집합을 n-집합이라고부르기로한다. 그러면 n-집합의 -순열의개수는 np 개 n! {}}{ (n! n(n 1 (n + 1 (2.1 로주어지며이는교재에나와있는대로점화식 np 0 1 4
np n P 1 (n ( 1 을써서증명할수있다. 이것보다좀더흥미로운점화식으로 np 0 1 np n 1 P + n 1 P 1 (2.2 가있다. 연습문제 2.1 위의 (2.2 가성립하는이유를설명하고, 이점화식을이용하여 (2.1 을증명하시오. ( 힌트. n을포함하는순열과그렇지않은순열들로나누어생각한다. 연습문제 2.2 점화식 np 0 1, np n n 1 P 1 은어떤가? 이것을가지고 (2.1 을증명할수있는가? 집합의 - 부분집합은그집합의부분집합으로서원소의개수가 인것을말한다. 집합의 - 조합은곧 - 부분집합을뜻한다. n- 집합의 - 조합의개수는 nc ( n n! (n!! n P! 로주어지며이는교재의 (53 쪽, 정리 2.2.1 에있듯이 n P n C! 로부터유도할수도있 고, (88 쪽 에있듯이파스칼의삼각형에서ㄱ - 법칙이성립함을이용하여수학적귀납법으로 증명할수도있다. (2.3 순열과조합의개수에서자주등장하는팩토리얼함수 n! 은 n 이커짐에따라대단히빨리 증가하는특성을가지고있는데, 큰 n 에대하여 n! 이몇자리수인가, 즉 n! α 10 m, α < 1 으로두었을때 m 의대략적인값을 ( 계산기를써서 알아보려면스털링의공식을쓰면된다. n! ( n n 2πn e (2.4 예제 2.3 (1 100 개의똑같은의자를 5 개의교실에나누어넣으려고한다. 첫두교실에 50 개의의자 를넣는다면의자를분배하는방법은모두몇가지인가? (p64, #8 ( 풀이. 각교실에들어가는의자의수를 x 1,..., x 5 라하면이문제는 x 1 + x 2 50, x 3 + x 4 + x 5 50 의음아닌정수해 (x 1, x 2, x 3, x 4, x 5 의개수를세는문제이다. 따라서 이문제는디오판투스방정식의해의개수를공부한후에나와야하는문제이다.( 예제 2.6 참조. 아무튼답은 2 H 50 3 H 50 ( ( 51 50 52 ( 50 51 ( 1 52 2 이다. 5
(2 n 쌍의부부가파티에서만났다. 각사람은자기의배우자가아닌모든사람과악수했다. 이파티에서이루어진악수의총횟수는얼마인가? (p65, #11 ( 풀이. 파티의각참여자는 2n 명의참석자중에자신과자신의배우자 2 명을제외한 2n 2 명과악수를한다. 파티참여자의수는 2n 이며, 모든악수는두번카운트되고 있으므로 2n(2n 2 를 2 로나눈 2n(n 1 이답이된다. (3 일렬로놓여있는 2n 개의의자에남학생 n 명, 여학생 n 명을동성끼리는인접하지않 도록앉히는방법의수를구하라. (p65, #12 ( 풀이. 맨첫자리에남학생이오는경우는남학생자리 n 개, 여학생자리 n4 개에각각 n 명씩을앉히는방법은 n! n! 이다. 그런데맨첫자리에여학생이오는경우도있으므로 답은 2(n! 2 이다. (4 자연수 m, n, 에대한다음의등식을조합론적방법으로증명하라. (p65, #13.(1 ( m + n 2 ( m + 2 ( n + mn 2 ( 풀이. 좌변은 m + n 개의원소를가진집합에서 2 개의원소를뽑는방법의개수이다. 즉, m 개의원소를가진집합 A 와 n 개의원소를가진집합 B 가서로소일때, A B 에서 2 개의원소를뽑는것인데이것은다음 3 가지의경우로분할된다.( 즉, 중복과누락없 이나누어진다. 1 A 에서만 2 개의원소를뽑는경우, 2 B 에서만 2 개의원소를뽑는 경우, 3 A 에서 1 개, B 에서 1 개의원소를뽑는경우. 이각각의경우에뽑는방법의 수를합한것이우변이다. 그러므로좌변 우변이다. (5 자연수 m, n, 에대한다음의등식을조합론적방법으로증명하라. (p65, #14.(1, Vandermonde 의항등식 ( m + n i0 ( ( m n i i 예제 2.4 ( 풀이. 이것은바로위의문제에서 2 를 로일반화한것이다. 이때는 개의원소를뽑 는것은 +1 가지의경우로분할된다. 즉, i 0,..., 에대해서 A 에서 i 개, B 에서 i 개를뽑는것이다. 위식의우변은분할의각경우에대한방법의개수들을합한것이므 로좌변과같다. ( 더엄격하게하려면 A 에서뽑은원소는 B 에서뽑은원소들과관계가 없으므로 ( 각집합에서뽑아야할원소의개수가일단정해지면, 그다음각집합에서 어떤원소를뽑는가는독립적이다 방법의수를곱한다는말까지해야할것이다. 집합 {1, 2,..., n} 의모든 r- 부분집합들을생각하자. 각각의 r- 부분집합에서선택한가장작은 원소들의가중산술평균 (weighted arithmetic mean 은 n+1 r+1 임을증명하라. (p65, #10 ( 풀이. 가장작은원소가 1일때, 2일때,..., n r +1일때각각에해당하는 r-부분집합의개수는 ( ( n 1 r 1, n 2 ( r 1,..., r 1 개일것이므로원하는평균값은 1 (n r 1 ( n r n r+1 (2.5 6
이된다. 위식의분자를계산하기는쉽지않은데, (p107, #16 에서힌트를얻을수있다. n 0인임의의두정수 n, 에대하여 ( ( ( ( n n 1 n 2 + 2 + 3 + + (n + 1 ( n + 2 + 2 (2.6 이성립한다. ( 교재에나온식에는오타가 2 곳있다. 교재의식은 1 일때성립하지않음이쉽게확인된다. 를보여야한다. 파스칼의삼각형과ㄱ - 법칙을이용하기위하여위식의좌변을다음과같이 배열한다. ( ( +1 ( n 1. ( n 1 ( n ( +1 ( 위삼각형의맨왼쪽열의합은 n ( i i n ( i ( i0 n+1 +1 이다. (p94, 예제 2.4.7.(1 참조 왼쪽에서두번째열의합은 ( ( n +1 이다. 그리고맨오른쪽열의합은 +1 이다. 일반적으로 i 번째열의합은 ( n i+2 +1 이고 i 1,..., n + 1이므로결국삼각형전체의합은 n +1 i1 ( n i + 2 + 1 n+1 j+1 ( j + 1 n+1 j0 ( j + 1 ( n + 2 + 2 가된다. 이것으로 (2.6 의증명이완료되었다. (2.6 을다시쓰면 n +1 i1 ( n i + 1 i ( n + 2 + 2 (2.7 이다. (2.5 의분자는 n r+1 1 (n r 1 n r+1 i1 i (n i r 1 인데이것은 (2.7 에서 n을 n 1로, 를 r 1 로바꾼것이므로 (2.7 의우변은 ( n+1 r+1 (2.5 의분자 가된다. 그러면이제 (2.5 는 ( n+1 r+1 ( n r (n + 1!/((n r!(r + 1! n!/((n r!r! (n + 1!r! n!(r + 1! n + 1 r + 1 이되어원하는결과를얻는다. 예제 2.5 자연수 n, m, 에대한다음의등식을조합론적방법으로증명하라. (p65, #13.(2, Newton 의항등식 ( n m ( m ( n ( n m ( 풀이. 좌변의조합론적의미는왕의친위병 n 명중에서 m 명의경호대원을뽑고, m 명의경호 대원중에서다시 명의최측근경호대원을뽑는방법으로생각하면된다. 우변은 n 명중에서 정의 2.12 참조. 7
최측근경호대원 명을먼저뽑은다음에 n 명의남은친위병중에서일반경호대원 m 명을뽑는방법의개수이다. 이둘은서로같다. 2.2 여러가지순열 조합 중복순열의개수 : n Π r n r 집합 X 의원소들을 개의상자에나누어넣은것 을 X 의일반화된조합이라고한다. 이정의에서겹따옴표안의내용을좀더수학적으로엄격하게말해보자. n 1 + + n n 을만족하는음아닌정수 n 1,..., n, n 이주어졌을때집합 {(X 1,..., X n(x n, n(xi n i, n i1 X i X} 의원소들을일반화된조합이라하고, 이집합의원소의개수를 ( n n 1,...,n C(n; n1,..., n 로나타낸다. (Q: 상자들은구별되는가? 원소들은구별되는가? ( n n 1,...,n 의값을구하기위하여 4인경우를생각해보면 ( ( ( ( ( n n1 + n 2 + n 3 + n 4 n2 + n 3 + n 4 n3 + n 4 n4 n 1,..., n 4 n1 n 2 n 3 n 4 (n 1 + n 2 + n 3 + n 4! (n 2 + n 3 + n 4! (n 3 + n 4! (n 4! n 1!(n 2 + n 3 + n 4! n 2!(n 3 + n 4! n3!(n 4! n 4!(0! (n 1 + n 2 + n 3 + n 4! (n! n 1!n 2!n 3!n 4! n 1!n 2!n 3!n 4! 를얻는다. 그러므로 ( n C(n; n 1,..., n n 1,..., n n! n 1! n! (2.8 이된다. 2인경우는원래의조합에대응된다. 즉 ( ( n r n r, n r 이다. 원소의중복을허용하는집합을다중집합이라고하고 n 1 개 n 2 개 n 개 {}}{{}}{{}}{ { a 1,..., a 1, a 2,..., a 2,..., a,..., a } {n 1 a 1, n 2 a 2,..., n a } 로나타낸다. 이다중집합의순열의개수를 P (n; n 1,..., n 로나타내며, 이것의값이 일반화된조합의경우와같다. 즉, P (n; n 1,..., n C(n; n 1,..., n n! n 1! n! (2.9 이성립한다. 다중집합의순열을응용하는대표적인문제로바둑판도로망에서 (2차원또는 3차원 최단경로문제가있다. 다중집합에서 n i 들이모두 인경우를무한다중집합이라고부르고, 이경우에는집합 8
전체의순열보다는 r개의원소만취한순열의개수에관심을둔다. 이것의값은앞서나왔던중복순열과정확히일치한다. 즉, 무한다중집합 { a 1,..., a n } 의 r-순열은 n-집합의 r-중복순열이라고부르고이것들의개수는 n Π r r n 이다. 무한다중집합 { a 1,..., a n } 의 r-조합을 n- 집합의 r-중복조합이라고부르고이것들의개수를 n H r 로나타내며 ( n + r 1 nh r (2.10 r 이성립한다. 위의식은아래의디오판투스방정식의해의개수를세는문제에서유도할것이다. 예제 2.6 디오판투스방정식 x 1 + + x n r, (r 0, n 1 (2.11 의음아닌정수해의개수를구해보자. 이것은구별되는상자에구별안되는바둑알을넣 는문제로생각하수있다. 즉상자 1,..., 상자 n 에넣은바둑알의개수를 x 1,..., x n 으로보는 것이다. 쉽게접근하기위하여 n 3, r 5 인경우를생각해보자. 각각의해를다음과같은방 법으로하나의 {5 o, 2 +}- 순열에대응시킨다. 예를들어해 3 + 1 + 1 5 는 ooo + o + o 에대응되고, 해 0 + 2 + 3 5는 + oo + ooo로대응되게하는것이다. 이러한순열의개수는 P (7; 5, 2 ( 5+3 1 5 이다. 우리의다중집합에는 o가 바둑알의개수 만큼있고, + 가 변수의개수 1 만큼있다. 그러므로일반적인경우에해의수는 ( n+r 1 r 이다. nh r 은무한다중집합 A def { a 1,..., a n } 의 r-조합의개수로정의되었다. A의 r-조합 x 1 개 x n 개 {}}{{}}{은 { a 1,..., a 1,..., a n,..., a n }, (x 1 + +x n r 형태이므로이러한것들의개수는디오판투스 방정식 (2.11 과일치한다. 위의논의에서 1 대 1 대응 의개념을여러번사용한것에주목하자. 우리는무한다중집 합의 r- 조합을디오판투스방정식의해와대응시키고, 다시이를다중집합의순열에대응시켰 다. 좀더엄격하게말하자면 A 무한다중집합의 r- 조합들의집합 에서 B 디오판투스 방정식의해들의집합 으로가는전단사함수를구성하였고, 다시 B 에서 C 다중집합의 순열들의집합 로가는전단사함수를구성하였다. 경우의수를센다는것은결국어떤집합의원소의개수를알아내는것이며, 집합 A 의원 소의개수는그것과 1 대 1 대응되는다른집합 B 의원소의개수와같으므로, A 의원소를세는 것보다 B 의원소의개수를세는것이쉽다면, 이러한 B 를찾는것이우리가할일이된다. 예제 2.7 (p79, #2.3.13 11 권의책이책꽂이에나란히일렬로꽂혀있다. 이중 4 권을뽑되 뽑힌책들은서로인접하지않도록 ( 않았었도록 하는방법의개수를구하여라. ( 풀이. 교재와다른각도에서접근하겠다. 11 권의책들을집합 {1, 2,..., 11} 로나타내고뽑힌 4 권의책들을 {1, 3, 8, 10}, {4, 7, 9, 11} 등의부분집합으로나타내기로한다. 그렇다면구하는 디오판투스방정식의정의는유일하지않다. 정수해만찾는방정식을뜻하기도하고, 정수계수를가지는다항방정식 (polynomial equation 을뜻하기도한다. 여기서는후자의의미를사용하겠다. 9
답은아래의집합의원소의개수이다. {(x 1, x 2, x 3, x 4 1 x 1, x 4 11, x 1 + 1 < x 2, x 2 + 1 < x 3, x 3 + 1 < x 4 } (2.12 y 1 x 1, y 2 x 2 1, y 3 x 3 2, y 4 x 4 3 으로두면집합 (2.12 는전단사함수 (x 1, x 2, x 3, x 4 (y 1, y 2, y 3, y 4 에의하여집합 {(y 1, y 2, y 3, y 4 1 y 1 < y 2 < y 3 < y 4 8} (2.13 과 1 대 1 대응됨을알수있다. 그리고집합 (2.13 은다시아래의집합과 1 대 1 대응된다. {{y 1, y 2, y 3, y 4 } 1 y 1, y 2, y 3, y 4 8, } (2.14 그리고 (2.14 의원소의개수는다름아닌 ( 8 4 70 이다. 연습문제 2.8 중복조합들의개수공식 n H r n+r 1 C r 을아래의집합 A 와 1 대 1 대응되는집합 B 를찾아원소의개수를셈으로써얻어보라. A def {(x 1,..., x r 1 x 1 x 2 x n n} 연습문제 2.9 다음의조건을만족하는함수 f 들의개수를구하여라. f : {1, 2, 3, 4, 5} {1, 2,..., 19} f(n + 1 f(n + n, for x {1, 2, 3, 4} 연습문제 2.10 01 이꼭 m번나타나는길이 n의 {0, 1}-수열의개수를구하라. (p84, #8 ( 힌트. 문제에서말하는수열들은 0-블럭의시작위치와 1-블럭의시작위치로써결정된다. 수열의맨왼쪽위치를 1이라하고맨오른쪽위치를 n이라하자. 수열이 0으로시작하면 2m 개의위치를지정해야하고, 1로시작하면 2m + 1개의위치를지정해야한다. 후자의경우 1로끝나는경우와 0으로끝나는경우로나누어생각해도되겠지만, 위치 n + 1도존재하는것으로생각하면이렇게경우를나눌필요가없어편리하다. 연습문제 2.11 1, 2,..., 8 중 5개를 1번씩사용하여만들수있는 5자리의정수를작은것부터크기순서대로나열할때 25431은몇번째수인가? ( 힌트. 1로시작하는모든수는 25431 앞에나온다. 21, 22, 23, 24로시작하는모든수는 25431 앞에나온다. 이런식으로계속한다. 10
2.3 2항계수와계차행렬정의 2.12 파스칼의행렬은오른편그림과같이 ( n 들의값을배열하여행렬로만든것이다. n은맨 위쪽행의 0 에서시작하여아래쪽행으로가면서 증가하며, 는맨왼쪽열의 0 에서시작하여오른 쪽으로가면서증가한다. n < 인경우에는행렬의 원소는 0 이므로, 원소가양수인부분만보면삼각 형이되는데이삼각형을파스칼의삼각형이라고 한다. 맨왼쪽열과대각선에놓인쎌들의값은모두 1임에주목하라. 그리고공식 ( ( n n 1 ( 1 + n 1 는이그림에서ㄱ-법칙으로암기하면편하다. ( n 는 2항정리 (x + y n (x + 1 n n ( n n ( n 0 0 x y n, (2.15 x. (2.16 에서우변의다항식의항들의계수로나타나므로 2 항계수라고하기도한다. 2 항계수를포함 하는공식들중에중요한것들을알아보자. 예제 2.13 (1 n ( n 0 2 n : (2.16 의 x에 1을대입. (2 ( n ( odd n even 2 n 1 : (2.16 의 x에 1을대입하면간단히증명된다. 또하 def 나의증명방법이있는데이것은 X n {1,..., n} 의부분집합중원소의개수가짝수인 것을 짝부분집합, 원소의개수가홀수인것을 홀부분집합 이라고하고, 짝부분집합들 의개수를 f(n, 홀부분집합들의개수를 g(n 이라고둔다음, f(n g(n 2 n 1 임을 n 에대한수학적귀납법으로보이는것이다. 나머지부분은교재에나와있으며여기 서는생략한다. (3 n ( n 2 ( 0 2n ( n : 이것든 Vandermonde 항등식에서 m n인경우이다. n ( n n 임을이용한다. (4 n 0 ( n n2 n 1 : (2.16 의양변을 x 에대하여미분하고 x 1 을대입한다. (5 n 0 2( n n(n + 12 n 2 : (2.16 의양변을 x 에대하여미분한식의양변에 x 를곱한다음한번더미분한다. 그리고 x 1 을대입한다. (6 0 < p < 1, q 1 p일때 n 0 ( n p q (n np : (px + (1 p n 에대한 2항정리를사용한다. (7 n 0 ( np2( n 증명을응용한다. p q (n n 0 2( n p q (n (np 2 npq : 위에나온예들의 11
예제 2.14 (1 (2 (3 n i0 ( i ( n + 1 + 1 ( ( n + i n + + 1 i i0 n ( n i g n 이라하면 (g n n 은피보나치수열이다. i i0 위의 3 공식들은모두파스칼의삼각형을그리고ㄱ - 법칙을적용하여증명할수있다. 예제 2.15 5 i0 3 j0 ( i j 의값을구해보자. 우선이것은 의순서를뒤바꾸어얻은 3 j0 5 i0 ( i j 과값이같다는것을알아야한다. ( 일반적으로 2 개의 이있을때첨수변수의구간이상수들만으로이루어져있으면 의 순서를바꾸어도값이변하지않는다. 이제예제 2.14.(1 을이용하면답이쉽게구해진다. 연습문제 2.16 n ( ( ( m n m + n (1 를증명하라. i + i n i0 (2 n ( n+1 0 9 n 가 11의배수가되기위한자연수 n에대한조건은? (3 ( n 0 1 n 2( 1 + 1 n 3( 2 + ( 1 n 1 n n+1( n 의값은? ( 힌트. (2.16 의양변을부정적분하고 x 1을대입한다. 단, 적분상수를잊지말아야한다. 정의 2.17 수열 a (a 0, a 1, a 2,... 이주어졌을때, 이것의계차수열은 a ( a 0, a 1, a 2,..., where a i a i+1 a i 로정의된다. 이제귀납적으로 1 a a, n+1 a ( n a, (n 1, 2,... 로정의하고 n a, (n 0, 1,... 들을행으로가지는행렬을 a 의계차행렬이라하고아래의 그림과같이나타낸다. 12
계차행렬의 0 열에나타나는수열 d def (d 0, d 1,..., d n def (a 00, a 10, a 20,... 를 a 의쌍대수 열 (dual sequence 이라한다. 정리 2.18 수열 a 의제 n 항 a n 은그것의쌍대행렬과파스칼의행렬의제 n 행과의내적이다. 즉, a n 이성립한다. ( n d 0 + 0 ( n d 1 + 1 ( n d 2 + + 2 ( 증명. 교재의 p110, #2.5.1 에나와있다. ( n d n (2.17 n 따름정리 2.19 {a n } n 의쌍대수열이유한수열 (d 0, d 1,..., d, 0, 0,... 이고 d 0 라면일반항 a n 은 n 에대한 차다항식이다. 정리 2.20 (p113, #2.5.4 수열 a (a 0, a 1,... 의쌍대수열을 d (d n n 라놓았을때각 n 0, 1,... 에대하여 n ( ( n + 1 n + 1 a d 0 + d 1 + 1 2 0 이성립한다. ( 증명. a 의부분합 n 0 a s n 으로두고 x (x 0, x 1,... (0, s 0, s 1,... ( n + 1 3 d 2 + + ( n + 1 d n (2.18 n + 1 로두면 a 는 x 의계차수열이다. x 의쌍대수열은 (0, d 0, d 1,... 이므로정리 2.18 에의하여 ( ( ( n + 1 n + 1 n + 1 x n+1 d 0 + d 1 + 1 2 3 d 2 + + 이다. 그런데 s n x n+1 이므로우리가원하는 (2.18 을얻는다. ( n + 1 d n n + 1 정리 2.21 수열 a 의일반항 a n 이 n 에대한 - 차다항식이라면이수열의쌍대수열 d 는길이가 + 1 이다. 즉, d n 0, for n + 1, + 2,... 를만족한다. ( 이것은따름정리 2.19 의역이다. ( 증명. 이것은 (p114, #2.5.5 의따름정리이다. 예제 2.22 n 0 4 을 n 의식으로나타내어라. (p115, #2.5.6 13
중간시험은여기까지 14
3 배열과분배 3.1 비둘기집의원리정의 3.1 n+1 마리의비둘기를 n 개의비둘기집에넣으면 2마리이상들어간집이하나이상존재한다. 이사실을비둘기집의원리 (Pigeonhole principle 라한다. 연습문제 3.2 비둘기집의원리를증명하여라. ( 힌트 : 수학적귀납법 ( 정리 3.1.6 (p144 일단의실수들중에는그들의산술평균이상의수가존재한다. ( 증명. 주어진일단의실수 x 1,..., x n 의평균을 a 라하면 a x 1 + + x n n 이다. 모든 x i 가 a 미만이라고가정하면 na x 1 + + x n < a + + a na 라는모순을얻는다. 연습문제 3.3 (1 비둘기집의원리 ( 정의 3.1 를수학적귀납법을쓰지않고증명하여라. (2 일단의실수들중에는그들의산술평균이하의수가존재함을증명하여라. 비둘기집의원리는이해하기는대단히쉽지만활용하기는쉽지않을수있다. 무엇을비둘기로보고무엇을비둘기집으로보느냐가관건이다. 연습문제 3.4 (p151, #13 한변의길이가 1인정삼각형의내부에있는점들에대하여다음을증명하여라. (1 17 개의점중에는거리가 1 4 이하인두점이존재한다. ( 힌트 : 예제 3.1.1 p142 (2 33개의점중적어도세점은반지름이 3 20인원의내부에있다. ( 힌트 : 16개의작은정삼각형의외접원의반지름은얼마인가? 연습문제 3.5 (p151, #14 한변의길이가 1 인정사각형내부에있는 9 개의점중적어도세 점은넓이가 1 8 이하인삼각형의꼭짓점이됨을증명하여라. 단, 어느세점도한직선위에있지않다고한다. ( 힌트 : 4개의비둘기집을만들어보자. 연습문제 3.6 (p152, #15 다음을증명하여라. (1 가로, 세로의길이가각각 5, 6 인직사각형의내부에있는 8 개의점중에는거리가 10 이하인두점이존재한다. ( 힌트 : 직사각형을 7 개의구역으로나누어야한다. 각구역에 서두점간의거리의최댓값이 10 이하가되도록한다. 15
(2 좌표평면상의 5개의격자점중에는, 그점들을양끝점으로하는선분의중점도격자점인두점이존재한다. ( 힌트 : 1 4개의조각으로이루어진격자점들의 분할 을생각해야한다. 2 선분의중점의 x-좌표가정수이기위한조건은? y-좌표에대한조건은? (3 평면위에있는임의의볼록오각형에대하여 ABC 36 o 인세개의꼭짓점 A, B, C 가존재한다. ( 힌트 : 그림을그려보라. 별모양도형의꼭짓각들의합이 180 o 임을이용한다. 또는, 인접한두변을품는삼각형의꼭짓각중에서찾으려면, 이때는내각중에 540 o /5 108 o 이상인것이존재한다는것을이용한다. 연습문제 3.7 집합 X {0, 1, 2,..., 2n} 의임의의 (n + 2-부분집합의원소중에는합이 2n인두수가존재함을증명하여라. X에서 0을빼면문제가어떻게달라질까? ( 힌트 : p142, 예제 3.1.2, p150 #3 연습문제 3.8 200 이하의자연수중에서 n개를택하면그중하나는다른하나의약수임이보장되는최소의 n을구하여라. ( 힌트 : p150 #1 연습문제 3.9 (p150, #5 다음을증명하여라. (1 13개의정수중에는차가 12의배수가되는두수가존재한다. ( 힌트 : 12로나눈나머지들을 12개의비둘기집으로본다. (2 5개의정수중에는합이 3의배수인세수가존재한다. ( 힌트 : 법 3으로생각한다. 4개의정수중에는합이 3의배수인세수가존재하지않을수있음을보인다. (3 100 이하의자연수 53개중에는 1 차가 12가되는두수는존재하지만, 2 차가 11이되는두수가반드시존재하지는않는다. ( 힌트 : 100 이하의자연수중에 12로나눈나머지가 1인 6개의숫자중에는차이가 12인두수가존재한다. 나머지가 2, 3, 4일때도마찬가지. 나머지가 5 이상또는 0인경우에는 5개의숫자로충분하다. 2에대한답은 1 11, 23 33,... (4 n 2일때 (n + 2 개의 3n 이하의자연수중에는그차가 n보다크고 2n보다작은두수가존재한다. ( 힌트 : n + 1로나눈나머지가 로동일한두수가존재한다. 이두수의차이가 n+1이면문제가없다. 와 2n++2의두수가뽑혔을경우만해결하면된다. 뽑힌수중에 +3,..., 2n+ 1가하나라도있으면문제가없다. +1, +2, 2n+, 2n++1 중에기껏해야 2개밖에뽑힐수없다. 이제남은 1,..., 1, 2n + + 3,..., 3n을다뽑아도 n 3개다. 지금까지총 n + 1개를뽑았는데마지막남은 1개는어디서도뽑을수없다. (5 2n 이하인 (n+1 개의서로다른자연수중에는서로소인두수가존재한다. ( 힌트 : 차이가 1인두수는서로소이다. 왜냐하면두자연수의선형조합은최대공약수의배수이기때문이다. (6 1, 4, 7,..., 100에서임의로택한 20개의수중에는그합이 104인수의쌍이적어도 2개존재한다. ( 힌트 : 연습문제 3.7 연습문제 3.10 (p150, #6 n 2 + 1개의서로다른수로이루어진수열은길이 n+1인증가또는감소하는부분수열을가짐을증명하여라. ( 힌트 : a 1,..., a n 2 +1이길이 n + 1인증가하는부분수열을가지지않는다고가정한다. 각 1,..., n 2 + 1에대하여 a 에서시작하는가장긴 16
증가하는부분수열의길이를 m 라하면 m n이다. m 의값이같은 를 n + 1개취할수있다. a 1,..., a n+1 은감소수열이다. 연습문제 3.11 (p151, #8 임의로주어진서로다른 11개의정수중에는적당한연산부호로연결하면그결과가 1155의배수가되는 8개의정수가존재함을증명하여라. ( 힌트 : 1155 3 5 7 11이므로 11개의정수중에 2개를취하여차이가 3의배수가되도록할수있고,... 연습문제 3.12 (p151, #10 10시간동안 45m를걸어간어떤사람이첫한시간에는 6m를걷고마지막한시간에는 3m를걸었다고한다. 이사람은어떤연속된 2시간동안 9m 이상걸었음을증명하여라. ( 힌트 : 원래는 ( i 9(x i +x i+1 6 을증명하는문제인데이보다조금쉬운문제인 ( i 4(x 2i + x 2i+1 6 을풀도록한다. 연습문제 3.13 (p151, #11 어떤운동선수는매일한번이상, 일주일에 12번이하의연습을 12 주간 (84일 계속하였다고한다. 이선수가곡 23회연습한연속된몇날이있음을증명하여라. ( 힌트 : p143, 예제 3.1.4 연습문제 3.14 (p151, #12 원탁에 10명의손님의자리가명찰과함께놓여있다. 10명의손님이명찰을확인하지않고아무렇게나앉았는데, 제자리에않은손님이 1명도없었다. 이때명찰이놓인원탁을적당히회전시키면적어도 2명의손님이제자리에앉게됨을보여라. ( 힌트 : p145, 예제 3.1.7과비슷하나조금쉽다. 3.2 포함배제의원리 이절에서사용하는모든집합은유한집합이다. 집합 X 의원소의개수를 X 로나타내기로한다. 우리는다음의사실을잘알고있다. A B A + B A B, A B C A + B + C A B B C C A + A B C. 포함배제의원리는위의사실을아래와같이일반화한것이다. I {1, 2,..., n} 이라하고각 i I에대하여집합 A i 가존재할때 A i i I n ( 1 1 β, where 1 β J I, J j J A j. (3.1 즉, β 1 A 1 + A 2 + + A n, β 2 A 1 A 2 + + A n 1 A n, β 3 A 1 A 2 A 3 + + A n 2 A n 1 A n, 17
이다. 일반적으로 β 는 ( n 개의항의합임을알수있다. 그리고거의모든문제에서이항들의값은동일하다. 예제 3.15 (p160, 3.2.6 n- 집합에서 r- 집합으로가는전사함수의개수를 T (n, r 이라했을때 이다. T (n, r r ( r ( 1 (r n (3.2 0 ( 풀이. {1,..., n} 에서 {1,..., r} 로가는함수의개수는, f 에아무런조건이없다면 r n 이다. f가전사함수라는것은모든 i 1,..., r에대해서 f가 i를함수값으로가진다는것이므로, 이러한 f들의집합을 B i 라하면 r i1 B i 가곧우리가원하는 T (n, r 이될것이다. 문제는 r i1 B i 의값을구하기가쉽지않다는것이다. 이문제를해결하기위하여각 i 1,..., r에 def 대하여 A i Bi c로두면 r r B i i1 i1 A c i ( r c A i r n r A i i1 이다. 여기서 r i1 A i 의값을구할때포함배제의원리를사용하게된다. (3.1 에서의 β 는각 1,..., r 에대하여 ( r (r n 이므로 를얻는다. T (n, r r n r ( r ( 1 1 (r n 1 i1 r ( r ( 1 (r n 0 {1,..., n} 의순열 σ 중에 i. σ(i i 를만족하는것들의개수를 n- 번째교란수라고하고 D n 으로나타낸다. 정리 3.16 (p162, 3.2.7 n ( 1 D n n!! 0 (3.3 ( 풀이. {1,..., n} 의순열 σ 중에 σ(i i 를만족하는것들의집합을 A i 라하고 n! n i1 A i 를포함배제의원리를사용하여계산하면된다. 각 1,..., n 에대하여 이므로 β 가된다. D n n! ( n (n! n!! ( 1 i1 1 n! n! n! ( 1! 0 18
연습문제 3.17 (p166, #7 갑식이는어느일주일동안매일 8 명의친구중 2 명씩을저녁식사에 초대한다는계획을세웠다. 8명모두를적어도한번이상올수있도록초대하는방법의수를구하여라. ( 힌트 : 특정한친구 명을초대하지않는방법의수는 ( 8 7 2 이다. 그리고친구 명을선택하는방법의수는당연히 ( 8 이다. 연습문제 3.18 (p166, #8 1 학년부터 6 학년까지한학년에한반씩 6 개반과, 한반에한명씩 6 명의교사로구성된어느초등학교가있다. 다음해에학생들이한학년씩진급을하는데, 각 학년의학생들이모두새로운담임을만나도록교사를배정하는방법의수를구하여라. ( 힌트 : σ(i i + 1 for i 1,..., 5. 6 학년담임선생님은어떤학년을맡게되든상관없음. 연습문제 3.19 (p166, #9 1 에서 9 까지의자연수를배열하는데, 1 이 2 의오른쪽에또는 2 가 3 의오른쪽에또는 3 이 4 의오른쪽에있도록배열하는방법의수를구하여라. 단, 여기서 오 른쪽 이라고해서인접할필요는없다. ( 힌트 : 3 개의조건중특정한하나의조건을만족하는 배열의수 9! 9! 2!. 특정한두조건을만족하는배열의수 3!. 연습문제 3.20 (p167, #10 (1 1 어떤모임에온 n쌍의부부가서로동시에악수하는방법의수를구하여라. 2 ( ( 2n 2n 2 ( 2 2 2 2 는왜틀린답인지설명하여라. ( 힌트 : 1 첫사람이악수할수있는사람은 2n 1. 남은사람들중에첫사람이악수할수있는사람은 2n 3. 2 중복이 있다. (2 n 쌍의부부가서로동시에악수하되어느누구도자신의배우자와는악수하지않는방 법의수를구하여라. ( 힌트 : 포함배제의원리사용 연습문제 3.21 (p167, #12 디오판투스방정식 x 1 + x 2 + x 3 + x 4 25, x 1 > x 4 의음아닌 정수해의개수를구하여라. ( 힌트 : 0, 1,..., 12 에대해서 x 1 x 4 인해를제외한다. 연습문제 3.22 (p168, #17 0, 1,..., 9 의순열중첫번째숫자는 1 보다크고마지막숫자는 8 보다작은것의개수를구하여라. ( 힌트 : 포함배제의원리 ( 혹은드모르강의법칙 3.3 분배와분할 0 n 라할때, n 개의대상을 개의상자에넣는방법으로다음과같은 8 가지경우를생각 할수있다. 이경우들을 대상 - 상자조합 이라고부르기로한다. 맨오른쪽열에보인 방법의 수 에대하여는이섹션에서상세히설명할것이다. 대상구별상자구별빈상자없음방법의수 1 1 1 T (n, 1 1 0 n 1 0 1 S(n, 1 0 0 i0 S(n, i 0 1 1 H n 0 1 0 H n 0 0 1 p(n, 0 0 0 i0 p(n, i 19
경우의수를구하는문제에서대상을구별하는지그렇지않은지가명시되어있지않은경우가많다. 명시되어있지않은경우에는사람, 카드, 편지등은구별되는것이고바둑돌, 구슬등은 ( 색깔이같다면 구별되지않는것으로보는것이보통이다. 상자는방, 우체통등대부분의경우구분이되는것으로보며, 예외로구분되지않는것으로보는상자는 그룹 이다. 8 가지의대상-상자조합중에서먼저 111과 110에대해서생각해보자. 대상을상자에넣는방법의수를알고자할때, 대상과상자는그것들의내용은상관없이개수만알면되므로대상들을 {1,..., n}, 상자들을 {1,..., } 로둔다. 대상을상자에넣는것을함수 f : {1,..., n} {1,..., } 로보고논의하기로한다. 즉, 대상 x를상자 y에넣는것을 f(x y로생각한다. 그리고이러한함수의개수가몇개인지를알아내는것이우리가할일이다. 대상과상자의차이는, 하나의대상은단하나의상자에들어가야하지만, 하나의상자는여러개의대상을받아들일수있다는것이다. 이것이바로함수의개념과일치한다. 함수의값 f(x 는 x가정해지면이것에따라서유일하게정해지지만, 함수의값이 y라하면 ( 즉, 공역의원소를하나취하여그것을 y로나타낸다면 f(x y가되는 x들의집합을 f 1 (y {1,..., n} 로나타내기로할때, f 1 (y 는 2 n 개의부분집합중어떤것도될수있다는것이다. 빈상자를허용하지않는다는것은모든 y에대해서 f 1 (y 라는뜻이며, 이는곧 f 가전사함수라는것을의미한다 이것은대상-상자조합 111에해당한다. 빈상자를허용하는것, 즉대상-상자조합 110은 f 1 (y 에대해아무런조건이없다는뜻이다. f에대한조건은정의역이 {1,..., n} 이고공역이 {1,..., } 라는것뿐이다. 이러한함수 f는유한열 f(1, f(2,..., f(n 으로나타낼수있다. 각 f(i 들은 1,..., 중어느하나의값을가진다. n 1이라면이러한 f는 개존재한다. 길이가 n + 1인유한열은길이 n의유한열에 개의가능한값중에서어느하나를골라덧붙이는것이므로, 이러한유한열의개수는 ( 길이 n의유한열의개수 가될것이다. 길이가 n인유한열의개수는귀납가설에의하여 n 이므로이제수학적귀납법에의하여 110 대상-상자조합에서 방법의수 는 n 이됨을알수있다. 111 대상-상자조합에서의방법의수 T (n, 는포함배제의원리를이용하여 (3.2 에서알아낸바있다. 이제 101 조합, 즉대상은구별되고, 상자는구별되지않으며빈상자는없는경우에대하여알아보자. 이때의 방법의수 를 S(n, 로나타내고제2종스털링수라고부른다. 그리고이렇게대상을상자에넣는것을 그룹으로나누었다 고말한다. 왜냐하면그룹은통상서로 20
구별하지않기때문이다. ( 그룹 은비어있지않고구별되지않는상자를뜻한다고보면된다. 물론그룹은그안의원소들에의하여는구별된다. S(n, 는 111 조합에대한답, 즉 T (n, 를이용하여쉽게구할수있다. 전사함수 f : {1,..., n} {1,..., } 가주어지면 f 1 (1 은상자1에넣고, f 1 (2 는상자2에넣고,... 이런식으로상자에넣는다. 이제상자에붙은번호 1,..., 를모두지워버려 ( 그리고상자들의위치를뒤섞어놓아 상자들을구별하지않기로한다. 그러면원래는다른함수였으나이제는구별되지않는것들이생길것인데, 정확히! 개의 ( 원래는달랐던 함수들이서로구별되지않을것이다. 구별되지않는함수 들을분할이라고한다. 역으로생각하면, {1,..., n} 를 개의그룹으로나눈뒤에, 각그룹에번호를 1,..., 로주고그룹 i에들어있는 x들에대하여 f(x i로줌으로써전사함수 f를만들어낼수있다. 그러므로아래의식을얻는다. S(n, T (n,! (3.4 제 2 종스털링수 S(n, 를 T (n, 를사용하지않고직접얻는방법이있다. 이방법은ㄱ - 열법칙 이라고부르며, 이것으로닫힌식은얻을수없지만점화식을얻을수있다. ㄱ - 열법칙은아래의식을말한다. S(n, S(n 1, 1 + S(n 1, (3.5 그림에서는 ( 가 + ( 나 ( 열번호 ( 다 를뜻한다. (3.4 가성립하는이유는 n이혼자서그룹을이루는경우와그렇지않은경우로나누어생각하면알수있을것이다. 다음의정리는스털링에의하여밝혀진것으로증명없 이명제만제시한다. 그림 1: S(n, 정리 3.23 n x n S(n, [x] 0 제2종스털링수를알았으니이제는제1종스털링수에대하여알아보자. 이수는 s(n, 로나타내며 n명을 개의원탁에않히는방법의수를뜻한다. s(n, 에대한점화식은ㄱ-행법칙에의하여얻을수있다. 21
ㄱ - 행법칙은아래의식을말한다. s(n, s(n 1, 1 + (n 1 S(n 1, (3.6 그림에서는 ( 가 + ( 나 ( 행번호 ( 다 를뜻한다. (3.4 가성립하는이유는 n이혼자서한원탁을독차지하고앉는경우와그렇지않은경우로나누어생각하 면알수있을것이다. 그림 2: s(n, 정리 3.24 n [x] n ( 1 n+ s(n, x 0 이제 4 번째대상 - 상자조합 100, 즉 n 명을몇개의그룹으로나누는방법의수에대해서 알아보자. 이수는 B n, 벨수라고하는데 S(n, 를이용하여아주쉽게구할수있다. n 명을 개의그룹으로나누었다면 는 1 부터 n 사이의자연수가될것이므로 B n n S(n,, n 0, 1,... 0 0 를넣은것은 B 0 1 로정의했기때문이다. n > 0 인경우는 S(n, 0 0 이므로아무문제 없다. B n 은 n명을 n개이하의그룹으로나누는방법의수인데, 우리가대상-상자조합 100 에서우리가원하는것은 n명을 개이하의그룹으로나누는방법의수이므로 i0 S(n, i 가된다. 지금까지는대상이구별되는경우에대하여공부하였다. 이제대상이구별되지않는경우에대해서알아보자. n개의바둑돌을구별되는 개의통에넣는방법의수는디오판투스방정식의음아닌해의개수와같다. x 1 + + x n (3.7 x i 를 i번째통에들어간바둑돌의개수로보는것이다. 이때해의개수가 H n 임은앞서구한바있다. x i 0를허용하는것은빈상자가있을수있다는뜻이다. 즉, H n 은대상-상자조합 010에서방법의수이다. 011 조합, 즉빈상자를허용하지않는경우는 (3.7 에서 x i > 0 조건을만족하는해만인정하는것으로보면된다. x i 1 y i 로두면 (3.7 은 y 1 + + y n n 가되므로, 이때구하는방법의수는 H n 가됨을쉽게알수있다. 22
이제 n개의바둑돌을 개의그룹으로나누는대상-상자조합, 즉 001에대해서방법의수를구해보자. 이방법의수는 p(n, 로나타내며 n의 -분할수 (partition number 라고한다. p(n, 는자연수 n을 개의자연수의합으로나타내는방법의수와같다. 예를들면 7을 3개의자연수의합으로나타내는방법은 7 5 + 1 + 1 4 + 2 + 1 3 + 3 + 1 3 + 2 + 2 의 4 가지이므로 p(7, 3 4이다. 디오판투스방정식에서는 (x 1, x 2, x 3 (5, 1, 1 과 (x 1, x 2, x 3 (1, 5, 1, (x 1, x 2, x 3 (1, 1, 5 를 3개의해로구별하여본다는점이지금과다르다. p(n, 는 n > 0인경우에대해서만생각한다. 우선 p(n, n p(n, 1 1임을알수있다. > n > 0인경우에는 p(n, 0로둔다. 그리고 n > > 0에대한 p(n, 는아래정리의점화식을사용하여구할수있다. 정리 3.25 p(n, p(n, 1 + p(n, 2 + + p(n, (3.8 ( 증명. n개의바둑돌을구별이안되는 개의통에빈통이없도록넣는방법의수를구하면된다. 빈통을없애기위하여먼저각통에 1개씩넣는다. 그리고남은 n 개의바둑돌을 개의통에넣을것인데, 이번에는바둑돌을배정받지못하는통이있어도된다. 즉, i 1,..., 개의통에빈통이없도록넣으면된다. (3.8 을이용하여 p(n, 표를채우는과정을보자. 아래의 3개표중왼쪽표는 p(n, n p(n, 1 1을이용하여만든것이다. 가운데표는 p(n, 2 p(n 2, 1+p(n 2, 2 를 n 3,..., 6에대해서계산한것이다. n 3 에대한계산은붉은색으로나타내었고, n 4에대한계산은보라색으로나타내었다. 오른쪽표는 p(n, 3 p(n 3, 1 + p(n 3, 2 + p(n 3, 3 에대해서계산한것이다. n 5 에대한계산을붉은색으로나타내었다. n\ 1 2 3 4 5 6 1 1 0 0 0 0 0 2 1 1 0 0 0 0 3 1 1 0 0 0 4 1 1 0 0 5 1 1 0 6 1 1 n\ 1 2 3 4 5 6 1 1 0 0 0 0 0 2 1 1 0 0 0 0 3 1 1 1 0 0 0 4 1 2 1 0 0 5 1 2 1 0 6 1 3 1 n\ 1 2 3 4 5 6 1 1 0 0 0 0 0 2 1 1 0 0 0 0 3 1 1 1 0 0 0 4 1 2 1 1 0 0 5 1 2 2 1 0 6 1 3 3 1 대상 - 상자의마지막조합인 000 은 n 개의바둑돌을구별안되는 개의통에빈통을허 용하여넣는것을뜻한다. 이것은 n 개의바둑돌을구별안되는 개이하의통에빈통이 없도록넣는것과같다. 따라서이렇게넣는방법의수를 p (n 이라하면 p (n p(n, 1 + + p(n, (3.9 가된다. p n (n def p(n 을 n 의분할수라고정의한다. 23
n을 개이하의자연수의합으로 ( 순서를고려하지않고 나타내는방법수를 p (n 이라하였는데, 이번에는 n을 이하의자연수의합으로나타내는방법수를생각해보자. 이수를 q (n 으로나타내면 q (n p (n 임을패러즈다이어그램 (Ferrers diagram 을통하여보일수있다. 예를들어 21 8 + 6 + 3 + 3 + 1은오른쪽그림과같이나타낼수있다. 이그림은 21을 5개이하의그룹으로분할한하나의예를보여준다. 그런데이그림은, 8개의열각각에있는점들의개수를세어보면, 21을 5 이하의자연수들로분할한하나의예, 즉 21 5 + 4 + 4 + 2 + 2 + 2 + 1 + 1를보여주는것으로해석할수도있다. 일반적으로 n을 개이하의그룹으로분할한것은, 페레즈다이어그램을통하여, n을 이하의자연수들로분할한것과 1대1 대응이된다. 따라서 q (n p (n 이다. 그림 3: Ferrers Diagram 연습문제 3.26 q(, n def q (n q 1 (n 으로정의하면 q(, n 의의미는무엇인가? 연습문제 3.27 (p191, #1 7 명의사람을 4 개의그룹으로가르는방법의수를구하여라. ( 힌트 : S(7, 4 연습문제 3.28 (p191, #2 수의집합 X 의원소의합을 σ(x 로나타내기로하자. 집합 {1, 2,..., 101} 을조건 σ(x +1 σ(x + 6, ( 1, 2, 3, 4, 5 를만족하는 6개의부분집합 X 1,..., X 로분할하는것이가능한가? ( 힌트 : 이문제는이섹션에서공부한내용과무관하다. 단순한등차수열문제임. 연습문제 3.29 (p191, #3 n 개의서로다른소수의곱으로표현되는자연수를 n 개의인수의곱으로나타내는방법의수를구하여라. ( 힌트 : p172 #3.3.2. 인수 1 허용? 연습문제 3.30 (p191, #6 자연수 n을 1과 2의합으로나타내는방법 ( 더하는순서를바꾸는것은다른방법인것으로간주 의수를 A(n 이라하고, 2 이상의자연수들의합으로나타내는방법 ( 더하는순서를바꾸는것은다른방법인것으로간주 의수를 B(n 이라고하면 A(n B(n + 2 임을증명하라. ( 힌트 : n 1, 2, 3, 4, 5, 6에대해서 A(n 과 B(n + 2 을각각계산하여값이같음을확인한다. A(n 중에 2의개수가 인것들의개수는 B(n+2 중에 +1 개의합인것들의개수 +1 H n+2 2(+1 과대응됨을보인다. 연습문제 3.31 (p192, #9 제1 스털링행렬의제n행의합을구하여라. ( 힌트 : 행렬을그리고값을유추하여 n의식으로나타낸다. 그리고ㄱ-행법칙과수학적귀납법을사용하여이것이옳음을증명한다. 연습문제 3.32 (p193, #14 집합 X {1, 2,..., 14} 에대하여다음을구하여라. 24
(1 X를공집합이아닌 4개의부분집합으로분할하는방법의수. ( 힌트 : 대상-상자조합 101 (2 X를크기가 2, 3, 4, 5인 4개의부분집합으로분할하는방법의수. ( 힌트 : p70, 일반화된조합 (3 X를크기가 3, 3, 4, 4인 4개의부분집합으로분할하는방법의수. ( 힌트 : 일반화된조합과약간다름. 연습문제 3.33 (p193, #18 n-집합에서 -집합으로가는함수로서변역의원소의개수가 r 이상인것들의개수는 P r S(n, 4 임을증명하여라. ( 힌트 : T (n, r 을이용한다. - end - 25