A235454 -id:A235454 - cp's OEIS frontend

A235453 Triangle T(n, k) = Number of non-equivalent (mod D_4) ways to arrange k indistinguishable points on an n X n square grid so that no three of them are collinear. Triangle read by rows.

1, 0, 1, 2, 1, 1, 3, 8, 13, 15, 5, 1, 3, 21, 70, 181, 217, 142, 28, 4, 6, 49, 290, 1253, 3192, 4699, 3385, 1076, 110, 5, 6, 93, 867, 6044, 27041, 77970, 134353, 129929, 62177, 12511, 717, 11, 10, 171, 2266, 22302, 149217, 672506, 1958674, 3531747, 3695848, 2068757

Offset: 1

Heinrich Ludwig, Jan 12 2014

The triangle T(n, k) is irregularly shaped: 1 <= k <= 2n. First row corresponds to n = 1.
Without the restriction "non-equivalent (mod D_4)" the numbers are given by triangle A194193. (But this one is read by antidiagonals!)
T(n, 2n) = A000769(n).
2n is an upper bound on the number of points that can be placed on the grid. For large n, it is conjectured that this bound is not reached (see MathWorld link).

			Triangle begins
1,  0;
1,  2,   1,    1;
3,  8,  13,   15,     5,     1;
3, 21,  70,  181,   217,   142,     28,      4;
6, 49, 290, 1253,  3192,  4699,   3385,   1076,   110,     5;
6, 93, 867, 6044, 27041, 77970, 134353, 129929, 62177, 12511, 717, 11;
...

Heinrich Ludwig, Table of n, a(n) for n = 1..99
Achim Flammenkamp, Progress in the no-three-in-line problem
Eric Weisstein's World of Mathematics, No-Three-in-a-Line-Problem

Cf. A194193, A000938, A000769.
Column 1 is A008805
Column 2 is A014409
Column 3 is A235454
Column 4 is A235455
Column 5 is A235456
Column 6 is A235457
Column 7 is A235458

A235455 Number of non-equivalent (mod D_4) ways to arrange 4 points on an n X n square grid so that no three points are collinear.

Original entry on oeis.org

1, 15, 181, 1253, 6044, 22302, 68661, 183645, 439578, 964938, 1974128, 3801457, 6966581

Offset: 2

Heinrich Ludwig, Jan 12 2014

Column 4 of A235453.
Also number of non-equivalent complete quadrangles on an n X n grid.
Without the restriction "non-equivalent (mod D_4)" the numbers are given by A175383, n >= 2.

			There are a(3) = 15 non-equivalent ways to place 4 points (X) on a 3 X 3 grid. Examples are:
  X . X    . X .    X X .
  . . .    X . X    X . .
  X . X    . X .    . . X

Cf. A235453, A045996, A235454 (3 points), A235456 (5 points), A235457 (6 points), A235458 (7 points)

a(13), a(14) from Heinrich Ludwig, Nov 16 2016

A235456 Number of non-equivalent (mod D_4) ways to arrange 5 points on an n X n square grid so that no three points are collinear.

Original entry on oeis.org

5, 217, 3192, 27041, 149217, 650566, 2317137, 7124316, 19459757, 48617666, 111797647, 241575473

Offset: 3

Heinrich Ludwig, Jan 12 2014

Column 5 of A235453.

Without the restriction "non-equivalent (mod D_4)" the numbers are given by A194190, n >= 3.

			There are a(3) = 5 non-equivalent ways to place 5 points (X) on a 3 X 3 grid:
  X . X    X . X    . X X    X X .    X . X
  X . X    X . .    X . X    X . .    X X .
  . X .    . X X    . X .    . X X    . X .

Cf. A235453, A194190, A235454 (3 points), A235455 (4 points), A235457 (6 points), A235458 (7 points)

a(13), a(14) from Heinrich Ludwig, Nov 16 2016

A235457 Number of non-equivalent (mod D_4) ways to arrange 6 points on an n X n square grid so that no three points are collinear.

Original entry on oeis.org

1, 142, 4699, 77970, 672506, 4338248, 21167201, 85351595, 294664274, 911848844, 2528561187, 6501165477

Offset: 3

Heinrich Ludwig, Jan 12 2014

Column 6 of A235453.

Without the restriction "non-equivalent (mod D_4)" the numbers are given by A194191, n >= 3.

			There is a(3) = 1 way to place 6 points (X) on a 3 X 3 grid (without rotations and reflections):
   . X X
   X . X
   X X .

Cf. A235453, A194191, A235454 (3 points), A235455 (4 points), A235456 (5 points), A235458 (7 points).

