算法问题:n组对象配对,最终均不配对的结果总数是多少?

详细说明:

有n组已经一一配对的人,现在随机分组,重新一对一分配,求最终每个新分组都与之间不同(每个人配对的新人都与之前不同,不能存在其中某些人的分组没有变化的情况)的可能情况总数。(分组内外部均没有先后次序区别)

我的思路:

第一个人可以有n-1个选择,假设他选择了B,那么原本与B配对的人下一个选择,他有n-1个选择,然后假设他选择了C,原本与C配对的人下一个选择,他有n-2过选择……,最终结果是:(n-1) * (n-1)!


当然,结果是我是错的……

求问:

应该如何计算?我的思路错在哪里?

编程问题,所以程序解决思路也可以,不过我主要想知道数学原理。

将问题理解成1,2,3...n的错位排列:1,2,3...n重排,k不在第k个位置上。记Si为有i个数在原来位置上的排列,个数为n!/(i!(n_i)!)=n!/i!。#表示乘号。即i个数在原位上,剩下的数全排,剩下的数在不在原位上无所谓,因为容斥原理,错排个数为n!_n!/1!+n!/2!_...+n!/n! (_1)#. #表示乘方

关键你的匹配上的人没有减掉!

首先给出一个序列,滑动配对,就会不同
ABCD
cdab
计算该序列有几种配对方式。

    接着,把其中某些序列顺序打乱
找出不同于滑动序列的新的配对方式
    这些方式就是另外的可以配对的方式。
    把以上加起来求和

第一个人可以有n-1个选择,假设他选择了B,那么原本与B配对的人下一个选择,他有n-3个选择(减去第一个人和B,还有不能选自己吧)

n!(1_1/1!+1/2!_...+(_1)#n/n!)

n!(1_1/!+1/2!_...+(_1)#n/n!)

怎么发图!!!!!!!!!!!图片

计算该序列有几种配对方式。接着,把其中某些序列顺序打乱找出不同于滑动序列的新的配对方式这些方式就是另外的可以配对的方式。把以上加起来求和.