원판에 색칠하기

예제
그림과 같이 6개의 영역으로 나누어진 원을 A,B,C,D,E,F의 6가지 색을 사용하여 칠하려고 한다. 같은 색을 중복하여 사용해도 좋으나 이웃한 영역은 서로 다른 색으로 칠하는 방법의 수를 구하라. (단, 각 영역에는 한 가지 색만 칠하고, 가운데 원을 제외한 나머지 5개의 영역은 모두 합동이다)

풀이

1. 6가지 색을 다 사용하는 경우
   중앙에 들어갈 수 있는 색 6가지, 그 외는 5색이 원순열
   $$6 \times (5-1)!$$
2. 5가지 색을 사용하는 경우
   
   • 중앙에 들어갈 수 있는 색 6가지
   • 5가지 색 중에서 4가지색 선택:$\mathrm{_5C_4}$
   • 그 외에는 1가지 색을 2번쓰고: $\mathrm{_4C_1 = 4}$
   • 나머지 배열: $3!$
     $$6 \times \mathrm{_5C_4} \times4 \times3!$$
3. 4가지 색을 사용하는 경우
   
   • 중앙에 들어갈 수 있는 색 6가지
   • 5가지 색 중 3가지 선택: $\mathrm{_5C_3}$
   • 3가지 색 중 1번 쓸 색 선택: 3가지
   • 배열 2가지
     $$6 \times \mathrm{_5C_3} \times3 \times2$$
4. 총경우의 수는 = $1+2+3$