A007902 Number of pebbling configurations with n pebbles.

1, 1, 2, 4, 9, 20, 46, 105, 243, 561, 1301, 3014, 6995, 16227, 37668, 87426, 202961, 471150, 1093819, 2539348, 5895408, 13686805, 31775756, 73771474, 171270732, 397628399, 923150354, 2143222823, 4975795414, 11552012449, 26819637103, 62265592589, 144558421877

Offset

1,3

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000

F. R. K. Chung, R. L. Graham, J. A. Morrison and A. M. Odlyzko, Pebbling a chessboard, Amer. Math. Monthly 102 (1995), pp. 113-123.

A. Khodulev, Pebble spreading, Kvant, July 1982, pp. 28-31, 55.

Charles Knessl, On the number of reachable configurations for the chessboard pebbling problem, Mathematical and Computer Modelling, Volume 47, Issues 1-2 (2008), 127-139.

M. Kontsevich, Problem M715, Kvant, November 1981, p. 21.

Zvezdelina Stankova and Brady Haran, Pebbling a Chessboard, Numberphile video (2013)

Formula

a(n) ~ c * d^n, where d = 2.321642199494229709895447236309905876768690729938226667582430304..., c = 0.122687073421485997619475676632990508558955463577161642002764414... (Knessl, 2006). - Vaclav Kotesovec, Sep 06 2014

Example

a(4) = 4:
|_|_|_|_|_   |_|_|_|_|_   |_|_|_|_|_   |_|_|_|_|_
|Q|_|_|_|_   |_|_|_|_|_   |_|_|_|_|_   |_|_|_|_|_
|_|Q|_|_|_   |Q|Q|_|_|_   |_|Q|_|_|_   |_|_|_|_|_
|_|Q|_|_|_   |_|_|Q|_|_   |Q|_|Q|_|_   |Q|Q|Q|_|_
|_|Q|_|_|_   |_|Q|_|_|_   |_|_|Q|_|_   |_|_|_|Q|_ . - Alois P. Heinz, Dec 20 2013

Maple

G:= proc(k, m) option remember; `if`(k<1, 0,
      `if`(m=0, 2*G(k-1, 0) +G(k, 1) +`if`(k=2, 1, 0),
      `if`(m=1, G(k-3, 0) +2*G(k-2, 1) +G(k-1, 2) +G(k-4, 1),
       G(k-m-2, m-1) +2*G(k-m-1, m) +G(k-m, m+1))))
    end:
a:= n-> `if`(n=1, 1, G(n, 0)):
seq(a(n), n=1..40);  # Alois P. Heinz, Dec 20 2013

Mathematica

G[k_, m_] := G[k, m] = If[k<1, 0, If[m == 0, 2*G[k-1, 0]+G[k, 1]+If[k == 2, 1, 0], If[m == 1, G[k-3, 0]+2*G[k-2, 1]+G[k-1, 2]+G[k-4, 1], G[k-m-2, m-1]+2*G[k-m-1, m]+G[k-m, m+1]]]]; a[n_] := If[n == 1, 1, G[n, 0]]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Feb 03 2014, after Alois P. Heinz *)

Crossrefs

Cf. A007901.

Sequence in context: A006958 A036617 A367713 * A057417 A191653 A191827

Adjacent sequences: A007899 A007900 A007901 * A007903 A007904 A007905

Keyword

nonn,easy,nice

Author

odlyzko(AT)dtc.umn.edu (A. M. Odlyzko)

Status

approved