경우의 수_원순열_난이도 상

아래 그림과 같은 $7$ 개의 영역을 서로 다른 네 가지 색을 일부 또는 전부를 사용하여 색칠하는 경우의 수를 구하시오.

(단, 이웃하는 영역은 서로 다른 색을 칠해야 하고, 회전하여 일치하는 것은 같은 것으로 본다.)

정답 $56$

색을 세 가지만 사용하는 경우

4개의 색 중 3개를 선택하는 경우의 수는 ${}_4{\rm C}_3$, 다시 3개의 색 중 가운데 영역을 칠할 색을 선택하는 경우의 수는 $_3{\rm C}_1$ 이 됩니다. 만약 4개의 색 중 $A, \; B, \; C$ 3개의 색이 선택되고, 가운데 영역을 칠할 색으로 $A$가 선택되었다고 하면 영역을 모두 칠하는 방법은 아래 그림 처럼 한 가지 밖에 없습니다.

$\therefore {}_4 {\rm C}_3 \times 3 =12$

네 가지 색을 모두 사용하는 경우

가운데 영역을 칠할 색을 선택하는 경우의 수는 ${}_4{\rm C}_1$ 

만약 가운데 영역을 칠할 색으로 $A$ 가 선택되었다고 하면 바깥쪽 영역을 $B, \; C, \; D$ 세 가지 색으로 칠해야 합니다. 이때, 이 세 가지 색을 모두 2번씩 사용하여 칠하는 방법은 아래의 그림처럼 다섯 가지가 존재합니다. (B를 기준으로 B가 두 칸 떨어져 있는 경우와, 한 칸 떨어져 있는 경우로 나누어 생각하면 쉽습니다.)

또한 $B, \;C, \;D$ 중 $B$ 를 1번만 사용하고 나머지를 2번, 3번 사용하여 칠하는 방법은 아래 그림처럼 두 가지가 존재합니다. 

이 경우 $B, \; C, \; D$ 중 1번만 사용할 색을 선택하는 경우의 수는 ${}_3{\rm C}_1$ 

결국 네 가지 색을 모두 사용하여 칠하는 경우의 수는 

$\therefore {}_4{\rm C}_1 \times \{ 5 + ({}_3{\rm C}_1 \times 2)\} = 44$

위 두 가지 경우의 수를 더하면 $12+44=56$ 이 됩니다.