Permutations, Derangements, and Other Forbidden Position Problems Using Non-Attacking Rooks
Permutations, Derangements, and Other Forbidden Position Problems Using Non-Attacking Rooks
A permutation of can be made to correspond to placing mutually non-attacking rooks on an chessboard: if the permutation is , place the rook on the rank and file. (Thinking of a chessboard as a matrix, rank and file mean row and column.) A derangement is a permutation where no element stays in its original position; it corresponds to placing the rooks on the board with the added requirement that the squares on the main diagonal are forbidden. Two other forbidden position problems are illustrated: avoiding the main diagonal and the diagonal just above it, and avoiding the main tridiagonal. In this Demonstration a chessboard consists of white squares, and black squares indicate forbidden positions.
{1,2,…,n}
n
n×n
{,,…,}
x
1
x
2
x
n
th
i
th
i
th
x
i