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,3

Comments

In other words, a(n) is 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

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

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

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[Piecewise[{{3, n == 3}, {6, n == 5}}, (4 + 3 n (n + 1) + 8 Cos[2 (n - 1) Pi/3])/18], {n, 20}] (* Eric W. Weisstein, Mar 27 2026 *)
Join[{1, 1, 3, 4, 6}, LinearRecurrence[{2, -1, 1, -2, 1}, {7, 10, 12, 15, 19}, 20]] (* Eric W. Weisstein, Mar 27 2026 *)
CoefficientList[Series[(-1 + x - 2 x^2 + 2 x^3 - 2 x^4 + 3 x^5 - 3 x^6 + 2 x^7 - 2 x^8 + x^9)/((-1 + x)^3 (1 + x + x^2)), {x, 0, 20}], x] (* Eric W. Weisstein, Mar 27 2026 *)

Prog

(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

Crossrefs

Cf. A007997, A058212, A239567.

Cf. A297557 (number of maximum independent vertex sets).

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