a(13), a(14) from Heinrich Ludwig, Nov 16 2016

A235458 Number of non-equivalent (mod D_4) ways to arrange 7 points on an n X n square grid so that no three points are collinear.

Original entry on oeis.org

28, 3385, 134353, 1958674, 19929645, 138586349, 753795278, 3356614240, 13108210508, 44374441652, 137349454120

Offset: 4

Heinrich Ludwig, Jan 12 2014

Column 7 of A235453.

Without the restriction "non-equivalent (mod D_4)" the numbers are given by A194192, n >= 4.

			There are a(4) = 28 non-equivalent ways to place 7 points (X) on a 4 X 4 grid. Example:
   . X X .
   . . . X
   X . . X
   X X . .

Cf. A235453, A194192, A235454 (3 points), A235455 (4 points), A235456 (5 points), A235457 (6 points).

a(13), a(14) from Heinrich Ludwig, Nov 16 2016

A279447 Number of nonequivalent ways to place 3 points on an n X n square grid so that no more than 2 points are on a vertical or horizontal straight line.

Original entry on oeis.org

0, 1, 14, 73, 301, 890, 2321, 5166, 10654, 20055, 35880, 60511, 98419, 153608, 233331, 343820, 496076, 699261, 969234, 1318885, 1770185, 2340646, 3059749, 3950618, 5051786, 6393075, 8023756, 9981531, 12328239, 15110740, 18405415, 22269656, 26796504, 32055353, 38158166

Offset: 1

Heinrich Ludwig, Dec 17 2016

Column 4 of A279453.
Rotations and reflections of placements are not counted. For numbers if they are to be counted see A279437.
For condition "no more than 2 points on straight lines at any angle", see A235454.

Heinrich Ludwig, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (3,1,-11,6,14,-14,-6,11,-1,-3,1).

Cf. A235454, A279437, A279452, A279453, A279454.

Same problem but 2, 4..7 points: A014409, A279448, A279449, A279450, A279451.

I:=[0,1,14,73,301,890,2321,5166,10654,20055,35880]; [n le 11 select I[n] else 3*Self(n-1)+Self(n-2)-11*Self(n-3)+ 6*Self(n-4)+14*Self(n-5)-14*Self(n-6)-6*Self(n-7)+11*Self(n-8)-Self(n-9)-3*Self(n-10)+Self(n-11): n in [1..40]]; // Vincenzo Librandi, Dec 17 2016

LinearRecurrence[{3, 1, -11, 6, 14, -14, -6, 11, -1, -3, 1},{0, 1, 14, 73, 301, 890, 2321, 5166, 10654, 20055, 35880}, 35] (* Vincenzo Librandi Dec 17 2016 *)

concat(0, Vec(x^2*(1 + 11*x + 30*x^2 + 79*x^3 + 62*x^4 + 55*x^5 + 4*x^6 - x^7 - x^8) / ((1 - x)^7*(1 + x)^4) + O(x^30))) \\ Colin Barker, Dec 17 2016

a(n) = (n^6 - 5*n^4 + 14*n^3 - 14*n^2 + 4*n)/48 + IF(MOD(n, 2) = 1, 2*n^3 - 3*n^2 + 1)/16.
a(n) = 3*a(n-1) + a(n-2) - 11*a(n-3) + 6*a(n-4) + 14*a(n-5) - 14*a(n-6) - 6*a(n-7) + 11*a(n-8) - a(n-9) - 3*a(n-10) + a(n-11).
G.f.: x^2*(1 + 11*x + 30*x^2 + 79*x^3 + 62*x^4 + 55*x^5 + 4*x^6 - x^7 - x^8) / ((1 - x)^7*(1 + x)^4). - Colin Barker, Dec 17 2016

cp's OEIS Frontend

A235453 Triangle T(n, k) = Number of non-equivalent (mod D_4) ways to arrange k indistinguishable points on an n X n square grid so that no three of them are collinear. Triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A235455 Number of non-equivalent (mod D_4) ways to arrange 4 points on an n X n square grid so that no three points are collinear.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A235456 Number of non-equivalent (mod D_4) ways to arrange 5 points on an n X n square grid so that no three points are collinear.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A235457 Number of non-equivalent (mod D_4) ways to arrange 6 points on an n X n square grid so that no three points are collinear.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A235458 Number of non-equivalent (mod D_4) ways to arrange 7 points on an n X n square grid so that no three points are collinear.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A279447 Number of nonequivalent ways to place 3 points on an n X n square grid so that no more than 2 points are on a vertical or horizontal straight line.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula