TOPICS
Search

Ryser Formula

A formula for the permanent of a matrix

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

where the sum is over all subsets of {1,...,n}, and |s| is the number of elements in s. The formula can be optimized by picking the subsets so that only a single element is changed at a time (which is precisely a Gray code), reducing the number of additions from n^2 to n.

It turns out that the number of disks moved after the kth step in the tower of Hanoi is the same as the element which needs to be added or deleted in the kth addend of the Ryser formula (Gardner 1988, Vardi 1991, p. 111).

See also

Determinant, Gray Code, Permanent, Tower of Hanoi

Explore with Wolfram|Alpha

References

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.

Referenced on Wolfram|Alpha

Ryser Formula

Cite this as:

Weisstein, Eric W. "Ryser Formula." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RyserFormula.html

Subject classifications