nxy006
Magic_0919
采纳率100%
2016-01-24 15:26 阅读 1.8k
已采纳

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

10

详细说明:

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

我的思路:

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


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

求问:

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

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

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

8条回答 默认 最新

  • 已采纳
    sssseeeeee sssseeeeee 2016-01-25 02:53

    将问题理解成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)#. #表示乘方

    点赞 评论 复制链接分享
  • kernel_my kernel_my 2016-01-24 15:50

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

    点赞 评论 复制链接分享
  • lm_whales lm_whales 2016-01-24 15:50

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

        接着,把其中某些序列顺序打乱
    找出不同于滑动序列的新的配对方式
        这些方式就是另外的可以配对的方式。
        把以上加起来求和
    
    点赞 评论 复制链接分享
  • 91program 91program 2016-01-25 00:32

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

    点赞 评论 复制链接分享
  • sssseeeeee sssseeeeee 2016-01-25 02:32

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

    点赞 评论 复制链接分享
  • sssseeeeee sssseeeeee 2016-01-25 02:33

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

    点赞 评论 复制链接分享
  • sssseeeeee sssseeeeee 2016-01-25 03:01

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

    点赞 评论 复制链接分享
  • John_ToStr John_ToDebug 2016-01-25 10:04

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

    点赞 评论 复制链接分享

相关推荐