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.

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

Heinrich Ludwig, Table of n, a(n) for n = 1..153

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. A000108, A000326, A033536, A045943, A244506, A244507.

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

Adjacent sequences: A244497 A244498 A244499 * A244501 A244502 A244503

Keyword

nonn,tabf

Author

Heinrich Ludwig, Jun 29 2014

Status

approved