主题
Search

Ryser 公式


矩阵积和式的公式

 perm(a_(ij))=(-1)^nsum_(s subset= {1,...,n})(-1)^(|s|)product_(i=1)^nsum_(j in s)a_(ij),

其中,求和是对 {1,...,n} 的所有子集进行的,并且 |s|s 中元素的数量。 通过选择子集可以优化此公式,使得每次只更改一个元素(这正是格雷码),从而将加法的次数从 n^2 减少到 n

结果表明,在汉诺塔游戏中第 k 步之后移动的盘子数量与 Ryser 公式的第 k被加数中需要添加或删除的元素相同 (Gardner 1988, Vardi 1991, p. 111)。


另请参阅

行列式, 格雷码, 积和式, 汉诺塔

使用 Wolfram|Alpha 探索

参考文献

Gardner, M. "The Icosian Game and the Tower of Hanoi." Ch. 6 in Hexaflexagons and Other Mathematical Diversions: The First Scientific American Book of Puzzles and Games. New York: Simon and Schuster, pp. 55-62, 1959.Gardner, M. Time Travel and Other Mathematical Bewilderments. New York: W. H. Freeman, 1988.Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, p. 515, 1998.Nijenhuis, A. and Wilf, H. Chs. 7-8 in Combinatorial Algorithms. New York: Academic Press, 1975.Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, p. 111, 1991.

在 Wolfram|Alpha 中引用

Ryser 公式

请引用为

Weisstein, Eric W. “Ryser 公式。” 来自 MathWorld-- Wolfram Web 资源。 https://mathworld.net.cn/RyserFormula.html

学科分类