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

作者: wjyyy 分类: 学习笔记,数学,组合数学,递推 发布时间: 2018-06-25 19:35

点击量:25

 

   错排问题,就是把书架上的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.

 

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

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 【错排公式推导】 […]

/* */