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.

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

Offset: 1

Author

Heinrich Ludwig, Mar 18 2014

Keywords

• nonn
• easy

Comments

In other words, the independence number of the (n-1)-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 n-triangular honeycomb king graph. - Eric W. Weisstein, Sep 06 2017

Examples

			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
		

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. 33-62.
• 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 Number
• Eric Weisstein's World of Mathematics, Triangular Grid Graph
• Index entries for linear recurrences with constant coefficients, signature (2,-1,1,-2,1).

Crossrefs

Cf. A007997, A058212, A239567.

Programs

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 *)

PARI

Vec(x*(x^9-2*x^8+2*x^7-3*x^6+3*x^5-2*x^4+2*x^3-2*x^2+x-1)/((x-1)^3*(x^2+x+1)) + O(x^100)) \\ Colin Barker, Feb 08 2015

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^9-2*x^8+2*x^7-3*x^6+3*x^5-2*x^4+2*x^3-2*x^2+x-1) / ((x-1)^3*(x^2+x+1)). - Colin Barker, Feb 08 2015

Extensions

Extended by Charles R Greathouse IV, Dec 04 2014