错位排列 | 您所在的位置:网站首页 › 信封的编号是什么 › 错位排列 |
首先先介绍一下什么是错位排列: 错位重排是指一种比较难理解的复杂数学模型,是伯努利和欧拉在错装信封时发现的,因此又称伯努利-欧拉装错信封问题 也是离散课本上出现的戴错帽子问题 简介表述为:编号是1、2、…、n的n封信,装入编号为1、2、…、n的n个信封,要求每封信和信封的编号不同,问有多少种装法? 对这类问题有个 固定的递推公式 (类似于 dp、递推之类的),记n封信的错位重排数为Dn, 则D1=0,D2=1,(0封信错排数是0,一封信错排数是1) Dn=(n-1)*(Dn-2+Dn-1) 此处n-2、n-1为下标 即 F[N]=(N-1)*( F[N-1] + F[N-2] ) 当n>2 我们只需记住Dn的前几项:D1=0,D2=1,D3=2,D4=9,D5=44 此时我们只需要记住结论,进行递推计算找出递推方程即可 【例】五个盒子都贴了标签,全部贴错的可能性有多少种? 即全贴错标签,N个项数全部排错的可能数,可以总结出数列: 0,1,2,9,44,265,……… 可以得到这样一个递推公式:(N-1)*(A+B)=C (A是第一项,B是第二项,C是第三项,N是项数) s(n)=(n-1) [ s(n-1)+s(n-2)] s(2)=1,s(3)=2 s(4)=3*(1+2)=9 s(5)=4*(2+9)=44 s(6)=5*(9+44)=265 .................... 公式由来 把编号 1-------------n的小球放到编号1------n的盒子里,全错位排列(1号球不在1号盒,2号球不在2号盒,依次类推),共有几种情况? 设n个球全放错的情况有 s(n)种 1号盒子可以选 [2,n] 共(n-1)种选择,设1号盒选择某号球后对应的错排次数是 a (n-1 个选择对应的错排次数是相同的 ,则 s(n)=(n-1)a 不妨设1号盒选择2号球 1: 2号盒选择1号球,剩下 (n-2)个球去错排,有 s(n-2)种情况 2: 2号盒不选择1号球,则后面总有一个盒子选择1号球,我们可以把1号球换成2号球, 对问题没有影响,此时就相当于对(n-1)个球去错排,有s(n-1)种情况 于是 a= s(n-1)+s(n-2) s(n)=(n-1) [ s(n-1)+s(n-2)] s(2)=1,s(3)=2 s(4)=3*(1+2)=9 s(5)=4*(2+9)=44 s(6)=5*(9+44)=265 ....................
以上来自百度百科 po一个例题 国庆期间,省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做"考新郎",具体的操作是这样的: 首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排; 然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个. 最后,揭开盖头,如果找错了对象就要当众跪搓衣板... 看来做新郎也不是容易的事情... 假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能. Input 输入数据的第一行是一个整数C,表示测试实例的个数,然后是C行数据,每行包含两个整数N和M(1>m; LL x=s[n]/s[m]/s[n-m]; cout |
CopyRight 2018-2019 实验室设备网 版权所有 |