#00 前言

关于错排问题，这里提出几个新的内容。

我们知道传统的错排问题指的是 完全错排问题，且针对的是一组 $1$ ~ $n$ 的排列。

---

对于一个 $1$ ~ $n$ 的排列，其完全错排方案数设为 $\text{A}(n)$，则：

$\text{A}(n)=(n-1)(\text{A}(n-1)+\text{A}(n-2))$

且通过列举知道 $\text{A}(1)=0,\text{A}(2)=1$。通过递推式可以用矩阵乘法加速做到 $O(\text{log}n)$ 求解出 $\text{A}(n)$。

还有一种方法求出 $\text{A}(n)$ 即数列通式法：

$\text{A}(n)=n!\sum_{i=2}^{n}\displaystyle\frac{(-1)^i}{i!}$

---

以上金堆完全错排问题做简单介绍。

先前我已经发过帖子求了一类错排问题，很遗憾没有得到有效的解答，在此就我已经解答的一个问题作出阐述。

之前的帖子：这里

至于其他的问题欢迎大家解答，并且此贴希望 不要有无意义回复。

• 若要回答问题请先看 #03，然后看 #02，可以从 #01 中获得一些启发。

• 若有错误或错字、少字，可以评论回复。

#01 不完全错排问题

对于 $1$ ~ $n$ 的排列，求其恰好有 $k$ 个数在原先位置上的排列数量。

对于此问题，不再提出“原排列”的概念，因为具体的原排列顺序对答案没有影响，这可以拓展到所有集合的错排问题，在此作为 定理 $Ⅰ$。

这个我们可以考虑二项式反演。

我们知道如果用 $f(k)=\binom{n}{k}(n-k)!$ 去计算所要求的的结果是不正确的，因为我们选定了 $k$ 个数固定，其余数进行排列时，他们也有可能处在原来的位置上。

（上面的式子表示选择固定 $k$ 个数，其余数进行全排列的方案）

设 $\text{A}_n(k)$ 表示一组 $1$ ~ $n$ 的排列，恰好有 $k$ 个数在原来的位置上的排列数，则：

$\binom{n}{k}(n-k)!=f(k)=\sum_{i=k}^{n}\binom{i}{k}\text{A}_n(i)$

其实也不全是巧合，因为右边的式子即包含了左边所有的重复情况，因此可以反演得到：

$\text{A}_n(k)=\sum_{i=k}^{n}(-1)^{n-i}\binom{i}{k}\binom{n}{i}(n-i)!$

二项式反演的正确性不用多说了，这样我们就求解了这个问题。

上面的多项式可以在 $O(n)$ 的时间内求解，也许有高效的算法。

• 所以求问：上述多项式是否有更高效的算法。

至此我们已经解决了不完全错排问题。

#02 广义错排问题的探讨

因为是探讨，即这类问题没有人成功解决，或者没有提出明确的解决方案。

对于“广义”，即上述集合不再是 $1$ ~ $n$ 的排列，而变为了一个含有 $n$ 个数字的多重集，即数字可以重复。

• 广义完全错排为题

对于一个大小为 $n$ 的多重集，求其每个位置上的数都与原来不同的排列数。

比如对于 $1,1,2,3$，有不只一种完全错排方案，其中一种为 $2,3,1,1$。但是像 $1,1,1,2$ 这样的多重集，其完全错排的方案数为 $0$。

• 广义不完全错排问题

对于一个大小为 $n$ 的多重集，求其恰有 $k$ 个位置上的数不变的排列方案数。

因为多重集如果按照 $1$ ~ $n$ 的排列做全排，则必然有重复排列，所以要考虑去重的问题，即将上面的 $f(k)$ 这一函数做一优化去重。

给出一个简单的解释：

一多重集 $1,1,2,3$，有一组排列 $2,1,1,3$ 其中第二位的 $1$ 与第四位的 $3$ 与原先排列相同。

现在求问：以上两种广义错排问题的高效解决方案。

#03 总结

这篇帖子，我们解决了 $1$ ~ $n$ 排列的不完全错排问题，并提出了两个更加复杂的问题，一个简单版本（广义完全错排）和一个复杂版本（广义不完全错排）。

希望能有读者在获得启发的同时提出以上两个问题的解决方案，希望足够高效。