[SW Expert Academy][Computational Thinking] 집합과 조합론

링크

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPCwCKAAPw5UW6&subjectId=AV1lG0SaAAgCFAb_

문제 1

분수로 식을 바꾸면, $\frac{n!}{k!(n-k)!}$+$\frac{n!}{(k-1)!(n-k-1)!}$ = $\frac{(n+1)!}{k!(n+1-k)!}$ 이다. 좌변을 변경하면 $\frac{n!(n-k+1)}{k!(n-k+1)!}$ + $\frac{kn!}{k!(n-k+1)}$ = $\frac{n!(n+1)}{k!(n-k+1)}$ = $\frac{(n+1)!}{k!(n-k+1)}$ 이므로 우변과 같아진다.

문제 2

${n=1}$일 때, ${(x+y)^{n}}=\sum_{k=1}^{n}\binom{n}{k}x^{n-k}y^k$는 $(x+y)=\binom{1}{0}x+\binom{1}{1}y=x+y$이므로 양변이 같다.
${n=m}$일 때, $(x+y)^{m}=\sum_{k=0}^{m}\binom{m}{k}x^{m-k}y^k=\binom{m}{0}x^my^0+\binom{m}{1}x^{m-1}y+...+\binom{m}{m}x^0y^m$
${n=m+1}$일 때, $(x+y)^{m+1}=\sum_{k=0}^{m+1}\binom{m+1}{k}x^{m+1-k}y^k$이다.
이 때, ${n=m}$인 상태에서 양변에 $(x+y)$를 곱하면
$(x+y)^{m+1}=x^m(x+y)+mx^{m-1}y(x+y)+...+y^m(x+y) = x^{m+1}+x^my+mx^my+mx^{m-1}y^2+...+xy^m+y^{m+1} = x^{m+1}+(m+1)x^{m}y+...+(m+1)xy^m+y^{m+1}$이므로 n=m+1일 때와 양변이 같아지기 때문에 성립한다.

문제 3

문제 2에서 증명된 공식을 사용하면 $x=1, y=1$이면 $2^n=\binom{n}{0}+\binom{n}{1}+...+\binom{n}{n}$이므로 n개의 원소의 집합에서 각 갯수별로 고르는 가짓수의 합과 $2^n$가 같기 때문에 증명된다.

문제 4

귀류법을 사용하기 위해 $(A-B)\cap(B-A)\ne\emptyset$이라면,
$(A-B)\cap(B-A)=(A\cap{B^c})\cap(B\cap{A^c})=(A\cap{A^c})\cap(B\cap{B^c})=\emptyset$이므로 모순되기 때문에 증명된다.

문제 5

어떤 원소 $x$에 대해서 $x\in{A}$이고 $x\notin{B}$이면 원소가 $A$에만 존재하는 것이고 $x\in{B}$이고 $x\notin{A}$이면 원소가 $B$에만 존재한다. 이러한 경우, 서로의 교점이 없어 각 값은 서로소이므로 '두 집합이 다르다'는 뜻과 같다.

문제 6

