问题

n封不同的信与n个不同的信封,求将n封信都装错信封的方案个数 ;

错排公式

D(n) = (n−1) ( D(n−1) + D(n−2) )

公式推导

假如有n封信,任何一封信都需要错位,错排方案数是D(n);

1.分步计数原理: 使用分步计数原理,先统计第一封信的排列方法,然后再讨论其余信的排列方法数;

( 1 )第一步: 首先找出一封信a出来,这封信不能排在其本身位置,只能放在其余n − 1个位置上,因此有 n − 1 种排法;

( 2 )第二步: 现在讨论其余除 a 之外的其余信的位置的错排问题 ;

2.分类计数原理

假设第一封信 a 占据了 b 的位置 , 那么此时 b 放在哪个信封分两种情况 ,b 放在 a 位置,或 b 不放在 a 位置;

( 1) 第一类 : 第一种情况是放在 a 位置 , 此时 b 放在 a 位置,剩下 n-2封信进行错排,方案数是D(n−2);

( 2 ) 第二类 : 第二种情况是 b 没有去 a 的位置 , 那么 b 可能出现在除 a 之外的任何位置 , b 有 n − 2 个位置可以去 ; 其余所有元素都有 n − 2 个位置可以去 (其本身位置和原来的b位置不能去 ), 这种情况下相当于除 a 之外的其它元素的错排问题(同样是每个元素都有n - 2 种位置选法) , 即 n − 1 个元素的错排问题 , 方案数是 D ( n − 1 );( 核心推导逻辑 )

( 3 ) 加法法则 : 汇总上述分类计数原理 , 使用 加法法则 , 计算结果是 D ( n − 1 ) + D ( n − 2 )

3 . 乘法法则 : 汇总上述分步计数原理 , 使用 乘法法则 , 计算结果是

D ( n ) = ( n − 1 ) ( D ( n − 1 ) + D ( n − 2 ) )
———————————————————————————————————————————————————————

参考( 照抄 )：【组合数学】错排问题 ( 递推公式 | 通项公式 | 推导过程 ) ★)

代码

#include<iostream>
using namespace std;

int fun(int n)
{
    //边界情况的嘞
    if(n==1)
        return 0;
    if(n==2)
        return 1;
    return (n-1)*(fun(n-1)+fun(n-2));
}
int main()
{
    int n;
    cin>>n;
    cout<<fun(n);
    return 0;
}