欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

错排公式浅谈(推导+应用)

程序员文章站 2022-03-21 18:37:32
给出一个已经排好的长度为n的数列,问全部排错一共有多少排法? 典型利用错排公式去解决问题, (搜一下)我们不难知道错排公式递推式为 $$ D(n)=(n 1)(D(n 1)+D(n 2)) $$ 特殊地, D(1) = 0, D(2) = 1. 进一步的化简即可得出 $$ D(n) = n! [( ......

给出一个已经排好的长度为n的数列,问全部排错一共有多少排法?

典型利用错排公式去解决问题,

(搜一下)我们不难知道错排公式递推式为
\[ d(n)=(n-1)(d(n-1)+d(n-2)) \]
特殊地,d(1) = 0, d(2) = 1.

进一步的化简即可得出
\[ d(n) = n! [(-1)^2/2! + … + (-1)^{(n-1)}/(n-1)!+(-1)^n/n!] \]

推导

首先先来解释一下递推公式(分布乘法):

假设这组数列中有两个数a,b以及他们原来的位置(a),(b);

现在将a,b单独取出来看;错排公式浅谈(推导+应用)

第一步错排a:去除最初存在的位置还剩下n-1个位置满足a错排的要求,即n-1

错排公式浅谈(推导+应用)

第二步排b:这里有两种情况:

​ 1、b在a位置上:这里只有1种剩下的n-2项再进行上述的错排,即1 * d(n-2)

错排公式浅谈(推导+应用)

​ 2、b不在a位置上:这里相当于n-1项再进行上述的错排,即d(n-1)

错排公式浅谈(推导+应用)

综上即可得出递推公式
\[ d(n)=(n-1)(d(n-1)+d(n-2)) \]
之后进行整理:
\[ d(n)=n*d(n-1)+n*d(n-2)-d(n-1)-d(n-2) \]
递推可得
\[ d(n)-n*d(n-1)=-[d(n-1)-(n-1)*d(n-2)]················1项 \]

\[ d(n-1)-(n-1)d(n-2)=-[d(n-2)-(n-2)*d(n-3)]·········2项 \]

\[ d(n-2)-(n-2)d(n-3)=-[d(n-3)-(n-3)*d(n-4)]·········3项 \]

\[ d(n-3)-(n-3)d(n-4)=-[d(n-4)-(n-4)*d(n-5)]·········4项 \]

\[ ······ \]

\[ d(3)-3*d(2)=-[d(2)-2*d(1)]······························n-2项 \]

同时设d(n)=n!*nn

错项相消得
\[ n(n)-n(1)=1/2!-1/3!+1/4!+······+(-1)^{(n-1)}/(n-1)!+(-1)^n/(n)! \]
移项进一步整理(特殊的n(1)=0,n(2)=0)即可得出
\[ d(n) = n! [(-1)^2/2! + … + (-1)^{(n-1)}/(n-1)!+(-1)^n/n!] \]

应用

(懒得复制,上链接)

t1、hdu 2048 神、上帝以及老天爷

要计算概率=全不中奖组合数/所有组合数;

全不中奖组合数采用上面推导的错排公式即可求解

代码样例

#include <bits/stdc++.h>
using namespace std;

int main()
{
    long long f[21]= {0};
    f[1]=0;
    f[2]=1;
    for(int i=3; i<21; i++)
        f[i]=(i-1)*(f[i-1]+f[i-2]);
    int t,n;
    cin >> t;
    for(int i=0; i < t; i++)
    {
        cin >> n;
        long long sum=1;
        for(int j=2; j<=n; j++)
                sum*=j;
        double b=100.0*f[n]/sum;
        printf("%.2f%%\n",b);   
    }
    return 0;
}

t2、hdu 2049 不容易系列之(4)——考新郎

这道题先用排列组合计算出所有m个找错新娘的新郎的组合数,之后乘以利用错排公式计算出的数据;

代码样例

#include <bits/stdc++.h>
using namespace std;
#define maxn 21

long long ci(int m,int n)
{
        long long sum1=1,sum2=1;
        for(int j=2; j <= m; j++)
        sum1*=j;
        for(int j=n; j > n-m; j--)
        sum2*=j;
        return sum2/sum1;
}

int main()
{
    long long f[maxn]={0};
    f[1]=0;
    f[2]=1;
    for(int i=3; i < maxn; i++)
        f[i]=(i-1)*(f[i-1]+f[i-2]);
    int c;
    cin >> c;
    for(int i=1; i <= c; i++)
    {
        int n,m;
        cin >> n >> m;
        printf("%lld\n",ci(m,n)*f[m]);      
    }
    return 0;
}