A007901 Number of minimal unavoidable n-celled pebbling configurations.

0, 0, 0, 0, 4, 22, 98, 412, 1700, 6974, 28576, 117146, 480722, 1974914, 8122084, 33435390, 137757480, 567998152, 2343472004, 9674252070, 39956606552, 165099840920, 682446679582, 2821858504062, 11671572244666, 48287711006032, 199822535773958, 827069530795224, 3423890026639184, 14176516741276534

Offset: 1

Author

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

Keywords

• nonn
• easy
• nice

References

• R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.50.

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.
• Google Labs, Google Labs congratulations puzzle
• Marcus Kazmierczak, Google Labs Puzzles, Jul 29, 2004.
• Slashdot (CmdrTaco), Google's Math Puzzle, Thu Sep 16, 2004.

Crossrefs

Cf. A007902.

Programs

Maple

The Maple snippet provides an alternative solution to the Google congratulations puzzle at http://www.7427466391.com. After running the Maple code, f(1) to f(4) match the puzzle, with f(5) being 1510865746 and f(6) being 6171783928.
Digits:=2000: E:=evalf(exp(1)): g:=n->trunc((E-(10^(-n)*trunc(E*10^n)))*10^(10+n)): h:=[0,0,0,0,4,22,98,412,1700]: f:=k->g(h[k+3]):

Mathematica

p[k_] := If[k < 7, {0, 4, -14, 22, -20, 6}[[k]], 0]; h[n_] := Sum[ k*p[k] * Binomial[2*n-k-1, n-k], {k, 1, n}]/n; u[n_] := Sum[ Sum[Binomial[j, n-k-j]*7^(2*k-n+j)*Binomial[k, j]*(-2)^(-n+k+2*j)*3^(2*(n-k-j)), {j, 0, k}], {k, 0, n}]; b[n_] := Sum[h[i]*u[n-i], {i, 1, n}]; a[n_] := If[n<2, 0 , b[n-2]]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Jan 14 2015, after Vladimir Kruchinin *)
CoefficientList[Series[x^3((1-3x+x^2)Sqrt[1-4x]-1+5x-x^2-6x^3)/(1-7x+14x^2-9x^3),{x,0,30}],x] (* Harvey P. Dale, May 19 2024 *)

Maxima

Polynom:[0,4,-14,22,-20,6];
p(k):=if k<7 then Polynom[k] else 0;
h(n):=sum(k*p(k)*binomial(2*n-k-1,n-k),k,1,n)/n;
u(n):=sum(sum(binomial(j,n-k-j)*7^(2*k-n+j)*binomial(k,j)*(-2)^(-n+k+2*j)*3^(2*(n-k-j)),j,0,k),k,0,n);
b(n):=sum(h(i)*u(n-i),i,1,n);
a(n):=if n<2 then 0 else b(n-2);
makelist(a(n),n,0,40); /* Vladimir Kruchinin, Sep 20 2014 */

PARI

x='x+O('x^44);
gf=x^3*((1-3*x+x^2)*sqrt(1-4*x)-1+5*x-x^2-6*x^3)/(1-7*x+14*x^2-9*x^3);
Vec(gf) \\ Joerg Arndt, Apr 20 2011

Formula

G.f.: x^3*((1-3*x+x^2)*sqrt(1-4*x)-1+5*x-x^2-6*x^3)/(1-7*x+14*x^2-9*x^3) [from the Stanley reference]. - Joerg Arndt, Apr 20 2011

Conjecture: (n-3)*(n-8)*a(n) +(-11*n^2+127*n-324)*a(n-1) +42*(n^2-12*n+34)*a(n-2) +(-65*n^2+799*n-2400)*a(n-3) +18*(n-6)*(2*n-13)*a(n-4)=0. - R. J. Mathar, Aug 14 2012