On the number of reachable configurations for the chessboard pebbling problem
Recently, Chung, Graham, Morrison and Odlyzko [F. Chung, R. Graham, J. Morrison, A. Odlyzko, Pebbling a chessboard, Amer. Math. Monthly 102 (1995) 113-1231 studied various combinatorial and asymptotic enumeration aspects of chessboard pebbling. Here, a pebble is placed at the origin (0, 0) of an infinite chessboard. At each step, a pebble is removed from (i, j) and replaced by two pebbles at positions (i, j + 1) and (i + 1, j) (provided these are unoccupied). After k steps, the board has k + I pebbles in various arrangements. Here we study the number of possible arrangements asymptotically, as k -> infinity. We analyze the recurrence derived in [F. Chung, R. Graham, J. Morrison, A. Odlyzko, Pebbling a chessboard, Amer. Math. Monthly 102 (1995) 113-123] by methods of applied mathematics, such as WKB expansions and matched asymptotics. In particular, we obtain an analytic expression for the growth rate of the number of possible arrangements. (c) 2007 Elsevier Ltd. All rights reserved.
chessboard pebbling asymptotics wkb expansions