错排问题的递推公式

痛定思痛。 2022-05-16 03:15 231阅读 0赞

### 问题描述 ###

考虑一个n个数字的排列，使所有的数字都不在自己所对应序号的位置上，这样的一个排列就称为原排列的一个错排，现在给定一个数字n，求解所有可能的错排的个数。

### 分析 ###

首先使用 D(n)  D ( n )  表示n个数字的错排数目， D(n−1)  D ( n − 1 ) 表示n-1个数字的全排列数目，以此类推，推导过程：

1.  对于第N  N 个位置的数字n n，首先选取一个位置K  K （任意的非N N的位置）放置，共有(n−1)  ( n − 1 ) 种情况
2.  然后考虑第K  K 个位置的数字k k，如果k  k 放在第N N个位置，那么相当于剩下的(n−2)  ( n − 2 ) 个数字进行错排，即共有D(n−2)  D ( n − 2 ) 种情况,（n  n ，k k都已经确定了位置），如果k  k 不放在第n n个位置，那么就相当于(n−1)  ( n − 1 ) 个数字进行错排，也就是D(n−1)  D ( n − 1 ) ，（这种情况，只有n  n 的位置确定了）

综上，所有的情况就是：  
D(n)=(n−1)⋅(D(n−1)\+D(n−2)) D( n )=(n − 1)⋅(D(n − 1)\+ D(n − 2))

这就是n个数字进行错排的递推公式，很多题目，例如[SDUT2058][]，都考察到了这一点：  
代码：

#include<stdio.h>
    #include<stdlib.h>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    
    long long int sav[25];
    int n;
    int main(){
        sav[1]=0;
        sav[2]=1;
        for(int i=3; i<21; i++){
            sav[i] = (i-1) * (sav[i-1] + sav[i-2]);
        }
        while(cin>>n){
            cout<<sav[n]<<endl;
        }
    
        return 0;
    }

以上~

[SDUT2058]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2553/pid/2058

发表评论取消回复

表情：

评论列表（有 0 条评论，231人围观）

还没有评论，来说两句吧...

相关阅读

相关约瑟夫环——公式法（递推公式）

约瑟夫问题约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。例如只有

痛定思痛。/ 2024年04月01日 09:42/ 0 赞/ 60 阅读

相关错排问题错排公式 Hdu 1465 + 2048 +2049 + 2068 + 4535

也称伯努利-欧拉装错信封问题 n错排公式：F\[n\]=(n-1)\(F\[n-1\]+F\[n-2\]) 证明： 1.当前n-1个错排时：将其任意一封信与n对调,共(

小鱼儿/ 2022年08月25日 10:52/ 0 赞/ 156 阅读

相关错排公式

错排公式 M(n)=(n-1)\[M(n-2)+M(n-1)\] 递推的方法推导错排公式　　当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用M(n)

傷城~/ 2022年08月10日 14:52/ 0 赞/ 141 阅读

相关 poj3597 Polygon Division +动态规划+递推公式+公式转化技巧

poj3597 Polygon Division +动态规划+递推公式+公式转化技巧题目链接：[http://poj.org/problem?id=3597][http_po

绝地灬酷狼/ 2022年07月16日 07:53/ 0 赞/ 185 阅读

相关递推中的错排问题

本文大部分资料来自网络。。。。假设有n个数，元素编号与位置编号各不对应的方法数用D(n)表示，那么D(n-1)就表示n-1个编号元素放在n-1个编号位置，各不对应

逃离我推掉我的手/ 2022年07月12日 09:47/ 0 赞/ 297 阅读

相关考新郎——错排公式

think: 1主要考察错排公式中体现的递推思想 2延伸到n个数中m个数的错排 [错排公式链接][Link 1] [sdut题目链接][sdut] [hdoj

爱被打了一巴掌/ 2022年07月12日 08:22/ 0 赞/ 173 阅读

相关考新郎——错排公式

think: 1主要考察错排公式中体现的递推思想 2延伸到n个数中m个数的错排 [错排公式链接][Link 1] [sdut题目链接][sdut] [hdoj

阳光穿透心脏的1/2处/ 2022年07月12日 08:22/ 0 赞/ 153 阅读

相关暗黑的字符串---递推公式

题目描述一个只包含'A'、'B'和'C'的字符串，如果存在某一段长度为3的连续子串中恰好'A'、'B'和'C'各有一个，那么这个字符串就是纯净的，否则这个字符串就是暗黑

我会带着你远行/ 2022年06月09日 09:25/ 0 赞/ 180 阅读

相关错排问题的递推公式

问题描述考虑一个n个数字的排列，使所有的数字都不在自己所对应序号的位置上，这样的一个排列就称为原排列的一个错排，现在给定一个数字n，求解所有可能的错排的个数。分析

痛定思痛。/ 2022年05月16日 03:15/ 0 赞/ 232 阅读

相关两道递推公式题的解题报告

T1（阿牛的EOF牛肉串）题意：一串由EOF三个字母组成的长度为\\(n\\)的字母串，不能出现连续的OO，求字符串种类数\\(f\[n\]\\) 答案：\

Bertha 。/ 2021年12月24日 19:19/ 0 赞/ 223 阅读