# [seqfan] Re: 3D version of A000938: 3-in-line inside the nXnXn cube

Richard Mathar mathar at strw.leidenuniv.nl
Sun May 23 14:13:27 CEST 2010

```Counted in
http://list.seqfan.eu/pipermail/seqfan/2010-May/004752.html :

rh> Ron Hardin
rh> Sun May 23 12:55:25 CEST 2010
rh> 3 points in a side-4 2..9 dimensional grid
rh> \$ awk '{print FILENAME,\$4}' stat??3.txt
rh> stat203.txt 44
rh> stat303.txt 376
rh> stat403.txt 2960
rh> stat503.txt 22624
rh> stat603.txt 171584
rh> stat703.txt 1303936
rh> stat803.txt 9969920
rh> stat903.txt 76793344

This looks like
a(n) = 6^n+8^n/2-4^n*3/2,
a(n)= +18*a(n-1) -104*a(n-2) +192*a(n-3),
Extrapolation (offset 0 by adding a(0)=0 and a(1)=4):
0,4,44,376,2960,22624,171584,1303936,9969920,76793344,595764224,4651472896,
36511354880,287837937664,2276984766464,18060760416256
g.f. 4*x*(-1+7*x)/((6*x-1)*(8*x-1)*(4*x-1)).

rh> 4 points in a side-5 2..9 dimensional grid
rh>
rh> \$ awk '{print FILENAME,\$5}' stat??4.txt
rh> stat204.txt 64
rh> stat304.txt 629
rh> stat404.txt 5632
rh> stat504.txt 48485
rh> stat604.txt 410944
rh> stat704.txt 3470549
rh> stat804.txt 29389312
rh> stat904.txt 250334405

This looks like
a(n) = 3*7^n/2-2*5^n+9^n/2.
a(n)= +21*a(n-1) -143*a(n-2) +315*a(n-3),
Extrapolation (offset 0 by adding a(0)=0, a(1)=5 which makes sense):
0,5,64,629,5632,48485,410944,3470549,29389312,250334405,2147573824,18558863669,
161488417792,1413825023525,12443523805504,110005873155989
G.f. of sequence if a(0) and a(1) included: x*(-5+41*x)/((9*x-1)*(7*x-1)*(5*x-1)).

>From a grand point of view, adding dimensions to these counting problems is
always susceptible to combinatorial arguments of the form "If we add a layer
or a sub-plane, how many new combinations are created by allowing some points
in that extra layer or plane?" So linear recurrences are not a big surprise.

RJM

```