OFFSET
1,1
COMMENTS
T(n,k) is the number of walks on the 3 dimensional grid that start and end at the origin using 2n steps and having exactly k primitive loops. The steps are in the eight directions: (1,1,1), (1,1,-1), (1,-1,1), (1,-1,-1), (-1,1,1), (-1,1,-1), (-1,-1,1), (-1,-1,-1). A primitive loop is a walk that starts and ends on the origin but does not otherwise touch the origin.
Column 1 is A094059.
Row sums are A002897.
FORMULA
G.f.: 1/( 1 - y*(1 - 1/A(x)) ) where A(x) is the o.g.f. for A002897.
Generally for such walks in N dimensions: 1/( 1 - y*(1 - 1/B(x)) ) where B(x) = Sum_{n>=0} binomial(2n,n)^N*x^n.
EXAMPLE
8,
152, 64,
5056, 2432, 512,
205720, 104000, 29184, 4096,
9305152, 4828544, 1525248, 311296, 32768,
449404224, 236984448, 79898624, 19226624, 3112960, 262144
MATHEMATICA
nn=6; a=Sum[Binomial[2n, n]^3x^n, {n, 0, nn}]; Map[Select[#, #>0&]&, Drop[CoefficientList[Series[1/(1-y(1-1/a)), {x, 0, nn}], {x, y}], 1]]//Grid
CROSSREFS
KEYWORD
AUTHOR
Geoffrey Critzer, Oct 04 2013
STATUS
approved