算法问题：n组对象配对，最终均不配对的结果总数是多少？

Question

详细说明：

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

我的思路：

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


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

求问：

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

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

Answer 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)#. #表示乘方