A239438 -id:A239438 - cp's OEIS frontend

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

Heinrich Ludwig, Mar 21 2014

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

			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)

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

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.

A239572 Triangle T(n, k) = Numbers of non-equivalent (mod D_3) ways to place k points on a triangular grid of side n so that no two of them are adjacent. Triangle read by rows.

Original entry on oeis.org

1, 1, 2, 2, 1, 3, 6, 6, 1, 4, 16, 32, 24, 7, 1, 5, 32, 113, 200, 176, 66, 6, 7, 60, 329, 1053, 1976, 2096, 1162, 302, 34, 2, 8, 100, 790, 3932, 12565, 25676, 32963, 25638, 11294, 2493, 222, 7, 10, 160, 1702, 11988, 57275, 187984, 425329, 658608, 684671, 462519

Offset: 1

Heinrich Ludwig, Mar 22 2014

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).
Without the restriction "non-equivalent (mod D_3)" numbers are given by A239567.

			Triangle begins
  1;
  1;
  2,   2,   1;
  3,   6,   6,    1;
  4,  16,  32,   24,     7,     1;
  5,  32, 113,  200,   176,    66,     6;
  7,  60, 329, 1053,  1976,  2096,  1162,   302,    34,    2;
  8, 100, 790, 3932, 12565, 25676, 32963, 25638, 11294, 2493, 222, 7;

Heinrich Ludwig, Table of n, a(n) for n = 1..136

Cf. A239438, A239567.
Column 1 is A001399,
Column 2 is A032091,
Column 3 is A239573,
Column 4 is A239574,
Column 5 is A239575,
Column 6 is A279446.

A027740 Number of independent subsets of nodes in graph formed from n-fold subdivision of triangle.

Original entry on oeis.org

1, 2, 4, 14, 60, 384, 3318, 40638, 689636, 16383974, 542420394, 25075022590, 1617185558560, 145563089994148, 18283036276489970, 3204638749437865046, 783848125594781710150, 267554112823378352976752

Offset: 0

R. H. Hardin

In other words, number of independent vertex sets (and vertex covers) in the (n-1)-triangular grid graph. - Eric W. Weisstein, Jun 14 2017

Number of planar n X n X n binary triangular grids with no more than 1 one in any similarly oriented 2 X 2 X 2 subtriangle. - R. H. Hardin, Dec 27 2008

Liang Kai, Table of n, a(n) for n = 0..40
Kai Liang, Independent Set Enumeration and Estimation of Related Constants of Grid Graphs, arXiv:2507.04007 [math.CO], 2025. See pp. 1, 10.
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Triangular Grid Graph
Eric Weisstein's World of Mathematics, Vertex Cover

Cf. A239567, A239438, A287064.

A297557 Number of maximum independent vertex sets in the n-triangular grid graph.

Original entry on oeis.org

1, 3, 1, 1, 1, 27, 2, 28, 32, 1, 27, 27, 1, 27, 27, 1, 27, 27, 1, 27, 27, 1, 27, 27, 1, 27, 27, 1, 27, 27, 1, 27, 27, 1, 27, 27, 1, 27

Offset: 0

Eric W. Weisstein, Dec 31 2017

John Machacek, Unique maximum independent sets in graphs on monomials of a fixed degree, arXiv:2010.11112 [math.CO], 2020-2021. See Theorem 2.1 p. 4.
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, Maximum Independent Vertex Set
Eric Weisstein's World of Mathematics, Triangular Grid Graph

Cf. A027740, A197564, A239438.

Conjecture: a(n) = a(n-3) for n >= 12. - Andrew Howroyd, Jan 01 2018

a(3k) = 1 for all k != 2. - John Machacek, May 01 2021

a(11)-a(24) from Andrew Howroyd, Jan 01 2018

a(25)-a(37) from Eric W. Weisstein, Feb 10 2024

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A239572 Triangle T(n, k) = Numbers of non-equivalent (mod D_3) ways to place k points on a triangular grid of side n so that no two of them are adjacent. Triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A027740 Number of independent subsets of nodes in graph formed from n-fold subdivision of triangle.

Views

Author

Keywords

Comments

Links

Crossrefs

A297557 Number of maximum independent vertex sets in the n-triangular grid graph.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions