赞
踩
题目链接:神、上帝以及老天爷
AC代码:
- #include<iostream>
- #include<iomanip>
- using namespace std;
- typedef long long ll;
- double fun (int m)
- {
- ll a[25],b[25];
- a[0]=0;a[1]=0;a[2]=1;a[3]=2;
- for(int i=4;i<25;i++)
- a[i]=(i-1)*(a[i-1]+a[i-2]);
- b[0]=0;b[1]=1;
- for(int i=2;i<25;i++)
- b[i]=b[i-1]*i;
- return (double)a[m]/b[m];
- }
- int main()
- {
- int t;
- cin>>t;
- while(t--)
- {
- int m;
- cin>>m;
- double sum;
- sum=fun(m)*100;
- cout<<fixed<<showpoint<<setprecision(2);
- cout<<sum<<"%"<<endl;
- }
- return 0;
- }
错排:
n个有序的元素应有n!个不同的排列,如若一个排列使得所有的元素不在原来的位置上,则称这个排列为错排;有的叫重排。
如,1 2的错排是唯一的,即2 1。1 2 3的错排有31 2,2 3 1。这二者可以看作是1 2错排,3分别与1、2换位而得的。
错排问题是组合数学发展史上的一个重要问题,错排数也是一项重要的数。令
是
的一个错排,如果每个元素都不在其对应下标的位置上,即
,那么这种排列称为错位排列,或错排、重排(Derangement)。
我们从分析1 2 3 4的错排开始:
1 2 3 4的错排有:
4 3 2 1,4 1 2 3,4 3 1 2,
3 4 1 2,3 4 2 1,2 4 1 3,
2 1 4 3,3 1 4 2,2 3 4 1。
第一列是4分别与123互换位置,其余两个元素错排。
1 2 3 4->4 3 2 1,
1 2 3 4->3 4 1 2,
1 2 3 4-> 2 1 4 3
第2列是4分别与312(123的一个错排)的每一个数互换
3 1 2 4->4 1 2 3,
3 1 2 4->3 4 2 1,
3 1 2 4->3 1 4 2
第三列则是由另一个错排231和4换位而得到
2 3 1 4->4 3 1 2,
2 3 1 4->2 4 1 3,
2 3 1 4->2 3 4 1
上面的分析结果,实际上是给出一种产生错排的结果。
为求其递推关系,分两步走:
第一步,考虑第n个元素,把它放在某一个位置,比如位置k,一共有n-1种放法;
第二步,考虑第k个元素,这时有两种情况:(1)把它放到位置n,那么对于除n以外的n-1个元素,由于第k个元素放到了位置n,所以剩下n-2个元素的错排即可,有
种放法;(2)第k个元素不放到位置n,这时对于这n-1个元素的错排,有
种放法。
根据乘法和加法法则,综上得到
特殊地,
。此外,存在
因此,
。
下面利用递推关系证明通项公式,可利用母函数方法,也可利用容斥原理。首先基于母函数方法进行证明,令
有递推关系得
因此
,
,
而1/(1-x)可以替换成无穷级数(无穷递缩等比数列)
故(由对应次数项系数相等)
此外,也可基于容斥原理进行证明。设
为数i在第i为上的全体排列,
。则有
故每个元素都不在原来的位置上的排列数为
下面是一个实例解析:
希望可以帮到你!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。