[ J ]	ApodeixiS 정의/정리/증명집 경우의 수

5A ACADEMY

SOOHAN

	APODEIXIS [경우의 수]

[경우의 수 용어의 정의] (1) 원순열 (2) 중복순열 (3) 중복조합 (4) 이항정리, 이항계수

	APODEIXIS [경우의 수]

001. 서로 다른 [eqn: n]개 중 [eqn: r]개를 택하여 일렬로 나열하는 경우의 수 [eqn: `_n {rmP}_r]은 [eqn: n CDOT (n-1) CDOT (n-2) CDOT CDOTS CDOT (n-r+1)= {n!} over {(n-r)!}] 임을 보여라. 가장 앞자리에 [eqn: n]가지, 각각의 경우마다 두 번째 자리에 [eqn: (n-1)]가지, 각각의 경우마다 세 번째 자리에 [eqn: (n-2)]가지, [eqn: cdots] 마지막 [eqn: r]번째 자리에 [eqn: (n-r+1)]가지가 가능하다. [순열] .
002. 서로 다른 [eqn: n]개 중 [eqn: r]개를 택하는 경우의 수 [eqn: ` _{n} {rmC} _{r}]은 [eqn: {{} _{n} rm P it rm _{r} it} over {r!} = {n CDOT (n-1) CDOT CDOTS CDOT (n-r+1)} over {r CDOT (r-1) CDOT CDOTS CDOT 1} = {n!} over {r!(n-r)!}] 임을 보여라. 서로 다른 [eqn: n]개에서 [eqn: r]개를 택하여 한 줄로 나열하는 경우의 수 [eqn: `_n {rmP}_r]은, 서로 다른 [eqn: n]개에서 [eqn: r]개를 택하는 경우의 수 [eqn: `_n {rmC}_r]과, 각각의 경우에 대하여 [eqn: r]개를 한 줄로 나열하는 경우의 수 [eqn: r!]의 곱이다. [조합] .

	APODEIXIS [경우의 수]

003. 서로 다른 [eqn: n]개를 원형으로 배열하는 원순열의 수는 [eqn: (n-1)!]임을 보여라. 증명1) 한 줄로 나열하는 [eqn: n!]가지 중 회전하여 일치하는 경우가 [eqn: n]가지씩 존재한다. 증명2) 하나를 임의로 배열하고, 나머지 [eqn: (n-1)]개를 배열한다. 따라서 [eqn: 1 TIMES (n-1)!]이다. [원순열] .
004. 서로 다른 [eqn: n]개 중 중복을 허용하여 [eqn: r]개를 택하여 일렬로 나열하는 경우의 수 [eqn: ` _{n} PI _{r}]는 [eqn: n^r]임을 보여라. [eqn: r]개의 자리에 올 수 있는 것이 각각 [eqn: n]가지이므로. [중복순열] .

	APODEIXIS [경우의 수]

005. 같은 것이 각각 [eqn: p]개, [eqn: q]개, [eqn: cdots], [eqn: r]개씩 있는 [eqn: n]개를 일렬로 나열하는 경우의 수는 [eqn: {n!} over {p!q! CDOTS r!}] (단, [eqn: p+q+cdots+r=n]) 임을 보여라. 모두 다른 것으로 보고 나열한 다음, 같은 경우가 나오는 경우의 수로 나눠준 것이다. [같은 것이 있는 순열] .
006. 서로 다른 [eqn: n]개 중 중복을 허용하여 [eqn: r]개를 택하는 경우의 수 [eqn: ` _{n} {rmH} _{r}]은 [eqn: ` _{n+r-1} rm C it rm _{r}]임을 보여라. [eqn: r]개의 공과 [eqn: (n-1)]개의 칸막이를 한 줄로 나열하는 경우의 수이다. [중복조합] .

	APODEIXIS [경우의 수]

007. [eqn: a+b+c=n]을 만족시키는 (1) [eqn: a], [eqn: b], [eqn: c] 중 중복을 허용하여 [eqn: n]개를 선택하는 경우의 수와 같다. (2) [eqn: (a-1)+(b-1)+(c-1)=n-3] (1) 음이 아닌 정수 [eqn: a], [eqn: b], [eqn: c]의 순서쌍 [eqn: (a,```b,```c)]의 개수가 [eqn: `_3 {rmH}_n]임을 보여라. (2) 자연수 [eqn: a], [eqn: b], [eqn: c]의 순서쌍 [eqn: (a,```b,```c)]의 개수가 [eqn: `_3 {rmH}_n-3]임을 보여라. [중복조합과 부정방정식] .
008. 두 집합 [eqn: X=left{1,```2,```3,```cdots,```r right}], [eqn: Y=left{1,```2,```3,```cdots,```n right}]에 대하여 조건 ‘[eqn: x_1 <x_2]이면 [eqn: f(x _{1} ) le f(x _{2} )]이다.’ 를 만족시키는 함수 [eqn: f:X -> Y]의 개수는 [eqn: ` _{n} {rmH} _{r}]임을 보여라. 공역 [eqn: n]개 중에서 중복을 허용하여 [eqn: r]개를 선택하자. 선택된 경우마다 조건을 만족하며 대응을 연결하는 방법은 유일하다. [중복조합과 함수의 개수] .

	APODEIXIS [경우의 수]

