[seqfan] Related to A005059

David Wilson davidwwilson at comcast.net
Sat Aug 11 12:18:42 CEST 2012


I was contacted about my observation that the number of 3-point lines 
through an n-dimensional grid of side 3 is A005059(n) = (5^n-3^n)/2.  
For example, in the normal 2D tic-tac-toe board of side 3, there are 
a(2) = 8 rows. In the 3D tic-tac-toe board of side 3, there would be 
a(3) = 49 rows. In an n-dimensional tic-tac-toe board, there would be 
a(n) rows.

So lets generalize this. For an n-dimensional grid of side p, we define 
f(p, n, k) (p >= 1, n >= 0, k >= 0) as the number of k-dimensional 
subgrids of side p. In these terms, f(3, 2, 1) = 8, the number of lines 
in a normal 2D tic-tac-toe board, while f(3, n, 1) = A005059(n) would be 
the number of lines in an n-dimensional tic-tac-toe board. The number of 
3x3 planes in a 3x3x3 cube would be presumably be f(3, 3, 2) = 15 (9 
planes orthogonal to a face, 6 planes diagonal to a face).

It's fairly easy that f(1, n, k) = 1 if 0 <= k <= n; 0 otherwise.

For p >= 2, I think I have a definition for f(p, n, k):

     f(p, n, k) = 0, if k < 0 or k > n; 1 if k == n; (2k+p)*f(p, n-1, k) 
+ f(p, n-1, k-1) otherwise.

Perhaps someone could confirm or deny this recurrence.




More information about the SeqFan mailing list