자연계열 (오후) 1번

(가) 주어진 대상 중에서 여러 가지 정해진 조건을 동시에 만족하지 않는 원소의 개수를 구해보자. 만약 주어진 조건들을 만족하는 것들의 개수를 쉽게 구할 수 있는 경우라면 이를 이용하여 원하는 결과를 얻을 수 있다. 예를 들어 1부터 $\displaystyle 10^4$까지의 자연수 중 4의 배수도 6의 배수도 아닌 것의 개수를 구하는 일을 생각해보자, 4의 배수이고 동시에 6의 배수인 것의 개수를 구하는 일은 어렵지 않으나, 4의 배수도 아니고 6의 배수도 아닌 것의 개수를 구하는 일은 조금 더 어려워 보인다. 이런 문제를 해결하는 좋은 방법으로 잘 알려진 다음 정리가 있다. 유한집합 $\displaystyle S$에 대하여 $\displaystyle n(S)$는 집합 $\displaystyle S$의 원소의 개수를 나타낸다고 하자.

정리 1. 유한집합 $\displaystyle U$와 $\displaystyle U$에서의 두 조건 $\displaystyle p_1,p_2$가 주어졌다고 하자. 조건 $\displaystyle p_1,p_2$의 진리집합을 각각 $\displaystyle A_1,A_2$, 그리고 $\displaystyle N_1=n(A_1)+n(A_2)$, $\displaystyle N_2=n(A_1\cap A_2)$라고 하면 다음이 성립한다: $\displaystyle n(A_1^c\cap A_2^c)=n(U)-N_1+N_2$이는 $\displaystyle n(A_1^c\cap A_2^c)=n(U-(A_1\cup A_2))=n(U)-n(A_1\cup A_2)$와 $\displaystyle n(A_1\cup A_2)=n(A_1)+n(A_2)-n(A_1\cap A_2)$를 이용하여 쉽게 확인할 수 있다:$\displaystyle n(A_1^c\cap A_2^c)=n(U)-n(A_1)-n(A_2)+n(A_1\cap A_2)=n(U)-N_1+N_2$정리 1은 자연스럽게 여러 개의 조건을 가지는 일반적인 정리로 확장할 수 있으며 다음은 네 개의 조건이 주어진 경우이다.

정리 2. 유한집합 $\displaystyle U$와 $\displaystyle U$에서의 네 개의 조건 $\displaystyle p_1,p_2,p_3,p_4$가 주어졌다고 하자. 조건 $\displaystyle p_i,\ 1\le i\le4$, 의 진리집합을 $\displaystyle A_i$라고 할 때, $\displaystyle k=1,2,3,4$에 대하여 $\displaystyle N_k$를 가능한 모든 $\displaystyle k$개의 서로 다른 $\displaystyle A_i$들의 모임에 대해 그들의 교집합의 원소의 개수를 더한 값이라 정의하면 다음이 성립한다:$\displaystyle n(A_1^c\cap A_2^c\cap A_3^c\cap A_4^c)=n(U)-N_1+N_2-N_3+N_4$정리 2에서 조건 $\displaystyle p_4$를 ‘$\displaystyle x\ne x$’라고 하면 $\displaystyle A_4=\varnothing$, $\displaystyle A_4^c=U$이고 따라서 $\displaystyle N_4=0$이며 조건이 세 개인 정리를 얻을 수 있다.

예제 1. 집합 $\displaystyle A=\{a,b,c,d\}$에서 집합 $\displaystyle B=\{1,2,3\}$로의 전사함수(공역과 치역이 같은 함수)의 개수를 구해보자. 전체집합 $\displaystyle U$를 $\displaystyle A$에서 $\displaystyle B$로의 모든 함수의 집합이라 하자. $\displaystyle i=1,2,3$에 대하여 $\displaystyle U$에서의 조건 $\displaystyle p_i$를 ‘$\displaystyle i$가 함수 $\displaystyle f\in U$의 치역의 원소가 아니다’라고하면 조건 $\displaystyle p_i$의 진리 집합 $\displaystyle A_i$는$\displaystyle \{f\in U\mid f\text{의 치역은 }B-\{i\}\text{의 부분집합}\}$이며 $\displaystyle A_i^c$는 $\displaystyle i$를 함수값으로 가지는 함수들의 집합이다. 따라서 $\displaystyle A_1^c\cap A_2^c\cap A_3^c$은 1, 2, 3을 모두 함수값으로 가지는 함수들의 집합, 즉 전사함수들의 집합이며 구하고자 하는 수는 $\displaystyle n(A_1^c\cap A_2^c\cap A_3^c)$이다. 이제 $\displaystyle n(U)=3^4$, $\displaystyle N_1=n(A_1)+n(A_2)+n(A_3)=3\cdot2^4$$\displaystyle N_2=n(A_1\cap A_2)+n(A_2\cap A_3)+n(A_3\cap A_1)=3$, $\displaystyle N_3=n(A_1\cap A_2\cap A_3)=0$이므로 정리 2에 의하여 $\displaystyle n(A_1^c\cap A_2^c\cap A_3^c)=n(U)-N_1+N_2-N_3=3^4-3\cdot2^4+3-0=36$이다.

(나) $\displaystyle n$이 자연수일 때, 가로로 $\displaystyle n$칸 세로로 $\displaystyle n$칸이 있는 체스판을 $\displaystyle B(n)$이라고 하자, (그림1)은 $\displaystyle B(5)$이다. 여러 가지 문제를 체스판 $\displaystyle B(n)$에 특정한 조건을 만족하도록 바둑돌들을 놓는 방법의 수를 구하는 문제로 바꾸어 생각할 수 있다.

각 행과 각 열에 하나의 돌만 있도록 $\displaystyle B(n)$에 $\displaystyle n$개의 돌들을 놓는 방법은 $\displaystyle \{1,2,\cdots,n\}$에서 $\displaystyle \{1,2,\cdots,n\}$으로의 일대일 대응으로 이해할 수 있다: $\displaystyle B(n)$의 $\displaystyle i$행에 놓여진 돌이 위치한 열의 번호를 $\displaystyle i$에 대응되는 수로 정하면 $\displaystyle \{1,2,\cdots,n\}$에서 $\displaystyle \{1,2,\cdots,n\}$으로의 일대일 대응을 얻을 수 있다. 예를 들어 (그림 2)의 방법은 1을 2로, 2를 4로, 3을 1로, 4를 3으로, 5를 5로 대응시키는, $\displaystyle \{1,2,3,4,5\}$에서 $\displaystyle \{1,2,3,4,5\}$으로의 일대일 대응으로 이해할 수 있다.각 행과 각 열에 한 개씩의 돌이 있도록 $\displaystyle B(n)$에 $\displaystyle n$개의 돌을 놓는 방법의 수를 계산해 보자. 돌을 1행에 놓을 수 있는 자리는 $\displaystyle n$개, 1행에 돌을 놓은 후 2행에 돌을 놓을 수 있는 자리는 $\displaystyle (n-1)$개, ... 이렇게 계산해 보면 $\displaystyle n\cdot(n-1)\cdot\cdots\cdot2\cdot1=n!$가지의 방법이 있음을 알 수 있다.