[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