w****o
发帖数: 2260 | 1 在这个链接中，有如下的题的描述和解答，感觉不太对。或者是我没有理解。
http://baike.baidu.com/view/3783120.htm
“
十本不同的书放在书架上。现重新摆放，使每本书都不在原来放的位置。有几种摆法？
当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用M(n)表示,
那么M(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.
第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;
第二步,放编号为k的元素,这时有两种情况.
1,把它放到位置n,那么,对于剩下的n-2个元素,就有M(n-2)种方法;
2,不把它放到位置n,这时,对于这n-1个元素,有M(n-1)种方法;
综上得到 M(n)=(n-1)[M(n-2)+M(n-1)]
”
-----------------------------------------------
我的不理解的地方是第二步的 case 2,这时编号为k的元素不放在位置n, 我觉得这种情
况下的摆法不是
M(n-1),因为我觉得，编号为k的元素可以放在别的元素的位置，可是别的元素不能放在
位置k,因为k已经被元素n给占了，另外别的元素可以占位置n,感觉这里根本不是除元素
n外的剩余(n-1)个元素之间的互换位置，所以不是 M(n-1).
谁能帮我给解释一下？谢谢！ | z**x
发帖数: 16 | 2 我觉得还是在理解M（n）吧
M（n-1）的定义就是这（n-1）个元素不在和自己编号相同的位置的方法数；而case2正
好对应这种情况
感觉你的疑惑是因为又多考虑了在M（n-1）中的情况，想复杂了 | h****e
发帖数: 928 | 3 用一个实例解释就清楚了：
假设1, 2, 3, 4，现在1放到了4的位置。在Case 2，4不能放在
原来1的位置上，题目就变成了如下的放置问题：
4 2 3
(1) 2 3
你可以认为现在4的本位是1，在放置的时候要避开，这就成了
M(N-1)的情况了。
顺便问一下，有简单的组合数学书推荐吗？只要能够应付一般
码工面试就可以了。 | I*******l
发帖数: 203 | 4 It seems that for the second case, several steps are skipped there.
Let P be any permutation such that case 2 holds. Let us consider the action
of P on element 1. The second case is P(1)=2 and P(2)!=1. Suppose P(2)=k,
then k>=3. Also let P(i)=1. Then we can define another permutation P' on {2,
3,..,n} such that P'(j)=P(j) for all j!=i and P'(i)=2. One can check that P'
is a derangement for {2,3,..,n}. In other words, when the second case
happens, there is a one-to-one correspondence between the derangement of the
set {1,2,...,n} and the derangement of the set {2,3,...,n}. | p*********g
发帖数: 5964 | 5 用inclusion-exclusion公式，
【在 w****o 的大作中提到】
: 在这个链接中，有如下的题的描述和解答，感觉不太对。或者是我没有理解。
: http://baike.baidu.com/view/3783120.htm
: “
: 十本不同的书放在书架上。现重新摆放，使每本书都不在原来放的位置。有几种摆法？
: 当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用M(n)表示,
: 那么M(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.
: 第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;
: 第二步,放编号为k的元素,这时有两种情况.
: 1,把它放到位置n,那么,对于剩下的n-2个元素,就有M(n-2)种方法;
: 2,不把它放到位置n,这时,对于这n-1个元素,有M(n-1)种方法;
| s*******d
发帖数: 82 | 6 right, check derangement
【在 p*********g 的大作中提到】
: 用inclusion-exclusion公式，
|
|
