主題
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.tw/Derangement.html

學科分類