Volume 9, Issue 2

Articles
In and Out
Trott's Corner
New Products
New Publications
Calendar
News Bulletins
New Resources
Classifieds

Editorial Policy
Staff
Submissions
Subscriptions
Back Issues
Contact Information

A Generator of Rook Polynomials

A List Example

In this example, the computer algorithm for finding rook polynomials is an orderly list adaptation of the "by hand " example. First, initiate a horizontal "stack" with the list of the chessboard's (row, column) cells on the initial top of the stack. (In the implementation the top will be the first element of the list stacklist.) From data in the top of the stack, generate a list of cells of the first exclusive type board and append it to the bottom of the stack. (In the implementation the bottom will be put farthest to the right). Next, compare the (row, column) pattern information of the first cell of the top with the patterns of the remaining top cells to obtain the cell information for the first inclusive type list. The x multiplier has the same functional weight as a (row, column) cell in the inclusive list and is added on the right to complete the inclusive list. The inclusive list is appended to the right of the exclusive list and is now at the bottom of the stack.

Here is the result of applying the process to the first top, which is the
first element in this list.

In the following table this will look like a stack.

The top of the stack has served its purpose and is discarded. The lists can be envisioned as propagating up with each removal of a used top (or to the left in the list implementation). The general philosophy is to repeat the generation and removal of new tops until the stack consists only of x entries and a single 1. The single 1 is derived from the exclusive reduction of a single cell (see [2, 113] and the earlier use of ).

The following tabulation shows the progress of the algorithm through the 17
successive stack values.

The stacks 1, 3, 5, 7, 9, 11, 14, and 17 are stable stack configurations, while the others are stacks in transition. In particular, when top lists consist solely of 's (as in stacks 13 and 16), those lists are transferred to the bottom of the stack before normal stack operation resumes. The algebraic interpretation of the final stack is to multiply along the rows and add up the column, ignoring the list structure. {{1}} is interpreted as 1. Under these conditions, the program will convert stack 17 to the rook polynomial, .