主题
Search

错位排列

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

错位排列是一种排列，其中没有一个对象出现在其“自然”（即，有序）位置。例如，{1,2,3}的唯一错位排列是{2,3,1}和{3,1,2}，因此!3=2。类似地，{1,2,3,4}的错位排列是{2,1,4,3}、{2,3,4,1}、{2,4,1,3}、{3,1,4,2}、{3,4,1,2}、{3,4,2,1}、{4,1,2,3}、{4,3,1,2}和{4,3,2,1}。错位排列是没有不动点的排列（即，没有长度为 1 的循环）。可以使用Wolfram 语言计算n个元素的列表的错位排列

Derangements[l_List] := With[
  {perms = Permutations[l]},
  {supp = PermutationSupport /@ perms},
  Pick[perms, Length /@ supp, Length[l]]
]

错位排列问题由 P. R. de Montmort 于 1708 年提出，并由他在 1713 年解决 (de Montmort 1713-1714)。尼古拉斯·伯努利也使用容斥原理解决了这个问题 (de Montmort 1713-1714, p. 301; Bhatnagar 1995, p. 8)。

错位排列也称为重合数（以重合纸牌游戏命名）或完全排列，!n个n元素的错位排列数称为子阶乘n。

给出n个元素的不同的错位排列数量的函数称为子阶乘!n，并且等于

!n=n!sum_(k=0)^(n)((-1)^k)/(k!)
(1)
=(Gamma(n+1,-1))/e
(2)

(Bhatnagar 1995, pp. 8-9)，其中Gamma(z,a)是不完全伽玛函数，或

!n=[(n!)/e],
(3)

其中k!是通常的阶乘，而[x]是最近整数函数。

随着对象数量的增加，没有一个对象出现在其正确位置的概率P接近

P=lim_(n->infty)(!n)/(n!)=1/e
(4)

(Wells 1986, p. 27)。事实上，即使只有四个点，该概率也已经非常接近1/e。

长度为n的错位排列数!n=d(n)满足递推关系

d(n)=(n-1)[d(n-1)+d(n-2)]
(5)

和

d(n)=nd(n-1)+(-1)^n,
(6)

其中d(1)=0和d(2)=1 (Skiena 1990, p. 33)。前几个是 0, 1, 2, 9, 44, 265, 1854, ... (OEIS A000166)。虽然d(n)序列不能表示为固定数量的超几何项 (Petkovšek et al. 1996, pp. 157-160; Koepf 1998, p. 159)，但是可以精确地求解该递推式。

参见

夫妻就座问题, 部分错位排列, 排列, 根, 子阶乘

使用 探索

参考文献

Aitken, A. C. 行列式和矩阵。 Westport, CT: Greenwood Pub., p. 135, 1983.Ball, W. W. R. and Coxeter, H. S. M. 数学消遣和散文，第 13 版。 New York: Dover, pp. 46-47, 1987.Bhatnagar, G. 逆关系，广义双基级数及其 U(n) 扩展。 Ph.D. 论文。Ohio State University, 1995.Comtet, L. “‘重合问题’。” §4.2 in 高级组合数学：有限和无限展开的艺术，修订和扩充版。 Dordrecht, Netherlands: Reidel, pp. 180-183, 1974.Coolidge, J. L. 数学概率导论。 Oxford, England: Oxford University Press, p. 24, 1925.Courant, R. and Robbins, H. 什么是数学？：思想和方法的初等方法，第 2 版。 Oxford, England: Oxford University Press, pp. 115-116, 1996.de Montmort, P. R. Essai d'analyse sur les jeux de hasard. Paris, 1708. 第二版出版于 1713-1714 年。第三版在纽约重印：Chelsea, pp. 131-138, 1980.Dickau, R. M. “错位排列。” http://mathforum.org/advanced/robertd/derangements.html.Durell, C. V. and Robson, A. 高等代数。 London, p. 459, 1937.Graham, R. L.; Knuth, D. E.; and Patashnik, O. 具体数学：计算机科学基础，第 2 版。 Reading, MA: Addison-Wesley, 1994.Hassani, M. “错位排列及其应用。” J. Integer Seq. 6, No. 03.1.2, 1-8, 2003. http://www.math.uwaterloo.ca/JIS/VOL6/Hassani/hassani5.html.Koepf, W. 超几何求和：求和与特殊函数恒等式的算法方法。 Braunschweig, Germany: Vieweg, 1998.Petkovšek, M.; Wilf, H. S.; and Zeilberger, D. A=B。 Wellesley, MA: A K Peters, 1996. http://www.cis.upenn.edu/~wilf/AeqB.html.Roberts, F. S. 应用组合数学。 Englewood Cliffs, NJ: Prentice-Hall, 1984.Ruskey, F. “关于错位排列的信息。” http://www.theory.csc.uvic.ca/~cos/inf/perm/Derangements.html.Skiena, S. “错位排列。” §1.4.2 in 实现离散数学：使用 Mathematica 的组合数学和图论。 Reading, MA: Addison-Wesley, pp. 33-34, 1990.Sloane, N. J. A. 序列 A000166/M1937 in “整数序列在线百科全书。”Stanley, R. P. 枚举组合数学，第 1 卷。 New York: Cambridge University Press, p. 67, 1986.Vardi, I. Mathematica 中的计算消遣。 Reading, MA: Addison-Wesley, p. 123, 1991.Wells, D. 企鹅好奇和有趣的数字词典。 Middlesex, England: Penguin Books, p. 27, 1986.

在 上引用

错位排列

请引用本文为

Weisstein, Eric W. “错位排列。” 来自 Web 资源。 https://mathworld.net.cn/Derangement.html

学科分类