错排公式

对于$D[n]$都有$D[n]=(n-1)*(D[n-1]+D[n-2])$【特殊的，$D[0]=1$,$D[1]=0$，$D[2]=1$】。

$D[n]=n!*(\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}- \frac{1}{5!}+ ··· ··· +\frac{(-1)^{n-1}}{(n-1)!}+\frac{(-1)^n}{n!})$。

下面拓展一下i个人有j个人是正确的；

i个人有j个时正确的，有三种情况，

1：前i-1个人有j-1个正确,然后分配给第i个人他自己的物品。

2：前i-1个人有j个正确，分配给第i个人他自己的物品，然后再把第i个人和前i-1个人拥有不正确物品的人交换

3：前i-1个人，有j+1个人正确，分配给$d_i$个人他自己的物品，然后和前i-1个人拥有正确物品的人交换

结果就是：

小tip：

当指数很大取模时，可以多次快速幂。

比如2的10的24次方的次方，可以拆成2的10的12次方取模，再对得数取模。

分配问题

整数拆分

整数的有序拆分

将n个相同物体分配到m个不同位置上，称为整数的有序拆分，拆分数等于方程$n=x_1+x_2+...+x_m$的解的个数。

无空位时，拆分数为$C_{n-1}^{m-1}$。

可以有空位时，拆分数为$C_{n+m-1}^{n}=C_{n+m-1}^{m-1}$。

例：

8台计算机分配给3个单位，第一个单位的分配量不超过3台，第二个单位的分配量不超过4台，第三个单位的分配量不超过5台，问有几种分派方案？

解：$G(x)=(1+x+x^2+x^3)(1+x+x^2+x^3+x^4)(1+x+x^2+x^3+x^4+x^5)$，化简之后（其实可以写个程序跑一跑），$x^8$的系数为14，所以共14种分配方案。

整数的无序拆分

将n个相同物体分配到m个相同的位置上，称为整数的无序拆分。

无空位时，

将正整数n分成m个部分，$n=n_1+n_2+...+n_m(m\geq 1,n_i\geq 1)$，且不考虑$n_i$的次序，满足$n_1\geq n_2...\geq n_m$，拆分数记为$P_m(n)$。

定理：正整数n拆分成m个部分的方案数等于整数n的拆分中最大部分为m的方案数。

若整数n拆分成1,2,…,m的和，并允许重复，其母函数为$G(x)=(1+x+x^2+...)(1+x^2+{(x^2)}^2+...)...(1+x^m+{(x^m)^2}+...)$。

可以有空位时，

当$n\geq m$时，方案数=$P_1(n)+P_2(n)+...+P_m(n)$。

当$n<m$时，方案数=$P_1(n)+P_2(n)+...+P_n(n)$。

整数n拆分中，所有部分均为奇数，其母函数为$G(x)=(1+x+x^2+...)(1+x^3+{(x^3)}^2+...)(1+x^5+{(x^5)}^2+...)...$。

整数n拆分中，所有部分不相等，其母函数为

$G(x)=(1+x)(1+x^2)(1+x^3)...$。

例：