tailieunhanh - Báo cáo toán học: "The Problem of the Kings Herbert S. Wilf"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: The Problem of the Kings Herbert S. Wilf. | The Problem of the Kings Herbert S. Wilf University of Pennsylvania Philadelphia PA 19104-6395 Submitted June 21 1994 Accepted December 9 1994 On a 2m X 2n chessboard the maximum number of nonattacking kings that can be placed is mn since each 2 X 2 cell can have at most one king. Let fm n denote the number of ways that mn nonattacking kings can be placed on a 2m X 2n chessboard. The purpose of this paper is to prove the following result. Theorem. For each m 1 2 3 . there are constants cm 0 dm and 0 0m m 1 such that fm n cmn dm m 1 n Otfm n x . For every such placement of kings the chessboard is naturally divided into mn 2 X 2 cells each containing exactly one king. Let s say that a cell is of type 1 resp. 2 3 4 if the king sits in its NW resp. NE SE SW corner. The arrangement of kings is then completely specihed by an m X n matrix whose entries are 2 1 2 3 4 . For example the array 14 112 3 3 2 2 3 1 4 4 4 3 3 corresponds to a legal arrangement of kings on a 6 X 10 board namely the following one. K K K K K K K K K K K K K K K Conversely a matrix such as 1 represents an allowable conhguration of kings iff it satishes certain adjacency conditions namely that none of the following two letter words is permitted 21 24 31 34 1 2 4 4 3 1 2 4 2 Supported in part by the Office of Naval Research 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 2 1995 R3 2 Think of the columns of the array 1 as wooden playing pieces like dominoes. If we scan one of the pieces from top to bottom we see a block of 0 or more 1 s and 2 s followed by a block of 3 s and 4 s. Hence the number of pieces is altogether N N m m 1 2m. Thus there are 12 possible pieces that might be used to make a 2 X n array namely the pieces 41 13421 12223 441434321233 Now hx an integer m 1 and one of the N m wooden pieces of height m say the piece u 1 u N m . Let fm n u be the number of legal m X n arrays whose last . nth column is the given piece u and let fm n Xu fm n u . Then clearly fm n 1 u X fm n v A v u n 1 fm 1 u