组合问题之错排问题

错排问题

n把钥匙，n把锁，随机分配，全部配错的方案数怎么算？

钥匙a，除了锁a以外有 （ n − 1 ） （n-1） （n−1） 种方案，假设选定锁b

钥匙b，此时面临两种选择 选择锁a 和 不选择锁a

• 选择锁a，a,b两者之间相互满足，此时剩下的是一个子问题，若原来的问题表示为 f ( n ) f(n) f(n) ，则子问题为 f ( n − 2 ) f(n-2) f(n−2)
• 不选择锁a，此时我们可以采取一个思想实验，将钥匙b看成钥匙a，那么不选择锁a就是出自题意的考虑，而剩下的其它钥匙（除开原来的a, b）也和此时的新a钥匙一样，满足：
  • 属于一个大小为n-1的钥匙集合
  • 都有属于各自的锁
  • 不能选择自身的锁 ，构成另一个子问题 f ( n − 1 ) f(n-1) f(n−1)
    
    

由此得出公式： f ( n ) = ( n − 1 ) ⋅ ( f ( n − 1 ) + f ( n − 2 ) ) f(n) = (n-1) \cdot (f(n-1) + f(n-2)) f(n)=(n−1)⋅(f(n−1)+f(n−2))

void cal_d(int n)
{
    d[1] = 0, d[2] = 1;
    for (int i = 3; i <= n; i++)
    {
        d[i] = (i - 1) * (d[i - 1] + d[i - 2]);
    }
}

例题