[go: up one dir, main page]
TOPICS
Search

Rook Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A rook polynomial is a polynomial

R_(m,n)(x)=sum_(k=0)^(min(m,n))r_kx^k
(1)

whose number of ways k nonattacking rooks can be arranged on an m×n chessboard. The rook polynomials are given by

R_(m,n)(x)=n!x^nL_n^(m-n)(-x^(-1)),
(2)

where L_n^alpha(x) is an associated Laguerre polynomial.

The first few rook polynomials R_n=R_(nn) on square n×n boards are

R_1(x)=x+1
(3)
R_2(x)=2x^2+4x+1
(4)
R_3(x)=6x^3+18x^2+9x+1
(5)
R_4(x)=24x^4+96x^3+72x^2+16x+1
(6)

(OEIS A021010).

RookPolynomial

As an illustration, note that the n=2 case has two ways to place two rooks (i.e., the rook number r_2^((2,2))=2), four ways to place one rook (r_1^((2,2))=4), and one way to place no rooks (r_0^((2,2))=1), hence R_2(x)=2x^2+4x+1.

See also

Rook Number, Rook Reciprocity Theorem, Rooks Problem

Explore with Wolfram|Alpha

References

Fielder, D. C. "A Generator of Rook Polynomials." Mathematica J. 9, 371-375, 2004.Liu, C. L. Introduction to Combinatorial Mathematics. New York: McGraw-Hill, pp. 111-118, 1968.Riordan, J. "The Problem of the Rooks," "Properties of Rook Polynomials," and "Rectangular Boards." §7.2, 7.3, and 7.4 in An Introduction to Combinatorial Analysis. New York: Wiley, pp. 164-170, 1958.Sloane, N. J. A. Sequence A021010 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Rook Polynomial

Cite this as:

Weisstein, Eric W. "Rook Polynomial." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RookPolynomial.html

Subject classifications