A282998 -id:A282998 - 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.

A239568 Number of ways to place 2 points on a triangular grid of side n so that they are not adjacent.

Original entry on oeis.org

0, 6, 27, 75, 165, 315, 546, 882, 1350, 1980, 2805, 3861, 5187, 6825, 8820, 11220, 14076, 17442, 21375, 25935, 31185, 37191, 44022, 51750, 60450, 70200, 81081, 93177, 106575, 121365, 137640, 155496, 175032, 196350, 219555, 244755, 272061, 301587, 333450, 367770

Offset: 2

Heinrich Ludwig, Mar 22 2014

Heinrich Ludwig, Table of n, a(n) for n = 2..1000
M. J. Hay, J. Schiff, N. J. Fisch, Maximal energy extraction under discrete diffusive exchange, arXiv preprint arXiv:1508.03499, 2015
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1)

Cf. A239567, A032091, A239569 (3 points), A239570 (4 points), A239571 (5 points), A282998 (6 points).

Regarding the third formula, see similar sequences listed in A241765.

concat(0, Vec(3*x^3*(x-2)/(x-1)^5 + O(x^100))) \\ Colin Barker, Mar 22 2014

a(n) = n*(n-1)*(n-2)*(n+5)/8.
G.f.: 3*x^3*(x-2) / (x-1)^5. - Colin Barker, Mar 22 2014
a(n) = Sum_{i=0..n} (i+5)*A000217(i). - Bruno Berselli, Apr 29 2014
a(n) = t(t(n,k),n) + n, where t(n,k) = n*(n+1)/2 + k*n and t(n,1) = A000096(n). - Bruno Berselli, Feb 28 2017

A239569 Number of ways to place 3 points on a triangular grid of side n so that no two of them are adjacent.

Original entry on oeis.org

0, 1, 21, 151, 615, 1845, 4571, 9926, 19566, 35805, 61765, 101541, 160381, 244881, 363195, 525260, 743036, 1030761, 1405221, 1886035, 2495955, 3261181, 4211691, 5381586, 6809450, 8538725, 10618101, 13101921, 16050601, 19531065, 23617195, 28390296, 33939576

Offset: 2

Heinrich Ludwig, Mar 22 2014

Rotations and reflections of placements are counted. If they are to be ignored, see A239573.

Vincenzo Librandi, Table of n, a(n) for n = 2..1000
Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1)

Cf. A239567, A239573, A239568 (2 points), A239570 (4 points), A239571 (5 points), A282998 (6 points).

[(n^2-3*n+2)*(n^4+6*n^3-23*n^2-92*n+264)/48: n in [2..40]]; // Vincenzo Librandi, Mar 23 2014

CoefficientList[Series[- x (11 x^4 - 36 x^3 + 25 x^2 + 14 x + 1)/(x - 1)^7, {x, 0, 40}], x] (* Vincenzo Librandi, Mar 23 2014 *)
LinearRecurrence[{7,-21,35,-35,21,-7,1},{0,1,21,151,615,1845,4571},50] (* Harvey P. Dale, Aug 08 2023 *)

concat(0, Vec(-x^3*(11*x^4-36*x^3+25*x^2+14*x+1)/(x-1)^7 + O(x^100))) \\ Colin Barker, Mar 22 2014

a(n) = (n-1)*(n-2)*(n^4+6*n^3-23*n^2-92*n+264)/48.

G.f.: -x^3*(11*x^4-36*x^3+25*x^2+14*x+1) / (x-1)^7. - Colin Barker, Mar 22 2014

A239570 Number of ways to place 4 points on a triangular grid of side n so that no two of them are adjacent.

Original entry on oeis.org

0, 1, 114, 1137, 6100, 23265, 71211, 186739, 436437, 932850, 1856305, 3483546, 6224439, 10668112, 17640000, 28271370, 44083006, 67084839, 99893412, 145869175, 209275710, 295463091, 411077689, 564300837, 765118875, 1025627200, 1360371051, 1786725864, 2325320137

Offset: 3

