保 险 箱 和 钥 匙

乱弹

能开的情况是最多有三个轮换，并且每个轮换里都有一个被抓出来。这样是能直接计算出来的。可惜我对这些组合关系不熟悉，要做的话，又要查书，几乎每步都要仔细验证，非一时半会可以做好。www.ddhw.com   也许野菜花有简单办法吧。www.ddhw.com   不管怎样，这题目实在有意思。 www.ddhw.com

乱弹

Let q(n,k) be the probability that not all safes can be opened, i.e., q(n,k)=1-p(n,k). Then in the total C(n,k) n! combinations, there are C(n,k) n!q(n,k) combinations that not all safes can be opened.  For  1<=i <=n-k, there are  C(n,i)i!(1-q(n-i, k))C(n-i, k) (n-i)! cases in which exactly i safes can not be opened (these i safes form some cycles...).   Therefore, we have:       C(n,k) n!q(n,k)=C(n,1)1!(1-q(n-1, k))C(n-1, k)(n-1)!+....+C(n, n-k)(1-q(k,k))C(k,k)k!.     Now we are left to prove by induction on n-k that q(n,k)=1-k/n, which can be done easily. www.ddhw.com

乱弹

C(n,k) n!q(n,k)=C(n,1)1!(1-q(n-1, k))C(n-1, k)(n-1)!+....+C(n, n-k)(n-k)!(1-q(k,k))C(k,k)k!.   I did use 置换群, but not much. www.ddhw.com

乱弹

To save yourself from double induction, you can try it on n+k. Anyway, it is not important. www.ddhw.com