009. 다음이 성립함을 설명하여라. (1) [eqn: (a+b) ^{n}]의 전개식에서 [eqn: a^k b^n-k]의 계수는 [eqn: n]개의 서로 다른 괄호 중 [eqn: a]가 선택되는 [eqn: k]개의 괄호를 선택하는 경우의 수 [eqn: `_n {rmC}_k]이다. (2) (1)에 [eqn: a=x], [eqn: b=1] 대입 (1) [eqn: (a+b) ^{n} = sum _{k=0} ^{n} ` _{n} rm C it rm _{k} `a ^{k} `b ^{n-k}] (2) [eqn: (1+x) ^{n} = sum _{k=0} ^{n} ` _{n} rm C it rm _{k} `x ^{k}] [이항정리] .
010. 다음이 성립함을 증명하여라. (1) [eqn: ` _{n} rm C it rm _{0} = _{n} rm C it rm _{n} = {n!} over {0!n!} =1] (2) [eqn: ` _{n} rm C it rm _{k} = _{n} rm C it rm _{n-k} = {n!} over {r!(n-k)!}] (3) [eqn: ` _{n} rm C it rm _{k} + _{n} rm C it rm _{k+1} = {n!} over {k!(n-k)!} + {n!} over {(k+1)!(n-k-1)!}# ````````````````````````````````````````````````````= {n!} over {k!(n-k-1)!} LEFT ( {1} over {k+1} + {1} over {n-k} RIGHT ) = {n!} over {k!(n-k-1)!} TIMES {n+1} over {(k+1)(n-k)} = {(n+1)!} over {(k+1)!(n-k)!}] (4) [eqn: (1+x)^n =sum_k=0 ^n `_n {rmC}_k x^k]에 [eqn: x=1]을 대입한다. (5) [eqn: (1+x)^n =sum_k=0 ^n `_n {rmC}_k x^k]에 [eqn: x=-1]을 대입한다. (6) (2)를 반복한다. (1) [eqn: `_n {rmC}_0 =_n {rmC}_n =1] (2) [eqn: ` _{n} rm C it rm _{k} = _{n} rm C it rm _{n-k}] (3) [eqn: ` _{n} rm C it rm _{k} + _{n} rm C it rm _{k+1} =` _{n+1} rm C it rm _{k+1}] (4) [eqn: ` _{n} rm C it rm _{0} + _{n} rm C it rm _{1} + _{n} {rm C} _{2} + CDOTS + _{n} {rm C} _{n} =2 ^{n}] (5) [eqn: ` _{n} rm C it rm _{0} + _{n} rm C it rm _{2} + _{n} rm C it rm _{4} + CDOTS = _{n} rm C it rm _{1} + _{n} rm C it rm _{3} + _{n} rm C it rm _{5} + CDOTS =2 ^{n-1}] (6) [eqn: ` _{n-k} rm C it rm _{0} + _{n-k+1} rm C it rm _{1} + _{n-k+2} rm C it rm _{2} + CDOTS + _{n} rm C it rm _{k} = _{n+1} rm C it rm _{k}] [이항계수의 성질] .

	APODEIXIS [경우의 수]

011. [eqn: k LEQ n]인 임의의 두 자연수 [eqn: n]과 [eqn: k]에 대하여 [eqn: k times_{n} rm C it rm _{k} =n times _{n-1} rm C it rm _{k-1}] 이 성립함을 증명하여라. 증명1) [eqn: ` _{n} rm C it rm _{k} = {n!} over {k!(n-k)!} = {n} over {k} TIMES {(n-1)!} over {(k-1)!(n-k)!} = {n} over {k} times` _{n-1} rm C it rm _{k-1}] 증명2) [eqn: k times_{n} rm C it rm _{k}]은 [eqn: n]명 중 [eqn: k]명을 선택하고 선택한 집단의 대표를 정하는 경우의 수이다. [eqn: n]명 중 대표를 먼저 뽑고 나머지를 선택하는 경우의 수로 생각하면 [eqn: n times_{n-1} rm C it rm _{k-1}]이다. [이항계수의 성질2] .
012. 다음을 증명하여라. (1) 풀이1) [eqn: (1+x)^n =sum_k=0 ^n `_n {rmC}_k x^k]의 양변을 미분한 후 [eqn: x=1]을 대입한다. 풀이2) [eqn: sum _{k=0} ^{n} k` _{n} rm C it rm _{k} = sum _{k=1} ^{n} k` _{n} rm C it rm _{k} = sum _{k=1} ^{n} n` _{n-1} rm C it rm _{k-1} =n sum _{k=1} ^{n} ` _{n-1} rm C it rm _{k-1} =n CDOT 2 ^{n-1}] (2) [eqn: (1+x)^n =sum_k=0 ^n `_n {rmC}_k x^k]의 양변을 닫힌 구간 [eqn: [0,```1]]에서 정적분한다. (3) [eqn: k(k-1)` _{n} rm C it rm _{k} =n(n-1)` _{n-2} rm C it rm _{k-2}]를 이용해서 [eqn: sum _{k=0} ^{n} k(k-1) _{n} rm C it rm _{k} = sum _{k=2} ^{n} k(k-1) _{n} rm C it rm _{k} =n(n-1) sum _{k=2} ^{n} ` _{n-2} rm C it rm _{k-2} =n(n-1)2 ^{n-2}] [eqn: sum _{k=0} ^{n} k ^{2} ` _{n} rm C it rm _{k} - sum _{k=0} ^{n} k` _{n} rm C it rm _{k} =n(n-1)2 ^{n-2}]에서 [eqn: sum _{k=1} ^{n} k _{n} rm C it rm _{k}=n cdot2^n-1]이므로 [eqn: sum _{k=0} ^{n} k ^{2} ` _{n} rm C it rm _{k} =n(n+1)2 ^{n-2}]이다. (1) [eqn: sum _{k=0} ^{n} k` _{n} rm C it rm _{k} =n cdot2^n-1] (2) [eqn: sum _{k=0} ^{n} {` _{n} rm C it rm _{k}} over {k+1} = {2 ^{n+1} -1} over {n+1}] (3) [eqn: sum _{k=0} ^{n} k ^{2} ` _{n} rm C it rm _{k} =n(n+1)2 ^{n-2}] [이항계수의 성질3] .