대회때 못풀었던 문제를 다시 보고 있는데, 점화식이 해결되지 않아서 물어보게 되었습니다.

크기 N의 cycle을 발견했을 때 이걸 최소횟수로 제자리에 돌려놓는 방법의 가짓수를 S(N)이라고 정의할게요.

처음에 생각할 때에는 cycle에 속한 숫자 중 하나를 무조건 제 자리에 갖다놓아야만 최소 횟수로 정렬할 수 있을 것 같아서 S(N) = N * S(N-1) = N! 으로 시도했었는데 틀리더라구요.

근데 나중에 생각해보니 같은 cycle에 속한 숫자들끼리라면 아무거나 바꿔도 최소 횟수를 달성할 수 있게 되더라구요. 다만 이렇게 하면 cycle이 두개로 쪼개지는 셈이 되어서 아래와 같이 점화식을 구성하게 되는데...

읭? 푼 사람의 코드를 보니 이 식이 N^(N-2)이랍니다. 실제로 값을 계산해 봐도 맞긴 한데 이게 어떻게 구해지는건지 잘 모르겠더군요 ㅠㅠ 학부때 group theory를 안배워서 그런가 ㅠㅠ 여튼 이 식의 유도를 도와주시면 감사하겠습니다.