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

Comments

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

Links

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

Example

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

Crossrefs

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

Sequence in context: A195805 A293908 A346249 * A219206 A077385 A337219

Adjacent sequences: A235450 A235451 A235452 * A235454 A235455 A235456

Keyword

nonn,tabf

Author

Heinrich Ludwig, Jan 12 2014

Status

approved