n个有序的元素应有n!个不同的排列,若一个排列使得所有的元素都不在原来位置上,则称这个排列为错排。
错排公式推导
设n个数1,2,3...,n错排数目为Dn,对于其中任意一个数i:
(1) 数i分别与其他的n-1个数交换位置,其余n-2个数进行错排,共得到(n-1)Dn-2个错排;
(2) 对除数i以外的n-1个数进行错排,然后i与其中每个数互换,得到(n-1)Dn-1个错排。
因此,得到递推关系:Dn=(n-1)(Dn-1 + Dn-2),D1=0,D2=1。它的通解为Dn=n!-C(n,1)(n-1)!+C(n,2)(n-2)! - ... +(-)C(n,n)1!。
HDU2048
题意:给出n个元素,求错排的概率。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef __int64 int64;
const int N = 21;
int64 d[N];
int64 f[N];
int main()
{
int i;
int c,n;
d[1] = 0;
d[2] = 1;
f[1] = 1;
f[2] = 2;
for(i = 3; i < N; i++)
{
d[i] = (i-1)*(d[i-1] + d[i-2]);
f[i] = f[i-1]*i;
}
scanf("%d",&c);
while(c--)
{
scanf("%d",&n);
double p = 1.0*d[n]/f[n]*100.0;
printf("%.2lf%%\n",p);
}
return 0;
}
HDU2068
题意:给出n个元素,求有>=一半的元素在自己的位置的组合数。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef __int64 int64;
const int N = 15;
int64 d[N];
//c(m,n),m>=n
int64 composite(int64 m, int64 n)
{
int64 i,j;
if(n==0)
return 1;
int64 result = 1;
for(i=m,j=1; j <= n; i--,j++)
result = result*i/j;
return result;
}
int main()
{
int i;
d[1] = 0;
d[2] = 1;
for(i = 3; i < N; i++)
d[i] = (i-1)*(d[i-1]+d[i-2]);
int n;
while(true)
{
scanf("%d",&n);
if(n==0)
break;
int k = n/2;
int64 result = 0;
for(i = 2; i <= k; i++)
result += composite(n,i)*d[i];
printf("%I64d\n",result+1);
}
return 0;
}
分享到:
相关推荐
组合数学——卢开澄 组合数学——卢开澄组合数学——卢开澄组合数学——卢开澄
分形几何 教材 [分形几何——数学基础及其应用].(英国)Kenneth.Falconer-OCR
组合数学——母函数与递推_朱全民.ppt
高等数学微积分复习总结——定积分及其应用收集.pdf
小学数学——植树问题.ppt
计算机系教材,许多大学的指定考试书目,相信还是很有用的,我也是费劲找到的
分形几何方面的基础理论书籍,需要用超星阅读器
五年级数学下册 第四单元啤酒生产中的数学——比例 比例的应用教案 青岛版 教案.doc
小学数学——植树问题PPT教案.pptx
小学二年级数学——植树问题PPT教案.pptx
北邮——计算机——数学建模——专业选修 北邮——计算机——数学建模——专业选修 北邮——计算机——数学建模——专业选修 北邮——计算机——数学建模——专业选修 北邮——计算机——数学建模——专业选修 北邮...
六年级下册数学人教版周测培优卷7 数学广角——鸽巢问题的应用能力检测卷(含答案).pdf
算法设计需要估算计算量和存储量。组合数学研究计数和枚举的方法和理论。
模糊数学——模糊矩阵运算PPT学习教案.pptx
自己写的加整理的组合数学第四版课后答案,加上幻方和组合,排列的C源代码。自己的作业
离散数学——求集合;soursecode离散数学——求集合;soursecode离散数学——求集合;soursecode离散数学——求集合;soursecode离散数学——求集合;soursecode离散数学——求集合;soursecode离散数学——求集合;sourse...
大学的教程,组合数学
关于 Matlab工具箱应用指南——应用数学篇 的详细介绍书籍
高二数学——椭圆讲解高二数学——椭圆讲解高二数学——椭圆讲解