错排公式的推导 学习笔记【递推】【组合数学】

点击量：253

   错排问题，就是把书架上的n本书，重新摆放（也叫重排）生成一个新的排列，每一本书都不在它原来的位置上，问有几种方案。

   我们通过排列，联想到组合数学问题，因此我们试着把它分解成子问题，当其中两个数发生重排关系时，剩下的怎么办。

   我们假设原来的数列是 1,2,3,4,…,n，现在假设一个k∈[1,n)，把n放到k的位置去，那么现在的数列是1,2,3,4,…,n,…,/。此时n的位置空出来了，轮到k选择。一共可分两种情况：一是k也到n的位置上去，那么此时把k和n消掉（因为它们位置已经根据条件限制定下来了），转移的状态数是D[n-2]（设第n个数的错排公式是D[n]）。二是k不到n的位置上去，我们也可以把k和n消掉，只不过把n当成是k，只能消掉一组。为什么呢？既然k不到n的位置，而n已经占了k的位置，那么我们把n占k消掉。此时k也不能到n的位置而其他元素可以到n的位置，仍然满足错排问题，那么这时的状态就是D[n-1]。而每次k有n-1种选择，那么我们的递推公式就是D[i]=(i-1)×(D[i-1]+D[i-2])。

    初始化D[1]=0,D[2]=1.

   这种思想其实是一种递推，只不过不容易看出。我们在实际运用中要灵活把问题分解成小问题，熟练运用“数学归纳法”，就可以试着写出递推公式了。