免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 不允许出现两个相继数字的排列数

本帖最后由 青青子衿 于 2019-9-13 10:29 编辑

在\(\,\{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, ___}]]
复制代码
...
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.
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

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

TOP

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

全部 `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)!.\]
不知还能不能化简……

TOP

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*}\,\)
复制代码
在真 latex 中是会报错的,align* 一般只能~裸~用,不能放在其他数学环境里面,得换用 aligned。
冇钱又冇样、冇型又冇款、冇身材又冇文采、冇学历又冇能力、冇高度冇速度冇力度兼夹冇野做!(粤语)
口号:珍爱生命,远离考试。

TOP

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

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

但係就知道唔可以再化簡

TOP

返回列表 回复 发帖