login
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.
11
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
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
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
KEYWORD
nonn,tabf
AUTHOR
Heinrich Ludwig, Mar 21 2014
STATUS
approved