답은 [a_1,a_2,...,a_n]의 배열로 나옵니다.

이 배열을 list라고 해주자고요.

여기서 n,k 그리고 n이하의 자연수인 e에 대한 함수를 하나 정의합시다

f(n,k,e) = list의 1번째 요소부터 e-1 번째 요소를 제외한 n이하의 자연 수 중 list[e]의 오름차순 순서

(단, f(n,k,1) = list[e])

물론 f(n,k,n) = 1이겠지요?

이렇게 정의해주면

k = (n-1)!*(f(n,k,1)-1)+(n-2)!*(f(n,k,2)-1)+...+1!(f(n,k,n-1)-1)+f(n,k,n)

k-1 = (n-1)!*(f(n,k,1)-1)+(n-2)!*(f(n,k,2)-1)+...+1!(f(n,k,n-1)-1)

여기까지 정리하고 일단 글쓴분의 아이디어는

1. k-1을 (n-1)!을 나누면 그 정수몫이 f(n,k,1)-1이니 f(n,k,1) 을 구하고

2. 과정 1의 나머지를 (n-2)!으로 나누면 그 정수몫이 f(n,k,2)-1이니 f(n,k,2) 을 구하고

...

이런식입니다.

이는 각 과정의 정수몫이 f(n,k,r)-1 꼴로 나오는 것을 가정한 방식이지요.

이 가정에 대한 증명을 해보았습니다.

k-1 = (n-1)!*(f(n,k,1)-1)+(n-2)!*(f(n,k,2)-1)+...+1!(f(n,k,n-1)-1)

(k-1)/(n-1)! = f(n,k,1)-1 + [(f(n,k,2)-1)/(n-1)+(f(n,k,3)-1)/{(n-1)(n-2)}+...+(f(n,k,n-1)-1)/{(n-1)(n-2)...2}]

(f(n,k,2)-1)/(n-1)+(f(n,k,3)-1)/{(n-1)(n-2)}+...+(f(n,k,n-1)-1)/{(n-1)(n-2)...2} 

<= (n-2)/(n-1)+(n-3)/{(n-1)(n-2)}+...+2/{(n-1)(n-2)...3+1/{(n-1)(n-2)...3*2} 

< (n-2)/(n-1)+(n-3)/{(n-1)(n-2)}+...+2/{(n-1)(n-2)...3+2/{(n-1)(n-2)...3*2}         (마지막 항의 1을 2로 올려줍시다)

= (n-2)/(n-1)+(n-3)/{(n-1)(n-2)}+...+2/{(n-1)(n-2)...3+1/{(n-1)(n-2)...3}

= (n-2)/(n-1)+(n-3)/{(n-1)(n-2)}+...+3/{(n-1)(n-2)...3

....

= (n-2)/(n-1)+(n-2)/{(n-1)(n-2)} = 1

따라서 k-1을 (n-1)!으로 나누면 정수몫이 f(n,k,1)-1가 나오게 되지요.

그 나머지인 (n-2)!*(f(n,k,2)-1)+...+1!(f(n,k,n-1)-1)에 대해서 같은 방식으로 그 정수몫이 f(n,k,2)-1임을 알 수 있고요.

암튼 그렇다고요...

심심해서 해봤어요...