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

A241765 a(n) = n(n + 1)(n + 2)(3n + 17)/24.

Original entry on oeis.org

0, 5, 23, 65, 145, 280, 490, 798, 1230, 1815, 2585, 3575, 4823, 6370, 8260, 10540, 13260, 16473, 20235, 24605, 29645, 35420, 41998, 49450, 57850, 67275, 77805, 89523, 102515, 116870, 132680, 150040, 169048, 189805, 212415, 236985, 263625, 292448

Offset: 0

Bruno Berselli, Apr 28 2014

Equivalently, Sum_{i=0..n} (i+4)*A000217(i).
Sequences of the type Sum_{i=0..n} (i+k)*A000217(i):
k = 0,  A001296: 0,  1,  7, 25,  65, 140, 266, 462, ...
k = 1,  A000914: 0,  2, 11, 35,  85, 175, 322, 546, ...
k = 2,  A050534: 0,  3, 15, 45, 105, 210, 378, 630, ... (deleting two 0)
k = 3,  A215862: 0,  4, 19, 55, 125, 245, 434, 714, ...
k = 4,     a(n): 0,  5, 23, 65, 145, 280, 490, 798, ...
k = 5,  A239568: 0,  6, 27, 75, 165, 315, 546, 882, ...
Antidiagonal sums (without 0) give A034263: 1, 9, 39, 119, 294, ...
Diagonal: 1, 11, 45, 125, 280, 546, ... is A051740.
Also: k = -1 gives A050534 deleting a 0; k = -2 gives 0 followed by A059302.
After 0, partial sums of A212343 and third column of A118788.
This sequence is even related to A005286 by a(n) = n*A005286(n) - Sum_{i=0..n-1} A005286(i).

			a(7) = 4*0 + 5*1 + 6*3 + 7*6 + 8*10 + 9*15 + 10*21 + 11*28 = 798.

Bruno Berselli, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A000217, A005286, A118788, A212343, A227342.

Cf. similar sequences A000914, A001296, A050534, A059302, A215862, A239568 (see table in Comments lines).

/* By first comment: */ k:=4; A000217:=func; [&+[(i+k)*A000217(i): i in [0..n]]: n in [0..40]];

Maple

A241765:=n->n*(n + 1)*(n + 2)*(3*n + 17)/24; seq(A241765(n), n=0..40); # Wesley Ivan Hurt, May 09 2014

Mathematica

Table[n (n + 1) (n + 2) (3 n + 17)/24, {n, 0, 40}] (* or *) LinearRecurrence[{5, -10, 10, -5, 1}, {0, 5, 23, 65, 145}, 40] CoefficientList[Series[x (5 - 2 x)/(1 - x)^5, {x, 0, 40}], x] (* Vincenzo Librandi, May 09 2014 *)

Maxima

makelist(coeff(taylor(x*(5-2*x)/(1-x)^5, x, 0, n), x, n), n, 0, 40);

PARI

a(n)=n*(n+1)*(n+2)*(3*n+17)/24 \\ Charles R Greathouse IV, Oct 07 2015

PARI

x='x+O('x^99); concat(0, Vec(x*(5-2*x)/(1-x)^5)) \\ Altug Alkan, Apr 10 2016

Sage

[n*(n+1)*(n+2)*(3*n+17)/24 for n in (0..40)]

Formula

G.f.: x*(5 - 2*x)/(1 - x)^5.

a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5).

a(n) = A227342(A055998(n+1)).

a(n) = Sum_{j=0..n+2} (-1)^(n-j)*binomial(-j,-n-2)*S1(j,n), S1 Stirling cycle numbers A132393. - Peter Luschny, Apr 10 2016

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

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

Original entry on oeis.org

0, 0, 1, 353, 12231, 153194, 1124820, 5893221, 24425212, 85152341, 259805430, 712840480, 1793423456, 4197531636, 9240962666, 19301854131, 38514786780, 73828909906, 136581190475, 244784427831, 426389859697, 723857976770, 1200460734396, 1948846090829, 3102524331336

Offset: 3

Heinrich Ludwig, Feb 26 2017

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

			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 (13,-78,286,-715,1287,-1716,1716,-1287,715,-286,78,-13,1).

Cf. A279446, A239567, A239568 (2 points), A239569 (3 points), A239570 (4 points), A239571 (5 points).

A282998:=n->(n^12 + 6*n^11 - 195*n^10 - 670*n^9 + 17455*n^8 + 13426*n^7 - 836249*n^6 + 1252990*n^5 + 19599884*n^4 - 68542552*n^3 - 131400416*n^2 + 974223360*n - 1308856320)/46080: 0,seq(A282998(n), n=4..30); # Wesley Ivan Hurt, Apr 10 2017

Drop[CoefficientList[Series[(x^5 * (1 + 340 * x + 7720 * x^2 + 21439 * x^3 - 12927 * x^4 - 27265 * x^5 + 28385 * x^6 - 6252 * x^7 - 116 * x^8 - 2365 * x^9 + 1787 * x^10 - 352 * x^11) / (1 - x)^13 ),{x,0,27}],x],3] (* Indranil Ghosh, Feb 26 2017, from the g.f. by Colin Barker *)

concat(vector(2), Vec(x^5*(1 + 340*x + 7720*x^2 + 21439*x^3 - 12927*x^4 - 27265*x^5 + 28385*x^6 - 6252*x^7 - 116*x^8 - 2365*x^9 + 1787*x^10 - 352*x^11) / (1 - x)^13 + 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 - 836249*n^6 + 1252990*n^5 + 19599884*n^4 - 68542552*n^3 - 131400416*n^2 + 974223360*n - 1308856320)/46080 for n>=4.

G.f.: x^5*(1 + 340*x + 7720*x^2 + 21439*x^3 - 12927*x^4 - 27265*x^5 + 28385*x^6 - 6252*x^7 - 116*x^8 - 2365*x^9 + 1787*x^10 - 352*x^11) / (1 - x)^13. - Colin Barker, Feb 26 2017

A368569 Irregular triangle read by rows: T(n,k) is the number of essential graphs with n nodes and k (directed or undirected) edges (n >= 1, 0 <= k <= n*(n-1)/2).

Original entry on oeis.org

1, 1, 1, 1, 3, 6, 1, 1, 6, 27, 60, 66, 24, 1, 1, 10, 75, 350, 1120, 2130, 2595, 1730, 690, 80, 1, 1, 15, 165, 1235, 6930, 27882, 79825, 162315, 236490, 245150, 180936, 91560, 29890, 5190, 240, 1

Offset: 1

Moritz Schauer, Feb 06 2024

			Triangle T(n,k) (with n >= 1 and 0 <= k <= n*(n-1)/2) begins as follows:
  1;
  1,  1;
  1,  3,  6,   1;
  1,  6, 27,  60,   66,   24,    1;
  1, 10, 75, 350, 1120, 2130, 2595, 1730, 690, 80, 1;
  ...

Row sums give A007984.
Row lengths give A000124.
Column k=1 is A000217.
Column k=2 is A239568.

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

A241765 a(n) = n*(n + 1)*(n + 2)*(3*n + 17)/24.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Maxima

PARI

PARI

Sage

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A368569 Irregular triangle read by rows: T(n,k) is the number of essential graphs with n nodes and k (directed or undirected) edges (n >= 1, 0 <= k <= n*(n-1)/2).

Views

Author

Keywords

Examples

A241765 a(n) = n(n + 1)(n + 2)(3n + 17)/24.