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

[Richard Mathar]

Back to http://list.seqfan.eu/pipermail/seqfan/2010-May/004757.html ,
a summary of formula patterns found in the problem of counting the sets
of t collinear points in an l-by-l-by-l...-by-l d-dimensional cube,
which I'll call a(t,l,d). Ron's table is clearly instrumental to uncover these.

This concerns the cases where t (the length of the "chain" of the points)
is rather close to "l", the edge length; if this is not the case, the
formulas are more complicated because the chains are not simply on 0, 90
and 45 degrees angles relative to the cube axes but may collect points
with generalized knight's moves. 

i)
a(l,l,d) is documented by A105373 and A102728.


ii)
a(l-1,l,d) = -(l-1)*l^d/2 +(l-2)*(l+2)^d/2 +(l+4)^d/2 .
The formula has a combinatorial interpretation related to a(l,l,d)
plus "subdiagonal" corrections which can be computed from the hull
(surface content) of the enclosing cube.

Examples in rows l=4,5,..., columns d=0,1,2,..:
0,4,44,376,2960,22624,171584,1303936,9969920,  A178294
0,5,64,629,5632,48485,410944,3470549,29389312,  A178295
0,6,88,984,9952,96096,907648,8494464,79355392,   A178296
0,7,116,1459,16520,177727,1861436,19230379,197501840,  A178297
0,8,148,2072,26032,309728,3575488,40575872,456270592,
0,9,184,2841,39280,513129,6488104,80447481,985934560,
0,10,224,3784,57152,814240,11208704,151033984,2007821312,

(The column d=2 is A137882.)


iii)
a(l-2,l,d) = -binomial(l-1,2)*l^d/2 +binomial(l-2,2)*(l+2)^d/2 
            +(l-3)*(l+4)^d/2 + (l+6)^d/2.

Examples in rows l=6,7,...,  colums d=0,1,2,...
0,15,234,2820,31176,333840,3546144,37807680,406924416,  A178299
0,21,364,4833,58360,676941,7731364,88086873,1008580720,  A178351
0,28,536,7816,103040,1296928,15977216,195266176,2386688000,
0,36,756,12048,172872,2357916,31336956,411328968,5376751632,
0,45,1030,17844,277528,4090320,58545760,824810304,11532489088,
0,55,1364,25555,428936,6807055,104653724,1579618795,23599519376,

(One column A000217, one related to A061989.)

iv)
a(l-3,l,d) = -binomial(l-1,3)*l^d/2 + binomial(l-2,3)*(l+2)^d/2 
             + binomial(l-3,2)*(l+4)^d/2 +(l-4)*(l+6)^d/2+(l+8)^d/2 .

Examples in rows l=9,10,... colums d=0,1,2,...
0,84,1824,30252,455040,6558084,92868384,1310034012,18559057920,
0,120,2820,50400,813072,12504960,188005440,2801548800,41730154752,
0,165,4180,80289,1387336,22770045,363905500,5741359929,90186558736,
0,220,5984,123136,2273792,39773440,675467264,11289404416,187263107072,
(One column A000292).

All the formulas above are a(l-r,l,d) equal to a sum over (l+const)^d .
Therefore, getting the generating function along the rows of the tables is just
a matter of calculating some geometric series. As mentioned above,
one can "extrapolate" these formulas to lower row numbers, but then
the counts will cover only the collinear points along cube axes and
diagonals.

Reading downwards columns (taking d=const in any of the tables) is obviously
evaluating polynomials in l.

Richard Mathar