$1,2,\ldots ,n$($n \ge 3$)의 번호가 적혀있는 작은 공들이 있다. 아래 서술한 색칠 방법을 써서 각각의 공을 빨강, 노랑, 파랑, 보라 네 가지 중의 하나를 칠한다: 먼저 $n$개의 공을 원 주 위에 임의로 배열한다. 시계방향 순서대로 임의의 연속 3개의 공에 대하여 그 번호가 $i$, $j$, $k$라 하자.
(1) 만일 $i \gt j \gt k$이면 $j$번 공에 빨강을 칠한다.
(2) 만일 $i \lt j \lt k$이면 $j$번 공에 노랑을 칠한다.
(3) 만일 $i \lt j$, $k \lt j$이면 $j$번 공에 파랑을 칠한다.
(4) 만일 $i \gt j$, $k \gt j$이면 $j$번 공에 보라를 칠한다.
$n$개의 공의 두 가지 염색방법이 다르다 함은 적어도 하나의 공이 두 가지 염색방법에서 다른 색을 가진다는 뜻이다. 서로 다른 색칠 방법의 수를 구하여라.
(2013년 3월 13일, 출처, 4시간 30분)