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–123] studied various combinatorial and asymptotic enumeration aspects of chessboard pebbling. Here, a pebble is placed at the origin (0,0)(0,0) of an infinite chessboard. At each step, a pebble is removed from (i,j)(i,j) and replaced by two pebbles at positions (i,j+1)(i,j+1) and (i+1,j)(i+1,j) (provided these are unoccupied). After kk steps, the board has k+1k+1 pebbles in various arrangements. Here we study the number of possible arrangements asymptotically, as k→∞k→∞. 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.