login
A244500
Number T(n, k) of ways to place k points on an n X n X n triangular grid so that no pair of them has distance sqrt(3). Triangle read by rows.
8
1, 1, 1, 3, 3, 1, 1, 6, 12, 8, 1, 10, 36, 55, 33, 9, 1, 15, 87, 248, 378, 339, 187, 63, 12, 1, 1, 21, 180, 820, 2190, 3606, 3716, 2340, 825, 125, 1, 28, 333, 2212, 9110, 24474, 43928, 53018, 42774, 22792, 7945, 1764, 196, 1, 36, 567, 5163, 30300, 121077, 339621
OFFSET
1,4
COMMENTS
In the following triangular grid points x have Euclidean distance sqrt(3) from point o. It is the second closest distance possible among grid points.
x
. .
. o .
x . . x
Triangle T(n, k) is irregular: 0 <= k <= max(n), where max(n), the maximal number of points that can be placed on the grid, is:
for n = 3j-2: max(n) = A000326(j) = j(3j-1)/2;
for n = 3j-1 or n = 3j: max(n) = A045943(j) = 3j(j+1)/2; j = 1,2,3,...
Empirical: (1) The number of ways to place the maximal number of points for grid sizes n = 3j are cubes of Catalan numbers, i.e., for n = 3j: T(n, max(n)) = C(j+1)^3 = A033536(j+1). (2) For n = 3j-2: T(n, max(n)) = A244506(n) = A244507^2(n). (3) For n = 3j-1: T(n, max(n)) = A000012(n) = 1 and T(n, max(n)-1) = 3j^2.
Row n is also the coefficients of the independence polynomial of the n-triangular honeycomb acute knight graph. - Eric W. Weisstein, May 21 2017
LINKS
Stan Wagon, Graph Theory Problems from Hexagonal and Traditional Chess, The College Mathematics Journal, Vol. 45, No. 4, September 2014, pp. 278-287.
Eric Weisstein's World of Mathematics, Independence Polynomial
EXAMPLE
On an 8 X 8 X 8 grid there is T(8, 18) = 1 way to place 18 points (x) so that no pair of points has the distance square root of 3.
x
x x
. . .
x . . x
x x . x x
. . . . . .
x . . x . . x
x x . x x . x x
Continuation of this pattern will give the unique maximal solution for all n = 3j-1.
Triangle T(n, k) begins:
1, 1;
1, 3, 3, 1;
1, 6, 12, 8;
1, 10, 36, 55, 33, 9;
1, 15, 87, 248, 378, 339, 187, 63, 12, 1;
1, 21, 180, 820, 2190, 3606, 3716, 2340, 825, 125;
First row refers to n = 1.
CROSSREFS
Cf. A000217 (column 2), A086274 (1/3 * column 3), A244501 (column 4), A244502 (column 5), A244503 (column 6).
Cf. A287195 (length of row n). - Eric W. Weisstein, May 21 2017
Cf. A287204 (row sums). - Eric W. Weisstein, May 21 2017
Sequence in context: A319699 A157636 A086626 * A300695 A296186 A232967
KEYWORD
nonn,tabf
AUTHOR
Heinrich Ludwig, Jun 29 2014
STATUS
approved