양의 정수 $k$와 $n$에 대해, 원 위에 $kn$개의 서로 다른 점 $P_1$, $P_2$, $\ldots$, $P_{kn}$이 시계방향으로 배열되어 있다. 각 점에 $k$개의 색 $c_1$, $c_2$, $\ldots$, $c_k$ 중 하나를 칠할 때, 다음 조건을 모두 만족시키도록 칠하는 방법의 수를 구하여라.

(1) 각각의 색으로 칠할 점의 개수는 $n$이다.
(2) 임의의 $i\neq j$에 대하여, 점 $P_a$와 $P_b$에 $c_i$를 칠하고 점 $P_c$와 $P_d$에 $c_j$를 칠한다면 선분 $P_aP_b$와 $P_cP_d$는 서로 만나지 않는다.

(2011년 8월 21일)