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

Author

Heinrich Ludwig, Mar 21 2014

Keywords

• nonn
• tabf

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

Examples

			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)
		

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

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.