排序的交换问题

对一组序列排序的过程，就是通过对其中的元素两两交换实现的。这种交换次数被证明在最优的情况下是O(nlgn)，n是序列的长度。现在假设有一组排列{a1,a2,...,aN}，元素来自{1,2,...,N}。这组序列要实现从小到大的排序所需要的最小的交换次数记为K。现在问，给定N，K。满足这种性质的排列有多少个。

假设满足长度为N，最小交换次数为K的序列的数目为F(N,K)
我们可以得到如下的递归公式:
F(N,K) = (N-1)F(N-1,K-1) + F(n-1,K)

这样就可以用动态规划的算法求F(N,K)