A239567 Triangle T(n, k) = Numbers of ways to place k points on a triangular grid of side n so that no two of them are adjacent. Triangle read by rows.

1, 3, 6, 6, 1, 10, 27, 21, 1, 15, 75, 151, 114, 27, 1, 21, 165, 615, 1137, 999, 353, 27, 28, 315, 1845, 6100, 11565, 12231, 6715, 1686, 150, 2, 36, 546, 4571, 23265, 74811, 153194, 196899, 153072, 67229, 14727, 1257, 28, 45, 882, 9926, 71211, 342042, 1124820

Offset

1,2

Comments

The triangle T(n, k) is irregularly shaped: 1 <= k <= A239438(n). First row corresponds to n = 1.

The maximal number of points that can be placed on a triangular grid of side n so that no two of them are adjacent is given by A239438(n).

Row n is the coefficients of the independence polynomial of the triangular grid graph, omitting x^0 coefficients. - Eric W. Weisstein, Nov 11 2016

Links

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

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

Eric Weisstein's World of Mathematics, Triangular Grid Graph

Example

Triangle begins:
   1;
   3;
   6,   6,    1;
  10,  27,   21,    1;
  15,  75,  151,  114,    27,     1;
  21, 165,  615, 1137,   999,   353,   27;
  28, 315, 1845, 6100, 11565, 12231, 6715, 1686, 150, 2;
...
There is T(10, 19) = 1 way to place 19 points (X) on a grid of side 10 under to the condition mentioned above:
               X
              . .
             . X .
            X . . X
           . . X . .
          . X . . X .
         X . . X . . X
        . . X . . X . .
       . X . . X . . X .
      X . . X . . X . . X
This pattern seems to be the densest packing for all n == 1 (mod 3) and n >= 10.
From Eric W. Weisstein, Nov 11 2016: (Start)
Independence polynomials of the n-triangular grid graphs for n = 1, 2, ...:
1 + 3*x,
1 + 6*x + 6*x^2 + x^3,
1 + 10*x + 27*x^2 + 21*x^3 + x^4,
1 + 15*x + 75*x^2 + 151*x^3 + 114*x^4 + 27*x^5 + x^6,
...
(End)

Crossrefs

Cf. A239438, A239572,

Column 1 is A000217,

Column 2 is A239568,

Column 3 is A239569,

Column 4 is A239570,

Column 5 is A239571,

Column 6 is A282998.

Row sums are A027740(n)-1.

Sequence in context: A319886 A021736 A091478 * A198239 A086727 A309496

Adjacent sequences: A239564 A239565 A239566 * A239568 A239569 A239570

Keyword

nonn,tabf

Author

Heinrich Ludwig, Mar 21 2014

Status

approved