不允许出现两个相继数字的排列数

青青子衿

在\(\,\{1,2,\cdots,n\}\,\)的排列中，不允许出现两个相继（相邻两个数，右边比左边大个1）数字的数目
\(\,\begin{align*}
&a_{n}= n\cdot\,\!a_{n-1}+ (n-1)\cdot\,\!a_{n-2}\\
&\begin{cases}
a_0=1\\
a_1=1
\end{cases}
\end{align*}\,\)
...

1. Cases[Cases[
2.   Cases[Permutations[{1, 2, 3, 4}], Except[{___, 1, 2, ___}]],
3.   Except[{___, 2, 3, ___}]], Except[{___, 3, 4, ___}]]

Copy the Code

...
1 3 2 4;     1 4 3 2;     2 1 4 3;
2 4 1 3;     3 2 1 4;     3 2 4 1;
4 1 3 2;     4 2 1 3;     4 3 2 1;
2 4 3 1;     3 1 4 2.

kuing

无需三个 Cases 啊
Cases[Permutations[{1, 2, 3, 4}], Except[{___, 1, 2, ___} | {___, 2, 3, ___} | {___, 3, 4, ___}]]

kuing

你那递推式不知该怎么理解，但我发现用容斥原理就可以直接得出结果：

全部 `n!`；

有一个相继，即 *12*、*23*、*34* 这类，每个 `(n-1)!`，有 `n-1` 个，所以共 `(n-1)(n-1)!`；

有两个相继，包括 *12*34* 这种，还包括 *123* 这种（看成 12 和 23 两个相继），每个都是 `(n-2)!`，有 `C_{n-1}^2` 个，所以共 `C_{n-1}^2(n-2)!`；

同理，有 `k` 个相继的共 `C_{n-1}^k(n-k)!`。

于是由容斥原理知结果为：
\[n!-(n-1)(n-1)!+C_{n-1}^2(n-2)!-C_{n-1}^3(n-3)!+\cdots+(-1)^{n-1},\]写成和式即
\[\sum_{k=0}^{n-1}(-1)^kC_{n-1}^k(n-k)!.\]
不知还能不能化简……

kuing

PS、你的公式代码

1. \(\,\begin{align*}
2. &a_{n}= n\cdot\,\!a_{n-1}+ (n-1)\cdot\,\!a_{n-2}\\
3. &\begin{cases}
4. a_0=1\\
5. a_1=1
6. \end{cases}
7. \end{align*}\,\)

Copy the Code

在真 latex 中是会报错的，align* 一般只能~裸~用，不能放在其他数学环境里面，得换用 aligned。

tommywong

可以寫成錯排，唔知係唔係同錯排有關

$\displaystyle (-1)^n+(n+1)
\sum_{k=0}^{n-1}(-1)^k\frac{(n-1)!}{k!}
=(n+1)D_{n-1}+(-1)^n$

但係就知道唔可以再化簡