

A239438


Maximal number of points that can be placed on a triangular grid of side n so that there is no pair of adjacent points.


5



1, 1, 3, 4, 6, 7, 10, 12, 15, 19, 22, 26, 31, 35, 40, 46, 51, 57, 64, 70, 77, 85, 92, 100, 109, 117, 126, 136, 145, 155, 166, 176, 187, 199, 210, 222, 235, 247, 260, 274, 287, 301, 316, 330, 345, 361, 376, 392, 409
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

In other words, the independence number of the (n1)triangular grid graph.
Apart from a(3) and a(5) same as A007997(n+4) and A058212(n+2).  Eric W. Weisstein, Jun 14 2017
Also the independence number of the ntriangular honeycomb king graph.  Eric W. Weisstein, Sep 06 2017


LINKS

Colin Barker, Table of n, a(n) for n = 1..1000
A. V. Geramita, D. Gregory, and L. Roberts, Monomial ideals and points in projective space, J. Pure Applied Alg 40 (1986), pp. 3362.
Stan Wagon, Graph Theory Problems from Hexagonal and Traditional Chess, The College Mathematics Journal, Vol. 45, No. 4, September 2014, pp. 278287.
Eric Weisstein's World of Mathematics, Independence Number
Eric Weisstein's World of Mathematics, Triangular Grid Graph
Index entries for linear recurrences with constant coefficients, signature (2,1,1,2,1).


FORMULA

a(n) = ceiling(n(n+1)/6) for n > 5, see Geramita, Gregory, & Roberts theorem 5.4.  Charles R Greathouse IV, Dec 04 2014
G.f.: x*(x^92*x^8+2*x^73*x^6+3*x^52*x^4+2*x^32*x^2+x1) / ((x1)^3*(x^2+x+1)).  Colin Barker, Feb 08 2015


EXAMPLE

On a triangular grid of side 5 at most a(5) = 6 points (X) can be placed so that there is no pair of adjacent points.
X
. .
X . X
. . . .
X . X . X


MATHEMATICA

Table[1/18 (Piecewise[{{28, n == 2  n == 4}}, 10] + 3 n (3 + n) + 8 Cos[(2 n Pi)/3]), {n, 0, 20}] (* Eric W. Weisstein, Jun 14 2017 *)


PROG

(PARI) Vec(x*(x^92*x^8+2*x^73*x^6+3*x^52*x^4+2*x^32*x^2+x1)/((x1)^3*(x^2+x+1)) + O(x^100)) \\ Colin Barker, Feb 08 2015


CROSSREFS

Cf. A007997, A058212, A239567.
Sequence in context: A157611 A147609 A202169 * A317138 A032387 A026313
Adjacent sequences: A239435 A239436 A239437 * A239439 A239440 A239441


KEYWORD

nonn,easy


AUTHOR

Heinrich Ludwig, Mar 18 2014


EXTENSIONS

Extended by Charles R Greathouse IV, Dec 04 2014


STATUS

approved