Heinrich Ludwig, Mar 22 2014

Rotations and reflections of placements are counted. If they are to be ignored see A239574.

Vincenzo Librandi, Table of n, a(n) for n = 3..1000
Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1)

Cf. A239567, A239574, A239568 (2 points), A239569 (3 points), A239571 (5 points), A282998 (6 points).

[(n^2-5*n+6)*(n^6+9*n^5-39*n^4-353*n^3+950*n^2 +4040*n-11904)/384: n in [3..40]]; // Vincenzo Librandi, Mar 23 2014

CoefficientList[Series[x (38 x^6 - 156 x^5 + 153 x^4 + 113 x^3 - 147 x^2 - 105 x - 1)/(x - 1)^9, {x, 0, 40}], x] (* Vincenzo Librandi, Mar 23 2014 *)
LinearRecurrence[{9,-36,84,-126,126,-84,36,-9,1},{0,1,114,1137,6100,23265,71211,186739,436437},30] (* Harvey P. Dale, May 28 2025 *)

concat(0, Vec(x^4*(38*x^6-156*x^5+153*x^4+113*x^3-147*x^2-105*x-1)/(x-1)^9 + O(x^100))) \\ Colin Barker, Mar 22 2014

a(n) = (n-2)*(n-3)*(n^6+9*n^5-39*n^4-353*n^3+950*n^2+4040*n-11904)/384.

G.f.: x^4*(38*x^6-156*x^5+153*x^4+113*x^3-147*x^2-105*x-1) / (x-1)^9. - Colin Barker, Mar 22 2014

A239571 Number of ways to place 5 points on a triangular grid of side n so that no two of them are adjacent.

Original entry on oeis.org

0, 0, 27, 999, 11565, 74811, 342042, 1239525, 3799488, 10259640, 25076952, 56552364, 119324403, 238062357, 452774595, 826245798, 1454229216, 2479147536, 4108199481, 6636929805, 10479498849, 16207085223, 24596072424, 36687908235, 53862785520, 77929575480

Offset: 3

Heinrich Ludwig, Mar 22 2014

Rotations and reflections of placements are counted. If they are to be ignored see A239575.

Vincenzo Librandi, Table of n, a(n) for n = 3..1000
Index entries for linear recurrences with constant coefficients, signature (11,-55,165,-330,462,-462,330,-165,55,-11,1)

Cf. A239567, A239575, A239568 (2 points), A239569 (3 points), A239570 (4 points), A282998 (6 points).

[(n^2-7*n+12)*(n^8+12*n^7-58*n^6-860*n^5+2141*n^4 +23728*n^3-61316*n^2-244928*n+770880)/3840: n in [3..40]]; // Vincenzo Librandi, Mar 23 2014

CoefficientList[Series[- 3 x^2 (40 x^8 - 185 x^7 + 198 x^6 + 213 x^5 - 243 x^4 - 638 x^3 + 687 x^2 + 234 x + 9)/(x - 1)^11, {x, 0, 40}], x] (* Vincenzo Librandi, Mar 23 2014 *)

concat([0,0], Vec(-3*x^5*(40*x^8-185*x^7+198*x^6+213*x^5-243*x^4-638*x^3+687*x^2+234*x+9)/(x-1)^11 + O(x^100))) \\ Colin Barker, Mar 22 2014

a(n) = (n -3) * (n -4) * (n^8 +12*n^7 -58*n^6 -860*n^5 +2141*n^4 +23728*n^3 -61316*n^2 -244928*n +770880)/3840.

G.f.: -3*x^5*(40*x^8-185*x^7+198*x^6+213*x^5-243*x^4-638*x^3+687*x^2+234*x+9) / (x-1)^11. - Colin Barker, Mar 22 2014

A279446 Number of non-equivalent (mod D_3) ways to place 6 indistinguishable points on a triangular grid of side n so that no two of them are adjacent.

Original entry on oeis.org

