这周我正在做一些事情，这让我想知道有多少排列打破了所有连续的元素。例如，如果我们正在查看abcde的排列，则acebd有效，但acdbe无效。我想计算这种排列的数量，并估计大N的没有连续项的N 个元素的排列数量。
简短的搜索导致 OEIS 序列A000255 ，它给出了答案的递归公式。在讨论之前，让我们定义一些术语并进行一些强力计算以了解问题。
暴力计算
给定一个正整数n ，将Q ( n ) 定义为 1, 2, 3, …, n + 1 的分区p的数量，这样对于没有k的情况， p ( k + 1) = p ( k ) + 1 。
从 itertools 导入排列 def no_consec(perm): 对于范围内的 k(len(perm) - 1)： 如果 perm[k+1] == perm[k] + 1： 返回错误 返回真 定义 Q(n): 计数 = 0 对于 p 的排列（范围（n+1））： 如果没有_consec(p)： 计数 += 1 返回计数
我们可以使用此代码来计算中等大小的n的Q ( n ) ，但是以这种方式计算Q ( n ) 所需的时间与n成正比！所以这不会很好地扩展。
递归关系
OEIS 序列 A000255 给出了我们所说的Q ( n ) 的值，前几个值与上面代码的输出相匹配。但 OEIS 做得更好，为Q提供了递归解决方案：
Q ( n ) = n Q ( n − 1) + ( n − 1) Q ( n − 2)
对于n > 1，初始条件Q (0) = Q (1) = 1。
与斐波那契数一样，您可以将其作为递归函数轻松实现
定义 Q2(n): 如果 n 在 [0, 1] 中： 返回1 返回 n*Q2(n-1) + (n-1)*Q2(n-2)
但迭代实施要快得多。
定义 Q3(n): q = [1]*(n+2) 对于范围 (2, n+1) 中的 k： q[k] = k*q[k-1] + (k-1)*q[k-2] 返回 q[n]
您可以使用functools中的lru_cache通过记忆化来加快递归实现速度。然而，记忆并不能阻止递归；它只是使用缓存来加速递归，并且您仍然会收到一条错误消息，指出超出了最大递归深度。
渐近学
我们可以计算大n的Q ( n ) ，但我们没有可以让我们找到渐近行为的解析表达式。我打算在下一篇文章中解决这个问题。
根据经验，当n趋向无穷大时， Q ( n ) 似乎接近 ( n + 1)!/ e ，但在撰写本文时我没有证据证明这一点。如果这是正确的，则意味着在极限情况下，没有固定点的排列概率等于其没有连续值的概率。
没有连续元素的排列后首次出现在John D. Cook上。
原文： https://www.johndcook.com/blog/2025/03/15/permutations-question/