$(A-B)\cup(B-A)=(A\cap{B^c})\cup(B\cap{A^c})=(A\cap{B^c})\cup(B\cap{A^c})\cup{\emptyset}=(A\cap{B^c})\cup(B\cap{A^c})\cup{(A\cap{A^c})\cup({B\cap{B^c}})}=\{A^c\cap(A\cup{B})\}\cup\{B^c\cap(A\cup{B}\}=(A\cup{B})\cap(A^c\cup{B^c})=(A\cup{B})\cap(A\cap{B})^c$

문제 7

$(A\oplus{B})\oplus{B}=\{(A\cup{B})-(A\cap{B})\}\oplus{B}=\{(A\cup{B})\cap(A\cap{B})^c\}\oplus{B}=\{\{(A\cup{B})-(A\cap{B})\}\cup{B}\}-\{\{(A\cup{B})-(A\cap{B})\}\cap{B}\}=\{\{(A\cup{B})\cap(A\cap{B})^c\}\cup{B}\}-\{\{(A\cup{B})\cap(A\cap{B})^c\}\cap{B}\}=\{\{(A\cup{B})\cap(A^c\cup{B^c})\}\cup{B}\}-\{\{(A\cup{B})\cap(A^c\cup{B^c})\}\cap{B}\}=\{(A\cup{B})\cap{U}\}-\{(A\cup{B})-A\}=A$

문제 8

8x8칸의 체스판에 동일한 말 2개를 놓는 경우의 수이므로 $\binom{64}{2}$와 같다.

문제 9

어떤 집합 A에 대해서 각 원소가 $a_1, a_2,...,a_n$이라고 할 때, 어떤 원소 $a_k$에 대해서 포함하는 경우와 포함하지 않는 경우가 2가지이므로 n개의 원소에 대해서 $2^n$가지 이다.

문제 10

0부터 9까지의 10개 숫자의 4~6자리 비밀번호이므로 순서를 고려해야하고 4자리, 5자리, 6자리의 경우를 각각 고려해야하므로 10개의 숫자에서 각 자리수의 숫자를 뽑는 순열이라고 볼 수 있다. 그러므로 가짓수는 $_{10}P_{4}+_{10}P_{5}+_{10}P_{6}$이다.

문제 11

단사함수 : 함수의 각 출력 값에 대해 유일한 입력 값이 대응되는 함수

n개의 수에 대해서 m개로 이어지는 단사함수이므로 서로다른 n개의 수에서 순서와 관련있게 m개를 선택하는 순열과 같다. 그렇게 때문에 경우의 수는 $_{n}P_{m}$으로 표현할 수 있다.

문제 12

서로 다른 52장의 카드에서 순서 상관없이 5개의 카드로 이루어진 조합의 갯수를 구하기 때문에 $_{52}C_{5}$으로 표현할 수 있다.

문제 13

서로 다른 52장의 카드에서 4가지의 서로 다른 무늬가 있으므로 한 가지의 무늬에는 13장의 카드씩 있다. 그렇기 때문에 13장에서 3장을 뽑고 나머지 카드에서 2장을 뽑는 경우가 무늬마다 4가지씩 있다. 그러므로 $_{13}C_{3}\times_{39}C_{2}\times4$이다.

문제 14

자연수에서 $a+b+c=100$이 되어야 하므로 3가지의 수를 선택하는 조합이지만, 1이상이 되어야하므로 $a'=a+1, b'=b+1, c'=c+1$로 표현할 수 있다. 그렇기 때문에 식을 수정하면 $a'+b'+c'=97$이기 때문에 서로 다른 97개의 공을 3개의 같은 상자에 담는 중복조합과 같은 문제이므로 $_{3}H_{97}=_{97+3-1}C_{3-1}=_{99}C_{2}$와 같다.

문제 15

전사함수 : 함수의 치역이 목표 집합 전체와 일치하는 함수입니다. 즉, 목표 집합의 모든 원소가 함수의 값으로 나타나는 경우

포함-배제 원리 : 계산할 때 포함되는 부분에 겹치는 부분을 올바르게 계산하기 위한 원리

전사함수이기 때문에 $A=\{a_1,a_2,a_3,a_4,a_5\}, B=\{b_1,b_2,b_3\}$라고 하면 $A$의 원소가 $B$의 원소를 하나씩은 선택해야한다. 그렇기에 전체 가지수는 $A$에서 $B$가 선택되는 경우가 원소당 3가지씩 되므로 $3^5$가지이다. 이때, 포함-배제 원리에 의해서 (1)한 개의 원소가 포함이 되지 않는 경우를 전체에서 빼고 (2)두 개의 원소가 포함되지 않는 경우가 (1)의 경우에 2번 중복 되기 때문에 한번 빼면 된다. 한 개의 원소가 포함이 되지 않는 경우는 $B$에서 포함되지 않을 원소 하나를 고르고 나머지 2개의 원소에서 5개의 원소가 선택하는 경우이므로 $_{3}C_{1}\times{2^5}$이고 두 개의 원소가 포함되지 않는 경우는 $B$에서 포함되지 않을 원소 두개를 고르고 나머지 1개의 원소에서 5개의 원소가 선택하는 경우이므로 $_{3}C_{2}\times{1^5}$이다. 그렇기에 가짓수를 계산하면 $3^5-_{3}C_{1}\times{2^5}+_{3}C_{2}\times{1^5}$이다.

문제 16

5개의 다른 숫자를 13가지의 숫자 중에서 선택하는 경우는 $_{13}C_{5}$이다. 또한 각 5개의 숫자가 적힌 카드에 그림을 선택시키는 경우는 각 카드당 4가지씩이므로 $4^5$이다. 그렇기 때문에 전체 가짓수는 $_{13}C_{5}\times{4^5}$이다.

문제 17

전체 구간이 n개라고 할 때, 원소의 개수가 하나이면서 연속되는 구간은 n개이다. 이렇게 하나의 원소가 늘어날 때마다 연속되는 구간의 개수는 1개씩 줄어든다. 괄과적으로 n개의 원소가 연속하는 구간의 개수는 1개이기 때문에 전체 갯수는 $n+(n-1)+(n-2)+...+1$이 된다. 그렇기에 이를 수식으로 표현하면 $\frac{n(n+1)}{2}$이다.