0, 0, 1, 66, 2096, 25676, 187984, 983172, 4073312, 14196011, 43309138, 118818916, 298926225, 699619679, 1540212590, 3217045155, 6419240369, 12304959047, 22763742133, 40797668697, 71065355815, 120643462032, 200077436639, 324808463585, 517088445952, 808515893580

Offset: 3

Heinrich Ludwig, Feb 26 2017

Rotations and reflections of placements are not counted. For numbers if they are to be counted see A282998.

			There is a(5) = 1 way to place 6 points on a triangular grid of side n = 5:
        X
       . .
      X . X
     . . . .
    X . X . X

Heinrich Ludwig, Table of n, a(n) for n = 3..1000
Index entries for linear recurrences with constant coefficients, signature (4,0,-17,8,36,-7,-68,-18,113,52,-126,-92,92,126,-52,-113,18,68,7,-36,-8,17,0,-4,1).

Cf. A282998, A239572, A032091 (2 points), A239573 (3 points), A239574 (4 points), A239575 (5 points).

Table[Boole[n > 4] ((n^12 + 6 n^11 - 195 n^10 - 670 n^9 + 17455 n^8 + 13426 n^7 - 835256 n^6 + 1246240 n^5 + 19563664 n^4 - 68181792 n^3 - 131524224 n^2 + 969500160 n - 1298903040)/276480 + Boole[OddQ@ n] (162 n^5 - 715 n^4 - 4480 n^3 + 21955 n^2 + 1108 n - 41685)/30720 + Boole[Mod[n, 3] == 1] (n^2 + n - 25)/27), {n, 3, 28}] (* Michael De Vlieger, Feb 26 2017 *)

concat(vector(2), Vec(x^5*(1 + 62*x + 1832*x^2 + 17309*x^3 + 86394*x^4 + 266304*x^5 + 557979*x^6 + 818157*x^7 + 829988*x^8 + 519203*x^9 + 94134*x^10 - 150065*x^11 - 123434*x^12 + 7445*x^13 + 64052*x^14 + 29943*x^15 - 11247*x^16 - 15803*x^17 - 3012*x^18 + 3100*x^19 + 1722*x^20 - 15*x^21 - 233*x^22 - 56*x^23) / ((1 - x)^13*(1 + x)^6*(1 + x + x^2)^3) + O(x^30))) \\ Colin Barker, Feb 26 2017

a(n) = (n^12 + 6*n^11 - 195*n^10 - 670*n^9 + 17455*n^8 + 13426*n^7 - 835256*n^6 + 1246240*n^5 + 19563664*n^4 - 68181792*n^3 - 131524224*n^2 + 969500160*n - 1298903040)/276480 + IF(MOD(n, 2) = 1, 162*n^5 - 715*n^4 - 4480*n^3 + 21955*n^2 + 1108*n - 41685)/30720 + IF(MOD(n, 3) = 1, n^2 + n - 25)/27 for n>=4.

G.f.: x^5*(1 + 62*x + 1832*x^2 + 17309*x^3 + 86394*x^4 + 266304*x^5 + 557979*x^6 + 818157*x^7 + 829988*x^8 + 519203*x^9 + 94134*x^10 - 150065*x^11 - 123434*x^12 + 7445*x^13 + 64052*x^14 + 29943*x^15 - 11247*x^16 - 15803*x^17 - 3012*x^18 + 3100*x^19 + 1722*x^20 - 15*x^21 - 233*x^22 - 56*x^23) / ((1 - x)^13*(1 + x)^6*(1 + x + x^2)^3). - Colin Barker, Feb 26 2017

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

A239568 Number of ways to place 2 points on a triangular grid of side n so that they are not adjacent.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A239569 Number of ways to place 3 points on a triangular grid of side n so that no two of them are adjacent.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A239570 Number of ways to place 4 points on a triangular grid of side n so that no two of them are adjacent.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A239571 Number of ways to place 5 points on a triangular grid of side n so that no two of them are adjacent.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A279446 Number of non-equivalent (mod D_3) ways to place 6 indistinguishable points on a triangular grid of side n so that no two of them are adjacent.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula