D_n 은 함수 f: {1,2,3,...n} -> {1,2,3,...,n}

중 모든 x에 대해 f(x)=x 를 만족하지 않는 함수의 총 개수임.


그럼 D(n,k) 를

f:{1,2,3,...,k} ->{1,2,3,...,n}

중 f(x)=x 를 만족하지 않는 함수의 개수로 정의하는것이 자연스러울 것.


D_n = (n-1) (D_(n-1) + D_(n-2)) 임이 알려져있음. 즉, k=n인 경우는 쉬움.


난 k<n 인 경우 n을 고정한 점화식과, k를 고정한 n에 대한 점화식을 구하고싶음.

가능하다면 n,k모두를 아우르는 점화식도 만들고싶음.


일단 생각이 나서 끄적이는중임. 여기 굇분들은 나보다 더 잘할테니 혹시 재밌을거같은분은 풀고 댓글에 써주셈

나도 비천한 머리 굴려서 푸는대로 올려봄