경우의 수_중복순열_난이도 상

집합 $\rm U=\{1, \; 2, \; 3, \; \cdots, \; 2017 \}$ 에 대하여 $\rm U$ 의 부분집합 $\rm A, \; B, \; C$ 의 관계가 아래 벤 다이어그램과 같다고 할 때, 부분집합 $\rm A, \; B, \; C$ 를 구성할 수 있는 방법의 수는? (단, $\rm A, \; B, \; C$ 는 모두 공집합이 아니다.)

① $3^{2016} - 2^{2017} +1$

② $3^{2017} - 2^{2017} +1$

③ $3^{2017} - 2^{2018} +1$

④ $3^{2018} - 2^{2017} +1$

⑤ $3^{2018} - 2^{2018} +1$

정답 ③

첫 번째 방법

먼저 전체 집합의 영역을 세 개로 나누자.

먼저 집합 $\rm A-C$ 가 나타내는 영역을 $a$ 라 하고, 집합 $\rm B$ 가 나타내는 영역을 $b$, 집합 $\rm C$ 가 나타내는 영역을 $c$ 라고 하자.  

$1$에서 $2017$까지의 자연수를 $a, \; b, \; c$ 각각에 나눠주는 방법의 수는 $3^{2017}$ 가지이다. 중요한 것은 이 $3^{2017}$ 가지에는 $(a, \; b)$, $( b, \; c)$, $(c, \; a)$ 의 두 군데로만 나누어 주는 방법의 수와 $a$ 혹은 $b$ 혹은 $c$ 의 한 군데로만 나누어 주는 방법의 수도 포함된다는 것이다.

따라서 $3^{2017}$ 에서 두 군데로만 나누어주는 경우의 수를 빼면 된다. 한 군데로만 나누어 주는 경우의 수를 따로 빼지 않는 것은 두 군데로만 나누어 주는 경우의 수에 한 군데로만 나누어 주는 경우의 수도 포함되기 때문이다.

 따라서 이제 $(a, \; b)$, $( b, \; c)$, $(c, \; a)$ 의 두 군데로만 나누어주는 경우의 수를 생각하면 되는데, 여기서 고려해야 할 사항이 또 있다. $a$ 에는 원소가 없다고 하더라도 $c$ 에 원소가 있다면 집합 $\rm A$ 는 공집합이 아니게 된다. $\rm C \subset A$ 이기 때문이다. 따라서 $(b, \; c)$ 로만 나누어 주는 경우의 수는 제외한다. $(a, \; b)$, $(c, \; a)$는 각각 $2^{2017}$ 가지이므로 전체는 $2 \times 2^{2017}$ 이 된다. 

 그런데 $(a, \; b)$ 에만 나눠주는 경우 $a$ 가 다 가져가는 경우와 $b$ 가 다 가져가는 경우도 포함이 된다. 또한 $(a, \; c)$ 에만 나눠주는 경우에도 $a$ 가 다 가져가는 경우와 $c$ 가 다 가져가는 경우가 포함된다. 즉 단순히 $3^{2017}$ 에서 $2\times 2^{2017}$ 을 빼주게 되면 $a$ 가 다 가져가는 경우가 두 번 빠지게 되는 결과를 초래한다. 

 결과적으로 $a$ 가 다 가져가는 경우의 수를 한 번 더해줘야 하는데, $a$ 가 다 가져가는 경우의 수는 한 가지 이므로 우리가 구하는 경우의 수는 $3^{2017}-2^{2018}+1$ 이 된다. 

두 번째 방법

먼저 집합 $\rm A$ 와 $\rm B$ 에 각각  $k$, $\;\;k-1$ 개 원소가 포함되게 나누는 방법은 $_{2017}{\rm C}_k\;\; (k=1, \; 2, \; \cdots, \; 2016)$ 이고, 이 상황에서 공집합이 아닌 집합 $C$ 를 결정하는 방법의 수는 $\sum \limits_{i=1}^{k} {}_k{\rm C}_i$ 이다. 따라서 구하는 경우의 수는 $\sum_{k=1}^{2016} \left \{ {}_{2017}{\rm C}_k \times \left ( \sum \limits_{i=1}^k {}_k{\rm C}_i \right ) \right \}$ 이때, $\sum \limits_{i=1}^k {}_k{\rm C}_i$ 는 이항계수의 성질에 의하여 $2^k -1$ 이므로 $\begin{aligned} \sum_{k=1}^{2016} \left \{ {}_{2017}{\rm C}_k \times \left ( \sum \limits_{i=1}^k {}_k{\rm C}_i \right ) \right \} &= \sum_{k=1}^{2016} \left \{ {}_{2017}{\rm C}_k \times \left ( 2^k -1 \right ) \right \} \\ &= \sum \limits_{k=1}^{2016} \left ({}_{2017}{\rm C}_k 2^k \right ) - \sum \limits_{k=1}^{2016} {}_{2017}{\rm C}_k \end{aligned}$

여기서 $(1+2)^{2017} = \sum \limits_{k=0}^{2017} \left ( {}_{2017}{\rm C}_k 2^k \right )$ 임을 이용하면 $\begin{aligned} \sum \limits_{k=1}^{2016} \left ( {}_{2017}{\rm C}_k 2^k \right ) &= 3^{2017} - \left ( 1 + 2^{2017} \right ) \\ &= 3^{2017} - 2^{2017} -1 \end{aligned}$ 또한 $\sum \limits_{k=1}^{2016} {}_{2017}{\rm C}_k = 2^{2017}-2$ 이므로 $\begin{aligned} \sum_{k=1}^{2016} \left \{ {}_{2017}{\rm C}_k \times \left ( \sum \limits_{i=1}^k {}_k{\rm C}_i \right ) \right \} &= \sum_{k=1}^{2016} \left \{ {}_{2017}{\rm C}_k \times \left ( 2^k -1 \right ) \right \} \\ &= \sum \limits_{k=1}^{2016} \left ({}_{2017}{\rm C}_k 2^k \right ) - \sum \limits_{k=1}^{2016} {}_{2017}{\rm C}_k \\ &= \left (3^{2017} - 2^{2017} -1 \right ) - \left (2^{2017} - 2 \right )  \\ &= 3^{2017} - 2 \times 2^{2017} +1 \\ &= 3^{2017} - 2^{2018} +1 \end{aligned}$